Expander Construction in VNC1

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

zbMATH Keywords

sequent calculusbounded arithmeticexpander graphsmonotone propositional logicalternating log time

Mathematics Subject Classification ID

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)

Expander Construction in VNC1 ⋮ Proof complexity of monotone branching programs

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