Dean Doron

According to our database, Dean Doron authored at least 38 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Small-Space Spectral Sparsification via Bounded-Independence Sampling.

Dean Doron, Jack Murtagh, Salil P. Vadhan, David Zuckerman

ACM Trans. Comput. Theory, 2024

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?

Dean Doron, Jonathan Mosheiff, Mary Wootters

Electron. Colloquium Comput. Complex., 2024

Online Condensing of Unpredictable Sources via Random Walks.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Electron. Colloquium Comput. Complex., 2024

Implications of Better PRGs for Permutation Branching Programs.

Dean Doron, William Hoza

Electron. Colloquium Comput. Complex., 2024

Binary Codes with Distance Close to Half.

Dean Doron

Electron. Colloquium Comput. Complex., 2024

Nearly-Linear Time Seeded Extractors with Short Seeds.

Dean Doron, João Ribeiro

Electron. Colloquium Comput. Complex., 2024

A Study of Error Reduction Polynomials.

Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz

Electron. Colloquium Comput. Complex., 2024

Nearly-Linear Time Seeded Extractors with Short Seeds.

Dean Doron, João Ribeiro

CoRR, 2024

2023

Derandomization with Minimal Memory Footprint.

Dean Doron, Roei Tell

Electron. Colloquium Comput. Complex., 2023

Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL.

Dean Doron, Edward Pyne, Roei Tell

Electron. Colloquium Comput. Complex., 2023

2022

An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy.

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

SIAM J. Comput., 2022

Almost Chor-Goldreich Sources and Adversarial Random Walks.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Electron. Colloquium Comput. Complex., 2022

Approximating Iterated Multiplication of Stochastic Matrices in Small Space.

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

Electron. Colloquium Comput. Complex., 2022

Approximating Large Powers of Stochastic Matrices in Small Space.

Gil Cohen, Dean Doron, Ori Sberlo

Electron. Colloquium Comput. Complex., 2022

New Near-Linear Time Decodable Codes Closer to the GV Bound.

Guy Blanc, Dean Doron

Electron. Colloquium Comput. Complex., 2022

On Hitting-Set Generators for Polynomials that Vanish Rarely.

Dean Doron, Amnon Ta-Shma, Roei Tell

Comput. Complex., 2022

2021

Monotone Branching Programs: Pseudorandomness and Circuit Complexity.

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

Electron. Colloquium Comput. Complex., 2021

Error Reduction For Weighted PRGs Against Read Once Branching Programs.

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

Electron. Colloquium Comput. Complex., 2021

Pseudorandom Generators for Read-Once Monotone Branching Programs.

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

Proceedings of the Approximation, 2021

2020

High-Probability List-Recovery, and Applications to Heavy Hitters.

Dean Doron, Mary Wootters

Electron. Colloquium Comput. Complex., 2020

Spectral Sparsification via Bounded-Independence Sampling.

Dean Doron, Jack Murtagh, Salil P. Vadhan, David Zuckerman

Electron. Colloquium Comput. Complex., 2020

Seed Protecting Extractors.

Gil Cohen, Dean Doron, Shahar Samocha

Electron. Colloquium Comput. Complex., 2020

Near-Optimal Erasure List-Decodable Codes.

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

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Nearly Optimal Pseudorandomness From Hardness.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Electron. Colloquium Comput. Complex., 2019

Log-Seed Pseudorandom Generators via Iterated Restrictions.

Dean Doron, Pooya Hatami, William Hoza

Electron. Colloquium Comput. Complex., 2019

2018

Randomness Extractors and Space-Bounded Computation

Dean Doron

PhD thesis, 2018

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

Dean Doron, Pooya Hatami, William Hoza

Electron. Colloquium Comput. Complex., 2018

Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends.

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

Electron. Colloquium Comput. Complex., 2018

Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions.

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

Electron. Colloquium Comput. Complex., 2018

A New Approach for Constructing Low-Error, Two-Source Extractors.

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

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Probabilistic logarithmic-space algorithms for Laplacian solvers.

Dean Doron, Francois Le Gall, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2017

A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate.

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

Electron. Colloquium Comput. Complex., 2017

On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace.

Dean Doron, Amir Sarid, Amnon Ta-Shma

Comput. Complex., 2017

An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy.

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

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

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

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

Electron. Colloquium Comput. Complex., 2016

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

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

Electron. Colloquium Comput. Complex., 2016

2015

On the de-randomization of space-bounded approximate counting problems.

Dean Doron, Amnon Ta-Shma

Inf. Process. Lett., 2015

On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace.

Dean Doron, Amnon Ta-Shma

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015