Bravely, Moderately: A Common Theme in Four Recent Works

DOI10.1007/978-3-642-22670-0_26zbMath1343.68113OpenAlexW41461218MaRDI QIDQ3088192

Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_26

zbMATH Keywords

Markov chainsapproximationpermanentexpander graphsspace complexityPCPlog-spaceNPundirected connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Ramanujan graphs
• Eigenvalues and expanders
• Explicit constructions of linear-sized superconcentrators
• Pseudorandom generators for space-bounded computation
• \(\text{RL}\subseteq \text{SC}\)
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Randomness is linear in space
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Proof verification and the hardness of approximation problems
• Approximating the Permanent
• Simple PCPs with poly-log rate and query complexity
• Undirected ST-connectivity in log-space
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• The PCP theorem by gap amplification
• Computational Complexity
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents