Randomness conductors and constant-degree lossless expanders

DOI10.1145/509907.510003zbMath1192.68475OpenAlexW2148180254MaRDI QIDQ3579250

Avi Wigderson, Michael Capalbo, Omer Reingold, Salil P. Vadhan

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.510003

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Related Items (40)

A new formula for the minimum distance of an expander code ⋮ Expander-based cryptography meets natural proofs ⋮ Partition expanders ⋮ Quantum Locally Testable Codes ⋮ Local expanders ⋮ Deterministic multi-channel information exchange ⋮ Expander \(\ell_0\)-decoding ⋮ Locally computable UOWHF with linear shrinkage ⋮ Improved constructions for non-adaptive threshold group testing ⋮ Low-degree test with polynomially small error ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Deterministic dynamic matching in worst-case update time ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Simple Codes and Sparse Recovery with Fast Decoding ⋮ An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs ⋮ Orion: zero knowledge proof with linear prover time ⋮ How to recover a secret with \(O(n)\) additions ⋮ Expander graphs and their applications ⋮ The complexity of inverting explicit Goldreich's function by DPLL algorithms ⋮ Meeting the deadline: on the complexity of fault-tolerant continuous gossip ⋮ The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms ⋮ An Introduction to Randomness Extractors ⋮ Symmetric LDPC codes and local testing ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Rainbow paths ⋮ Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack ⋮ Symmetric LDPC Codes and Local Testing ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ Minimal selectors and fault tolerant networks ⋮ A generalized Alon-Boppana bound and weak Ramanujan graphs ⋮ Optimal deterministic group testing algorithms to estimate the number of defectives ⋮ Key Agreement from Close Secrets over Unsecured Channels ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ Rate-1, Linear Time and Additively Homomorphic UC Commitments ⋮ Better short-seed quantum-proof extractors ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Certifiably Pseudorandom Financial Derivatives ⋮ Nonlinear approximation spaces for inverse problems

This page was built for publication: Randomness conductors and constant-degree lossless expanders