All reports by Author Dean Doron:

__
TR23-208
| 21st December 2023
__

Dean Doron, Edward Pyne, Roei Tell#### Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL

__
TR23-036
| 27th March 2023
__

Dean Doron, Roei Tell#### Derandomization with Minimal Memory Footprint

__
TR22-149
| 7th November 2022
__

Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma#### Approximating Iterated Multiplication of Stochastic Matrices in Small Space

__
TR22-103
| 15th July 2022
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 2

__
TR22-027
| 22nd February 2022
__

Guy Blanc, Dean Doron#### New Near-Linear Time Decodable Codes Closer to the GV Bound

Revisions: 1

__
TR22-008
| 14th January 2022
__

Gil Cohen, Dean Doron, Ori Sberlo#### Approximating Large Powers of Stochastic Matrices in Small Space

Comments: 1

__
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

__
TR21-018
| 20th February 2021
__

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

Revisions: 1

__
TR20-162
| 7th November 2020
__

Dean Doron, Mary Wootters#### High-Probability List-Recovery, and Applications to Heavy Hitters

Revisions: 3

__
TR20-161
| 5th November 2020
__

Gil Cohen, Dean Doron, Shahar Samocha#### Seed Protecting Extractors

__
TR20-026
| 25th February 2020
__

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman#### Spectral Sparsification via Bounded-Independence Sampling

Revisions: 1

__
TR19-149
| 4th November 2019
__

Dean Doron, Pooya Hatami, William Hoza#### Log-Seed Pseudorandom Generators via Iterated Restrictions

__
TR19-119
| 9th September 2019
__

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

Revisions: 1

__
TR19-099
| 29th July 2019
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

__
TR18-183
| 5th November 2018
__

Dean Doron, Pooya Hatami, William Hoza#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

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

Dean Doron, Edward Pyne, Roei Tell

We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation.

Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. ... more >>>

Dean Doron, Roei Tell

Existing proofs that deduce BPL=L from circuit lower bounds convert randomized algorithms into deterministic algorithms with large constant overhead in space. We study space-bounded derandomization with minimal footprint, and ask what is the minimal possible space overhead for derandomization.

We show that $BPSPACE[S] \subseteq DSPACE[c \cdot S]$ for $c \approx ...
more >>>

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

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>

Guy Blanc, Dean Doron

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... more >>>

Gil Cohen, Dean Doron, Ori Sberlo

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... 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 >>>

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

Dean Doron, Mary Wootters

An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j ... more >>>

Gil Cohen, Dean Doron, Shahar Samocha

We introduce a new type of seeded extractors we dub seed protecting extractors. Informally, a seeded extractor is seed protecting against a class of functions $C$, mappings seeds to seeds, if the seed $Y$ remains close to uniform even after observing the output $\mathrm{Ext}(X,A(Y))$ for every choice of $A \in ... more >>>

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

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

Dean Doron, Pooya Hatami, William Hoza

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

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

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

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

Dean Doron, Pooya Hatami, William Hoza

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

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

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