Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
DOI10.1137/22m1484134zbMath1528.05058OpenAlexW4388659218MaRDI QIDQ6089979
Benny Applebaum, Eliran Kachlon
Publication date: 15 December 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/22m1484134
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Linear codes (general theory) (94B05) Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Expander graphs (05C48)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cryptographic hardness of random local functions. Survey
- On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
- Explicit constructions of graphs without short cycles and low density codes
- Explicit Ramsey graphs and orthonormal labelings
- Secure arithmetic computation with constant computational overhead
- A note on negligible functions
- Randomness is linear in space
- Combinatorial batch codes
- Pseudorandomness and average-case complexity via uniform reductions
- Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes
- Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
- Public-key cryptography from different assumptions
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On Yao’s XOR-Lemma
- Expander codes
- Linear-time encodable and decodable error-correcting codes
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Modern Coding Theory
- Randomness conductors and constant-degree lossless expanders
- Batch codes and their applications
- Key agreement from weak bit agreement
- Foundations of Cryptography
- Improved low-density parity-check codes using irregular graphs
- Algebraic Attacks against Random Local Functions and Their Countermeasures
- Finite-length analysis of low-density parity-check codes on the binary erasure channel
- Hardness of approximating the minimum distance of a linear code
- Codes, Cryptology and Curves with Computer Algebra
- On the Implementation of Huge Random Objects
- Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
- On ε‐biased generators in NC0
- Theory of Cryptography
- Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation from Degree-5 Multilinear Maps
- Cryptography in $NC^0$
