Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-150 | 7th November 2022
Aaron (Louie) Putterman, Edward Pyne

Near-Optimal Derandomization of Medium-Width Branching Programs

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space
$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$
In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.
Previously, ... more >>>


TR22-149 | 7th November 2022
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma

Approximating Iterated Multiplication of Stochastic Matrices in Small Space

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>


TR22-148 | 11th November 2022
Peter Ivanov, Raghu Meka, Emanuele Viola

Efficient resilient functions

An $n$-bit boolean function is resilient to coalitions of size $q$
if no fixed set of $q$ bits is likely to influence the value of the
function when the other $n-q$ bits are chosen uniformly at random,
even though the function is nearly balanced. We construct explicit
functions resilient to ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint