Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

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


TR25-077 | 18th June 2025
Dean Doron, Edward Pyne, Roei Tell, Ryan Williams

When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism

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


TR25-076 | 14th June 2025
Jan Seyfried, Sayantan Sen, Marco Tomamichel

Testing (Conditional) Mutual Information

We investigate the sample complexity of mutual information and conditional mutual information testing. For conditional mutual information testing, given access to independent samples of a triple of random variables $(A, B, C)$ with unknown distribution, we want to distinguish between two cases: (i) $A$ and $C$ are conditionally independent, i.e., ... more >>>



Next next


ISSN 1433-8092 | Imprint