Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Dean Doron:

TR20-026 | 25th February 2020
Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

Spectral Sparsification via Bounded-Independence Sampling

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$ and an error parameter $\varepsilon > 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>>

TR19-149 | 4th November 2019
Dean Doron, Pooya Hatami, William Hoza

Log-Seed Pseudorandom Generators via Iterated Restrictions

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The ``iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length $\mathrm{polylog} n$ or even $\tilde{O}(\log n)$ for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>>

TR19-119 | 9th September 2019
Dean Doron, Amnon Ta-Shma, Roei Tell

On Hitting-Set Generators for Polynomials that Vanish Rarely

Revisions: 1

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

TR19-099 | 29th July 2019
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Nearly Optimal Pseudorandomness From Hardness

Revisions: 1

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

TR18-183 | 5th November 2018
Dean Doron, Pooya Hatami, William Hoza

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

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

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

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

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

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

ISSN 1433-8092 | Imprint