Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
DOI10.1137/22M1484134zbMATH Open1528.05058OpenAlexW4388659218MaRDI QIDQ6089979FDOQ6089979
Authors: 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
Recommendations
- Uniform generation of spanning regular subgraphs of a dense graph
- Randomness-Efficient Sampling Within NC 1
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Randomness-efficient sampling within NC\(^{1}\)
Random graphs (graph-theoretic aspects) (05C80) Data encryption (aspects in computer science) (68P25) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear codes (general theory) (94B05) Expander graphs (05C48)
Cites Work
- Expander codes
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Title not available (Why is that?)
- Codes, cryptology and curves with computer algebra
- Explicit constructions of graphs without short cycles and low density codes
- A note on negligible functions
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Linear-time encodable and decodable error-correcting codes
- Foundations of Cryptography
- Hardness of approximating the minimum distance of a linear code
- Pseudorandomness and average-case complexity via uniform reductions
- Title not available (Why is that?)
- Randomness is linear in space
- Public-key cryptography from different assumptions
- Cryptography with constant computational overhead
- Improved low-density parity-check codes using irregular graphs
- Pseudorandom generators with long stretch and low locality from random local one-way functions
- On ε‐biased generators in NC0
- Cryptography in $NC^0$
- On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
- Cryptographic hardness of random local functions. Survey
- Key agreement from weak bit agreement
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
- On Yao's XOR-lemma
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
- Randomness conductors and constant-degree lossless expanders
- Explicit Ramsey graphs and orthonormal labelings
- Modern Coding Theory
- Finite-length analysis of low-density parity-check codes on the binary erasure channel
- On the implementation of huge random objects
- Combinatorial batch codes
- Batch codes and their applications
- Secure arithmetic computation with constant computational overhead
- Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps
- Indistinguishability obfuscation from constant-degree graded encoding schemes
- Low-complexity cryptographic hash functions
- Algebraic attacks against random local functions and their countermeasures
- Efficiency improvements in constructing pseudorandom generators from one-way functions
- Theory of Cryptography
Cited In (2)
This page was built for publication: Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089979)
