Expander construction in VNC1

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

Abstract

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].

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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 - 2017 - Philosophy and Phenomenological Research 97 (2):393-409.
Three Kinds of Niche Construction.Bendik Hellem Aaby & Grant Ramsey - 2022 - British Journal for the Philosophy of Science 73 (2):351-372.
Social Construction.Ásta Sveinsdóttir - 2015 - Philosophy Compass 10 (12):884-892.
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.

Analytics

Added to PP
2020-03-20

Downloads
13 (#886,512)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
On theories of bounded arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.

View all 9 references / Add more references