All reports by Author Amnon Ta-Shma:

__
TR21-091
| 29th June 2021
__

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma#### Expander Random Walks: The General Case and Limitations

__
TR21-020
| 15th February 2021
__

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma#### Error Reduction For Weighted PRGs Against Read Once Branching Programs

__
TR20-059
| 16th April 2020
__

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma#### Pr-ZSUBEXP is not contained in Pr-RP

Revisions: 1

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, ... more >>>

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and ... more >>>

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.

The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ...
more >>>