Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YAKOV SHALUNOV:
All reports by Author Yakov Shalunov:

TR25-078 | 20th June 2025
Yakov Shalunov

Improved Bounds on the Space Complexity of Circuit Evaluation

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




ISSN 1433-8092 | Imprint