Sam Buss, Valentine Kabanets, Antonina Kolokolova
and Michal Koucký
"Expander Construction in VNC1"
Annals of Pure and Applied Logic 107, 7 (2020) Article 102796 (40 pages).
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
In Proceedings, 8th Conference on Innovations in Computer Science
Related talk at
Takeuti Symposium on Advances in Logic, September 20, 2018.
Back to Sam Buss's publications page.