On the public citation graph
Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
0 signed · 156 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/rsa.3240030308openalex-snapshot
Simple Constructions of Almost k‐wise Independent Random Variables
inferredcites →https://doi.org/10.1006/jcom.1993.1014openalex-snapshot
Witnesses for Boolean Matrix Multiplication and for Transitive Closure
inferredcites →https://doi.org/10.1006/jcss.1997.1388openalex-snapshot
On the Exponent of the All Pairs Shortest Path Problem
inferredcites →https://doi.org/10.1007/bf02074879openalex-snapshot
The effect of table expansion on the program complexity of perfect hash functions
inferredcites →https://doi.org/10.1016/0022-0000(88)90003-7openalex-snapshot
Probabilistic construction of deterministic algorithms: Approximating packing integer programs
inferredcites →https://doi.org/10.1016/0022-0000(93)90033-sopenalex-snapshot
Removing randomness in parallel computation without a processor penalty
inferredcites →https://doi.org/10.1016/0196-6774(86)90019-2openalex-snapshot
A fast and simple randomized parallel algorithm for the maximal independent set problem
inferredcites →https://doi.org/10.1016/s0022-0000(05)80069-8openalex-snapshot
The probabilistic method yields deterministic parallel algorithms
inferredcites →https://doi.org/10.1016/s0747-7171(08)80013-2openalex-snapshot
Matrix multiplication via arithmetic progressions
inferredcites →https://doi.org/10.1017/s0963548300001280openalex-snapshot
Perfect Hashing and Probability
inferredcites →https://doi.org/10.1109/18.119713openalex-snapshot
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
inferredcites →https://doi.org/10.1109/fscs.1990.89575openalex-snapshot
Simple construction of almost k-wise independent random variables
inferredcites →https://doi.org/10.1109/sfcs.1986.45openalex-snapshot
Probabilistic construction of deterministic algorithms: Approximating packing integer programs
inferredcites →https://doi.org/10.1109/sfcs.1989.63448openalex-snapshot
The probabilistic method yields deterministic parallel algorithms
inferredcites →https://doi.org/10.1109/sfcs.1992.267748openalex-snapshot
Witnesses for Boolean matrix multiplication and for shortest paths
inferredcites →https://doi.org/10.1137/0215074openalex-snapshot
A Simple Parallel Algorithm for the Maximal Independent Set Problem
inferredcites →https://doi.org/10.1137/0219054openalex-snapshot
The Spatial Complexity of Oblivious k -Probe Hash Functions
inferredcites →https://doi.org/10.1137/0222053openalex-snapshot
Small-Bias Probability Spaces: Efficient Constructions and Applications
inferredcites →https://doi.org/10.1137/0605009openalex-snapshot
On the Size of Separating Systems and Families of Perfect Hash Functions
inferredcites →https://doi.org/10.1137/0607062openalex-snapshot
Fredman–Komlós bounds and information theory
inferredcites →https://doi.org/10.1137/1.9781611970074openalex-snapshot
Ten Lectures on the Probabilistic Method
inferredcites →https://doi.org/10.1145/115234.115347openalex-snapshot
Simulating (log c n )-wise independence in NC
inferredcites →https://doi.org/10.1145/129712.129784openalex-snapshot
On the all-pairs-shortest-path problem
inferredcites →https://doi.org/10.1145/3532.3538openalex-snapshot
A polynomial time generator for minimal perfect hash functions
inferredcites →https://doi.org/10.1145/4221.4226openalex-snapshot
A fast parallel algorithm for the maximal independent set problem
inferredcites →https://doi.org/10.1145/828.1884openalex-snapshot
Storing a Sparse Table with 0 (1) Worst Case Access Time
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.2139/ssrn.4016393openalex-extracted
Breaking the Hegemony of the Triangle Method in Clique Detection
inferred← citeshttps://doi.org/10.1006/jcss.1999.1695openalex-snapshot
Improved Algorithms via Approximations of Probability Distributions
inferred← citeshttps://doi.org/10.1006/jcta.1998.2876openalex-snapshot
Optimal Linear Perfect Hash Families
inferred← citeshttps://doi.org/10.1006/jcta.1999.3050openalex-snapshot
Perfect Hash Families: Probabilistic Methods and Explicit Constructions
inferred← citeshttps://doi.org/10.1006/jcta.2000.3068openalex-snapshot
Explicit Constructions of Perfect Hash Families from Algebraic Curves over Finite Fields
inferred← citeshttps://doi.org/10.1007/10718964_28openalex-snapshot
On Multiplicative Secret Sharing Schemes
inferred← citeshttps://doi.org/10.1007/10719994_15openalex-snapshot
A New Approach to Robust Threshold RSA Signature Schemes
inferred← citeshttps://doi.org/10.1007/11496656_23openalex-snapshot
Two Dimensional Parameterized Matching
inferred← citeshttps://doi.org/10.1007/11523468_20openalex-snapshot
LCA Queries in Directed Acyclic Graphs
inferred← citeshttps://doi.org/10.1007/11523468_22openalex-snapshot
Deterministic Constructions of Approximate Distance Oracles and Spanners
inferred← citeshttps://doi.org/10.1007/11786986_24openalex-snapshot
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
inferred← citeshttps://doi.org/10.1007/3-540-36136-7_44openalex-snapshot
A Geometric Approach to Boolean Matrix Multiplication
inferred← citeshttps://doi.org/10.1007/3-540-36413-7_24openalex-snapshot
Robust Information-Theoretic Private Information Retrieval
inferred← citeshttps://doi.org/10.1007/3-540-44634-6_24openalex-snapshot
Fast Boolean Matrix Multiplication for Highly Clustered Data
inferred← citeshttps://doi.org/10.1007/3-540-44676-1_3openalex-snapshot
Exact and Approximate Distances in Graphs — A Survey
inferred← citeshttps://doi.org/10.1007/3-540-49543-6_18openalex-snapshot
Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract)
inferred← citeshttps://doi.org/10.1007/3-540-61422-2_115openalex-snapshot
Derandomization via small sample spaces
inferred← citeshttps://doi.org/10.1007/3-540-61440-0_159openalex-snapshot
Improved parallel approximation of a class of integer programming problems
inferred← citeshttps://doi.org/10.1007/978-1-4615-0013-1_18openalex-snapshot
Derandomization in Combinatorial Optimization
inferred← citeshttps://doi.org/10.1007/978-3-030-55857-4_7openalex-snapshot
Perfect Hash Families: The Generalization to Higher Indices
inferred← citeshttps://doi.org/10.1007/978-3-030-64378-2_3openalex-snapshot
Barriers for Succinct Arguments in the Random Oracle Model
inferred← citeshttps://doi.org/10.1007/978-3-030-67899-9_35openalex-snapshot
Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products
inferred← citeshttps://doi.org/10.1007/978-3-031-21203-1_25openalex-snapshot
The FastMap Pipeline for Facility Location Problems
inferred← citeshttps://doi.org/10.1007/978-3-0348-8295-8_26openalex-snapshot
Robust Additive Secret Sharing Schemes over Z m
inferred← citeshttps://doi.org/10.1007/978-3-319-09174-7_35openalex-snapshot
Approximating the $$k$$ -Set Packing Problem by Local Improvements
inferred← citeshttps://doi.org/10.1007/978-3-319-18173-8_5openalex-snapshot
Linear Time Constructions of Some $$d$$-Restriction Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-26626-8_33openalex-snapshot
Extreme Witnesses and Their Applications
inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_101openalex-snapshot
A New Algorithm for Optimal Constraint Satisfaction and Its Implications
inferred← citeshttps://doi.org/10.1007/978-3-540-45078-8_29openalex-snapshot
An Improved Bound on Boolean Matrix Multiplication for Highly Clustered Data
inferred← citeshttps://doi.org/10.1007/978-3-540-48000-6_32openalex-snapshot
Broadcast Authentication in Group Communication
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_8openalex-snapshot
Constructing Efficient Dictionaries in Close to Sorting Time
inferred← citeshttps://doi.org/10.1007/978-3-540-70583-3_51openalex-snapshot
History-Independent Cuckoo Hashing
inferred← citeshttps://doi.org/10.1007/978-3-540-73437-6_6openalex-snapshot
Finding Witnesses by Peeling
inferred← citeshttps://doi.org/10.1007/978-3-540-73951-7_13openalex-snapshot
Simple and Space-Efficient Minimal Perfect Hash Functions
inferred← citeshttps://doi.org/10.1007/978-3-540-74450-4_26openalex-snapshot
All-Pairs Ancestor Problems in Weighted Dags
inferred← citeshttps://doi.org/10.1007/978-3-540-75520-3_17openalex-snapshot
Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
inferred← citeshttps://doi.org/10.1007/978-3-540-75520-3_25openalex-snapshot
Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
inferred← citeshttps://doi.org/10.1007/978-3-642-04128-0_37openalex-snapshot
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
inferred← citeshttps://doi.org/10.1007/978-3-642-21254-3_26openalex-snapshot
Unique Small Subgraphs Are Not Easier to Find
inferred← citeshttps://doi.org/10.1007/978-3-642-27660-6_31openalex-snapshot
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-31612-8_30openalex-snapshot
Perfect Hashing and CNF Encodings of Cardinality Constraints
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_67openalex-snapshot
Large Neighborhood Local Search for the Maximum Set Packing Problem
inferred← citeshttps://doi.org/10.1007/bf01940869openalex-snapshot
Introduction to special issue on randomized and derandomized algorithms
inferred← citeshttps://doi.org/10.1007/bf02523683openalex-snapshot
Improved parallel approximation of a class of integer programming problems
inferred← citeshttps://doi.org/10.1007/s00145-007-0424-2openalex-snapshot
Robust Information-Theoretic Private Information Retrieval
inferred← citeshttps://doi.org/10.1007/s00446-016-0270-2openalex-snapshot
Algebraic methods in the congested clique
inferred← citeshttps://doi.org/10.1007/s00453-009-9328-xopenalex-snapshot
All-Pairs Bottleneck Paths in Vertex Weighted Graphs
inferred← citeshttps://doi.org/10.1007/s00453-010-9441-xopenalex-snapshot
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
inferred← citeshttps://doi.org/10.1007/s00453-012-9742-3openalex-snapshot
On Minimum Witnesses for Boolean Matrix Multiplication
inferred← citeshttps://doi.org/10.1007/s00453-018-0492-8openalex-snapshot
Extreme Witnesses and Their Applications
inferred← citeshttps://doi.org/10.1007/s10623-006-0007-5openalex-snapshot
Generalised Cumulative Arrays in Secret Sharing
inferred← citeshttps://doi.org/10.1007/s11425-017-9378-yopenalex-snapshot
Some intriguing upper bounds for separating hash families
inferred← citeshttps://doi.org/10.1016/j.cosrev.2013.06.001openalex-snapshot
Conjunctive and Boolean grammars: The true general case of the context-free grammars
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105227openalex-snapshot
Blazing a trail via matrix multiplications: A faster algorithm for non-shortest induced paths
inferred← citeshttps://doi.org/10.1016/j.ipl.2008.10.012openalex-snapshot
Faster multi-witnesses for Boolean matrix multiplication
inferred← citeshttps://doi.org/10.1016/j.ipl.2018.02.010openalex-snapshot
Are unique subgraphs not easier to find?
inferred← citeshttps://doi.org/10.1016/j.is.2012.06.002openalex-snapshot
Practical perfect hashing in nearly optimal space
inferred← citeshttps://doi.org/10.1016/j.jcta.2025.106075openalex-snapshot
Separating hash families with large universe
inferred← citeshttps://doi.org/10.1016/j.laa.2011.11.032openalex-snapshot
Path Laplacian matrices: Introduction and application to the analysis of consensus in networks
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.09.023openalex-snapshot
A new algorithm for optimal 2-constraint satisfaction and its implications
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.02.053openalex-snapshot
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.01.032openalex-snapshot
All-pairs disjoint paths from a common ancestor in O(nω) time
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.09.011openalex-snapshot
Parsing by matrix multiplication generalized to Boolean grammars
inferred← citeshttps://doi.org/10.1016/j.tcs.2014.05.005openalex-snapshot
New space/time tradeoffs for top- k document retrieval on sequences
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.08.024openalex-snapshot
Constant query time (1 + ϵ)-approximate distance oracle for planar graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00184-5openalex-snapshot
Broadcast authentication for group communication
inferred← citeshttps://doi.org/10.1016/s1389-1286(00)00169-9openalex-snapshot
Broadcast anti-jamming systems
inferred← citeshttps://doi.org/10.1023/a:1008268610932openalex-snapshot
On Some Methods for Unconditionally Secure Key Distribution and Broadcast Encryption
inferred← citeshttps://doi.org/10.1080/00207160.2012.701287openalex-snapshot
Unique subgraphs are not easier to find
inferred← citeshttps://doi.org/10.1080/00207160214648openalex-snapshot
Bounds And Constructions For Threshold Shared Generation Of Authenticators
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00074openalex-snapshot
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]
inferred← citeshttps://doi.org/10.1109/isit63088.2025.11195530openalex-snapshot
A New Construction Structure on Coded Caching with Linear Subpacketization: Non-Half-Sum Disjoint Packing
inferred← citeshttps://doi.org/10.1109/sfcs.1995.492475openalex-snapshot
Splitters and near-optimal derandomization
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743464openalex-snapshot
All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms
inferred← citeshttps://doi.org/10.1137/1.9781611973082.114openalex-snapshot
Counting and detecting small subgraphs via equations and matrix multiplication
inferred← citeshttps://doi.org/10.1137/140998949openalex-snapshot
Time-Optimal Top-$k$ Document Retrieval
inferred← citeshttps://doi.org/10.1137/21m1463707openalex-snapshot
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
inferred← citeshttps://doi.org/10.1137/23m1587713openalex-snapshot
Optimal Adjacency Labels for Subgraphs of Cartesian Products
inferred← citeshttps://doi.org/10.1137/s0895480196304246openalex-snapshot
Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes
inferred← citeshttps://doi.org/10.1142/s0129054123500259openalex-snapshot
Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products
inferred← citeshttps://doi.org/10.1145/1240233.1240242openalex-snapshot
Dynamic text and static pattern matching
inferred← citeshttps://doi.org/10.1145/1321440.1321532openalex-snapshot
External perfect hashing for very large key sets
inferred← citeshttps://doi.org/10.1145/1328911.1328912openalex-snapshot
Uniform deterministic dictionaries
inferred← citeshttps://doi.org/10.1145/1367064.1367069openalex-snapshot
Roundtrip spanners and roundtrip routing in directed graphs
inferred← citeshttps://doi.org/10.1145/1536414.1536477openalex-snapshot
Finding, minimizing, and counting weighted subgraphs
inferred← citeshttps://doi.org/10.1145/1798596.1798597openalex-snapshot
Finding heaviest H -subgraphs in real weighted graphs, with applications
inferred← citeshttps://doi.org/10.1145/195058.195411openalex-snapshot
Improved algorithms via approximations of probability distributions (extended abstract)
inferred← citeshttps://doi.org/10.1145/2650220openalex-snapshot
Two-Dimensional Parameterized Matching
inferred← citeshttps://doi.org/10.1145/2767386.2767414openalex-snapshot
Algebraic Methods in the Congested Clique
inferred← citeshttps://doi.org/10.1145/301250.301271openalex-snapshot
All pairs lightest shortest paths
inferred← citeshttps://doi.org/10.1145/345542.345611openalex-snapshot
Fast practical algorithms for the Boolean-product-witness-matrix problem
inferred← citeshttps://doi.org/10.1145/3514231openalex-snapshot
Optimal Joins Using Compressed Quadtrees
inferred← citeshttps://doi.org/10.1145/3519270.3538414openalex-snapshot
Can't See the Forest for the Trees
inferred← citeshttps://doi.org/10.1145/3673760openalex-snapshot
Deterministic Replacement Path Covering
inferred← citeshttps://doi.org/10.1145/378580.378622openalex-snapshot
Finding large independent sets of hypergraphs in parallel
inferred← citeshttps://doi.org/10.1145/567112.567114openalex-snapshot
All pairs shortest paths using bridging sets and rectangular matrix multiplication
inferred← citeshttps://doi.org/10.11606/t.45.2013.tde-13022014-083516openalex-snapshot
Algoritmos para junções em digrafos acíclicos e uma aplicação na Antropologia
inferred← citeshttps://doi.org/10.1360/ssm-2022-0008openalex-snapshot
Sparse hypergraphs: From theory to applications
inferred← citeshttps://doi.org/10.22456/2175-2745.26905openalex-snapshot
Deterministic and efficient minimal perfect hashing schemes
inferred← citeshttps://doi.org/10.3390/a15120448openalex-snapshot
A Multi-Dimensional Matrix Product—A Natural Tool for Parameterized Graph Algorithms
inferred← citeshttps://doi.org/10.3390/sym17122086openalex-snapshot
Symmetric Folding: An Efficient Method for Accelerating Witness-Based Random Search
inferred← citeshttps://doi.org/10.48550/arxiv.1307.2262openalex-snapshot
Approximate the k-Set Packing Problem by Local Improvements
inferred← citeshttps://doi.org/10.48550/arxiv.1307.6789openalex-snapshot
Optimal Top-k Document Retrieval
inferred← citeshttps://doi.org/10.48550/arxiv.1402.0054openalex-snapshot
Popular conjectures imply strong lower bounds for dynamic problems
inferred← citeshttps://doi.org/10.48550/arxiv.1412.2109openalex-snapshot
Algebrisation in Distributed Graph Algorithms: Fast Matrix Multiplication in the Congested Clique
inferred← citeshttps://doi.org/10.48550/arxiv.2011.04453openalex-snapshot
Improved List-Decodability of Reed--Solomon Codes via Tree Packings
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0008011openalex-snapshot
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0609009openalex-snapshot
Finding heaviest H-subgraphs in real weighted graphs, with applications
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0702159openalex-snapshot
Perfect Hashing for Data Management Applications
inferred← citeshttps://doi.org/10.5120/640-896openalex-snapshot
An Optimized All pair Shortest Paths Algorithm
inferred← citeshttps://doi.org/10.5555/1283383.1283488openalex-snapshot
All-pairs bottleneck paths in vertex weighted graphs
inferred← citeshttps://doi.org/10.5555/1496770.1496873openalex-snapshot
Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
inferred← citeshttps://doi.org/10.5555/2133036.2133150openalex-snapshot
Counting and detecting small subgraphs via equations and matrix multiplication
inferred← citeshttps://doi.org/10.5555/338219.338595openalex-snapshot
Faster deterministic dictionaries
inferred← citeshttps://doi.org/10.5555/365411.365535openalex-snapshot
New approaches to covering and packing problems
inferred← citeshttps://doi.org/10.5555/545381.545491openalex-snapshot
Roundtrip spanners and roundtrip routing in directed graphs
inferred← citeshttps://doi.org/10.7146/brics.v6i48.20118openalex-snapshot
Faster Deterministic Dictionaries
inferred← citeshttps://doi.org/10.7763/ijcee.2010.v2.263openalex-snapshot
An Efficient Algorithm for All Pair Shortest Paths
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.