Sasank Mouli

collaborators

2 papers

cs.LO2025

A Logspace Constructive Proof of L=SL

Sam Buss, Anant Dhayal, Valentine Kabanets +2

We formalize the proof of Reingold's Theorem that SL=L [Rei05] in the theory of bounded arithmetic VL, which corresponds to ``logspace reasoning''. As a consequence, we get that VL…

cs.CC2024

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable

Sasank Mouli

For every $n > 0$ , we show the existence of a CNF tautology over $O (n^{2})$ variables of width $O (lo g n)$ such that it has a Polynomial Calculus Resolution refutation over ${0, 1}$ …