Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VL AND VSL:
Reports tagged with VL and VSL:
TR25-178 | 15th November 2025
Sam Buss, Anant Dhayal, Valentine Kabanets, Antonina Kolokolova, Sasank Mouli

A Logspace Constructive Proof of L=SL

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




ISSN 1433-8092 | Imprint