Expander Construction in VNC1
From MaRDI portal
Publication:4638081
DOI10.4230/LIPIcs.ITCS.2017.31zbMath1402.03081OpenAlexW2771071550MaRDI QIDQ4638081
Valentine Kabanets, Antonina Kolokolova, Michal Koucký, Samuel R. Buss
Publication date: 3 May 2018
Full work available at URL: https://dblp.uni-trier.de/db/conf/innovations/innovations2017.html#BussKKK17
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved sorting networks with O(log N) depth
- On theories of bounded arithmetic for \(\mathrm{NC}^1\)
- A sorting network in bounded arithmetic
- Substitution Frege and extended Frege proof systems in non-classical logics
- Sorting networks of logarithmic depth, further simplified
- Explicit construction of linear sized tolerant networks
- Ramanujan graphs
- On uniform circuit complexity
- Explicit constructions of linear-sized superconcentrators
- Bounded arithmetic for NC, ALogTIME, L and NL
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Monotone simulations of non-monotone proofs.
- A bounded arithmetic AID for Frege systems
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Monotone Proofs of the Pigeon Hole Principle
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Approximate counting by hashing in bounded arithmetic
- Expander graphs and their applications
- An Elementary Construction of Constant-Degree Expanders
- Undirected connectivity in log-space
- Polynomial size proofs of the propositional pigeonhole principle
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Random Cayley graphs and expanders
- Expander Construction in VNC1
- Approximate counting in bounded arithmetic
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- A new proof of the weak pigeonhole principle
- The PCP theorem by gap amplification
This page was built for publication: Expander Construction in VNC1