Expander construction in VNC1

Annals of Pure and Applied Logic 171 (7):102796 (2020)

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the “NC^1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC^1 . This in turn implies that every proof in Gentzen's sequent calculus LK of a monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlák [9].
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2020.102796
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 49,066
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

A Sorting Network in Bounded Arithmetic.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):341-355.
From N to N: The Anatomy of a Construction. [REVIEW]Joost Zwarts - 2013 - Linguistics and Philosophy 36 (1):65-90.
Niche Construction: A Pervasive Force in Evolution?Wim J. van der Steen - 2000 - Behavioral and Brain Sciences 23 (1):162-163.
Social Construction and Grounding.Aaron M. Griffith - 2018 - Philosophy and Phenomenological Research 97 (2):393-409.
Three Kinds of Niche Construction.Bendik Hellem Aaby & Grant Ramsey - forthcoming - British Journal for the Philosophy of Science.
Social Construction.Ásta Sveinsdóttir - 2015 - Philosophy Compass 10 (12):884-892.
Social Construction: Big-G Grounding, Small-G Realization.Aaron Griffith - 2018 - Philosophical Studies 175 (1):241-260.
This Is So NP!Elizaveta Bylinina - 2011 - The Baltic International Yearbook of Cognition, Logic and Communication 6.
The Functions of Affect in the Construction of Preferences.Ellen Peters - 2006 - In Sarah Lichtenstein & Paul Slovic (eds.), The Construction of Preference. Cambridge University Press. pp. 454--463.


Added to PP index

Total views
5 ( #1,085,572 of 2,311,214 )

Recent downloads (6 months)
5 ( #201,969 of 2,311,214 )

How can I increase my downloads?


My notes

Sign in to use this feature