In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM 2018). Our results extend the works of Forbes, Shpilka, Tzameret, and Wigderson (Theory of Computing 2021) ... more >>>

Williams (STOC 2025) recently proved that time-$t$ multitape Turing machines can be simulated using $O(\sqrt{t \log t})$ space using the Cook-Mertz (STOC 2024) tree evaluation procedure. As Williams notes, applying this result to fast algorithms for the circuit value problem implies an $O(\sqrt{s} \cdot \mathrm{polylog}\; s)$ space algorithm for evaluating ... more >>>

Two fundamental problems on directed graphs are to decide $s$-$t$ connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for $s$-$t$ connectivity running in polynomial time and $n^{o(1)}$ space, and no known algorithm for estimating the $n$-step random walk matrix running in non-deterministic logspace. ... more >>>