Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amnon Ta-Shma:

TR17-041 | 6th March 2017
Amnon Ta-Shma

Explicit, almost optimal, epsilon-balanced codes

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

TR17-036 | 22nd February 2017
Dean Doron, Francois Le Gall, Amnon Ta-Shma

Probabilistic logarithmic-space algorithms for Laplacian solvers

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

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

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

TR16-120 | 1st August 2016
Dean Doron, Amir Sarid, Amnon Ta-Shma

On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revisions: 1

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

TR16-106 | 15th July 2016
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Low-error two-source extractors for polynomial min-entropy

Revisions: 1

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

TR16-088 | 1st June 2016
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Explicit two-source extractors for near-logarithmic min-entropy

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

TR13-155 | 10th November 2013
Gil Cohen, Amnon Ta-Shma

Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

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

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

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

TR10-047 | 23rd March 2010
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Local list decoding with a constant number of queries

Revisions: 1

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

TR06-108 | 24th August 2006
Dan Gutfreund, Amnon Ta-Shma

New connections between derandomization, worst-case complexity and average-case complexity

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

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

TR05-061 | 15th June 2005
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

On the Error Parameter of Dispersers

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

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

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

TR01-036 | 2nd May 2001
Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Extractors from Reed-Muller Codes

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

TR95-058 | 20th November 1995
Amnon Ta-Shma

On Extracting Randomness From Weak Random Sources

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

TR94-003 | 12th December 1994
Noam Nisan, Amnon Ta-Shma

Symmetric Logspace is Closed Under Complement

We present a Logspace, many-one reduction from the undirected
st-connectivity problem to its complement. This shows that

more >>>

ISSN 1433-8092 | Imprint