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

TR25-067 | 21st May 2025
Amnon Ta-Shma, ben chen

Better Weighted Pseudorandom Generators Against Low Weight Read-Once Branching Programs

In this work, we combine the work of Chen et. al and Hoza to obtain a WPRG against regular ROBPs
with seed length $O(\log t \cdot (\log w+\sqrt{\log \frac{1}{\epsilon}}+\log\log t) + \log \frac {1}{\epsilon})$, improving
upon previous construction which also include some additional lower order terms.

more >>>

TR25-066 | 21st May 2025
Shuichi Hirahara, Nobutaka Shimizu

An Optimal Error-Correcting Reduction for Matrix Multiplication

We present an optimal ``worst-case exact to average-case approximate'' reduction for matrix multiplication over a finite field of prime order $p$. Any efficient algorithm that correctly computes, in expectation, at least $(\frac{1}{p} + \varepsilon)$-fraction of entries of the multiplication $A \cdot B$ of a pair $(A, B)$ of uniformly ... more >>>


TR25-065 | 21st May 2025
Amnon Ta-Shma, ben chen

Simplyfing Armoni's PRG

We propose a simple variant of the INW pseudo-random generator, where blocks have varying lengths, and prove it gives the same parameters as the more complicated construction of Armoni's PRG. This shows there is no need for the specialized PRGs of Nisan and Zuckerman and Armoni, and they can be ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint