Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-178 | 15th November 2025 00:53

A Logspace Constructive Proof of L=SL

RSS-Feed




TR25-178
Authors: Sam Buss, Anant Dhayal, Valentine Kabanets, Antonina Kolokolova, Sasank Mouli
Publication: 15th November 2025 00:54
Downloads: 65
Keywords: 


Abstract:

We formalize the proof of Reingold's Theorem that SL=L (STOC'05) in the theory of bounded arithmetic VL, which corresponds to ``logspace reasoning''. As a consequence, we get that VL=VSL, where VSL is the theory of bounded arithmetic for ``symmetric-logspace reasoning''. This resolves in the affirmative an old open question from Kolokolova's PhD thesis (2005) (see also Cook and Nguyen (2010)).

Our proof relies on the Rozenman-Vadhan alternative proof of Reingold's Theorem (RANDOM'05). To formalize this proof in VL, we need to avoid reasoning about eigenvalues and eigenvectors (common in both original proofs of SL=L). We achieve this by using some results from Buss-Kabanets-Kolokolova-Kouck\'y (APAL, 2020) that allow VL to reason about graph expansion in combinatorial terms.



ISSN 1433-8092 | Imprint