Bravely, Moderately: A Common Theme in Four Recent Works
From MaRDI portal
Publication:3088192
DOI10.1007/978-3-642-22670-0_26zbMath1343.68113OpenAlexW41461218MaRDI QIDQ3088192
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
Markov chainsapproximationpermanentexpander graphsspace complexityPCPlog-spaceNPundirected connectivity
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
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