All reports by Author Amnon Ta-Shma:

__
TR20-163
| 5th November 2020
__

Gil Cohen, Noam Peri, Amnon Ta-Shma#### Expander Random Walks: A Fourier-Analytic Approach

__
TR19-119
| 9th September 2019
__

Dean Doron, Amnon Ta-Shma, Roei Tell#### On Hitting-Set Generators for Polynomials that Vanish Rarely

Revisions: 1

__
TR18-066
| 8th April 2018
__

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma#### Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

__
TR18-065
| 8th April 2018
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

Revisions: 1

__
TR17-041
| 6th March 2017
__

Amnon Ta-Shma#### Explicit, almost optimal, epsilon-balanced codes

__
TR17-036
| 22nd February 2017
__

Dean Doron, Francois Le Gall, Amnon Ta-Shma#### Probabilistic logarithmic-space algorithms for Laplacian solvers

__
TR17-027
| 16th February 2017
__

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma#### A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate

Revisions: 1

__
TR16-120
| 1st August 2016
__

Dean Doron, Amir Sarid, Amnon Ta-Shma#### On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revisions: 1

__
TR16-106
| 15th July 2016
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Low-error two-source extractors for polynomial min-entropy

Revisions: 1

__
TR16-088
| 1st June 2016
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Explicit two-source extractors for near-logarithmic min-entropy

__
TR13-155
| 10th November 2013
__

Gil Cohen, Amnon Ta-Shma#### Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

__
TR10-134
| 23rd August 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

Revisions: 2

__
TR10-047
| 23rd March 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### Local list decoding with a constant number of queries

Revisions: 1

__
TR06-108
| 24th August 2006
__

Dan Gutfreund, Amnon Ta-Shma#### New connections between derandomization, worst-case complexity and average-case complexity

__
TR05-061
| 15th June 2005
__

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma#### On the Error Parameter of Dispersers

__
TR04-069
| 13th August 2004
__

Eran Rom, Amnon Ta-Shma#### Improving the alphabet size in high noise, almost optimal rate list decodable codes

Revisions: 2

__
TR01-036
| 2nd May 2001
__

Amnon Ta-Shma, David Zuckerman, Shmuel Safra#### Extractors from Reed-Muller Codes

__
TR95-058
| 20th November 1995
__

Amnon Ta-Shma#### On Extracting Randomness From Weak Random Sources

__
TR94-003
| 12th December 1994
__

Noam Nisan, Amnon Ta-Shma#### Symmetric Logspace is Closed Under Complement

Gil Cohen, Noam Peri, Amnon Ta-Shma

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>

Dean Doron, Amnon Ta-Shma, Roei Tell

We study the following question: Is it easier to construct a hitting-set generator for polynomials $p:\mathbb{F}^n\rightarrow\mathbb{F}$ of degree $d$ if we are guaranteed that the polynomial vanishes on at most an $\epsilon>0$ fraction of its inputs? We will specifically be interested in tiny values of $\epsilon\ll d/|\mathbb{F}|$. This question was ... more >>>

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,

the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.

Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ...
more >>>

Amnon Ta-Shma

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1-\epsilon}{2}$ and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an ... more >>>

Dean Doron, Francois Le Gall, Amnon Ta-Shma

A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system $L x=b$, where $L$ is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem.

more >>>

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

We show a reduction from the existence of explicit t-non-malleable

extractors with a small seed length, to the construction of explicit

two-source extractors with small error for sources with arbitrarily

small constant rate. Previously, such a reduction was known either

when one source had entropy rate above half [Raz05] or ...
more >>>

Dean Doron, Amir Sarid, Amnon Ta-Shma

Approximating the eigenvalues of a Hermitian operator can be solved

by a quantum logspace algorithm. We introduce the problem of

approximating the eigenvalues of a given matrix in the context of

classical space-bounded computation. We show that:

- Approximating the second eigenvalue of stochastic operators (in a

certain range of ...
more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

We construct explicit two-source extractors for $n$ bit sources,

requiring $n^\alpha$ min-entropy and having error $2^{-n^\beta}$,

for some constants $0 < \alpha,\beta < 1$. Previously, constructions

for exponentially small error required either min-entropy

$0.49n$ \cite{Bou05} or three sources \cite{Li15}. The construction

combines somewhere-random condensers based on the Incidence

Theorem \cite{Zuc06,Li11}, ...
more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

We explicitly construct extractors for two independent $n$-bit sources of $(\log n)^{1+o(1)}$ min-entropy. Previous constructions required either $\mathrm{polylog}(n)$ min-entropy \cite{CZ15,Meka15} or five sources \cite{Cohen16}.

Our result extends the breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} and uses the non-malleable extractor of Cohen \cite{Cohen16}. The main new ingredient in our construction ... more >>>

Gil Cohen, Amnon Ta-Shma

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.

Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors

to a locally decodable code that can recover from a much higher error-rate. We also show how to ...
more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Recently Efremenko showed locally-decodable codes of sub-exponential

length. That result showed that these codes can handle up to

$\frac{1}{3} $ fraction of errors. In this paper we show that the

same codes can be locally unique-decoded from error rate

$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from

error rate $1-\alpha$ ...
more >>>

Dan Gutfreund, Amnon Ta-Shma

We show that a mild derandomization assumption together with the

worst-case hardness of NP implies the average-case hardness of a

language in non-deterministic quasi-polynomial time. Previously such

connections were only known for high classes such as EXP and

PSPACE.

There has been a long line of research trying to explain ... more >>>

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

Optimal dispersers have better dependence on the error than

optimal extractors. In this paper we give explicit disperser

constructions that beat the best possible extractors in some

parameters. Our constructions are not strong, but we show that

having such explicit strong constructions implies a solution

to the Ramsey graph construction ...
more >>>

Eran Rom, Amnon Ta-Shma

In this note we revisit the construction of high noise, almost

optimal rate list decodable code of Guruswami ("Better extractors for better codes?")

Guruswami showed that based on optimal extractors one can build a

$(1-\epsilon,O({1 \over \epsilon}))$ list decodable codes of rate

$\Omega({\epsilon \over {log{1 \over \epsilon}}})$ and alphabet

size ...
more >>>

Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, ... more >>>

Amnon Ta-Shma

We deal with the problem of extracting as much randomness as possible

from a defective random source.

We devise a new tool, a ``merger'', which is a function that accepts

d strings, one of which is uniformly distributed,

and outputs a single string that is guaranteed ...
more >>>

Noam Nisan, Amnon Ta-Shma

We present a Logspace, many-one reduction from the undirected

st-connectivity problem to its complement. This shows that

$SL=co-SL$