Sam Buss, Valentine Kabanets, Antonina Kolokolova
and Michal Koucký
"Expander Construction in VNC1"
Full-length preprint, September 2016 (revised February 2017).
Extended abstract, in Proceedings, 8th Conference on Innovations in Computer Science (ITCS), 2017.
We give a combinatorial analysis (using edge expansion) of a
variant of the
iterative expander construction due to Reingold, Vadhan, and
Wigderson , and show that this analysis can be formalized in
the bounded-arithmetic system VNC1
(corresponding to the "NC
To appear in
in Proceedings, 8th Conference on Innovations in Computer Science
Related talk at
Prague Workshop on Bounded Arithmetic, November 2, 2017.
Back to Sam Buss's publications page.