Dean Doron

According to our database, Dean Doron authored at least 40 papers between 2015 and 2025.

Collaborative distances:

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

2025

When Connectivity Is Hard, Random Walks Are Easy with Non-determinism.

Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Online Condensing of Unpredictable Sources via Random Walks.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Proceedings of the 40th Computational Complexity Conference, 2025

List-Recovery of Random Linear Codes over Small Fields.

Dean Doron, Jonathan Mosheiff, Nicolas Resch, João Ribeiro

Proceedings of the Approximation, 2025

Implications of Better PRGs for Permutation Branching Programs.

Dean Doron, William M. Hoza

Proceedings of the Approximation, 2025

Bit-Fixing Extractors for Almost-Logarithmic Entropy.

Dean Doron, Ori Fridman

Proceedings of the Approximation, 2025

2024

Small-Space Spectral Sparsification via Bounded-Independence Sampling.

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

ACM Trans. Comput. Theory, 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

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

Dean Doron, Edward Pyne, Roei Tell

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

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

Dean Doron, Jonathan Mosheiff, Mary Wootters

Proceedings of the Approximation, 2024

2023

Almost Chor-Goldreich Sources and Adversarial Random Walks.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Approximating Iterated Multiplication of Stochastic Matrices in Small Space.

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

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Derandomization with Minimal Memory Footprint.

Dean Doron, Roei Tell

Proceedings of the 38th Computational Complexity Conference, 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

Approximating Large Powers of Stochastic Matrices in Small Space.

Gil Cohen, Dean Doron, Ori Sberlo

Electron. Colloquium Comput. Complex., 2022

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

Dean Doron, Mary Wootters

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

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

Guy Blanc, Dean Doron

Proceedings of the 37th Computational Complexity Conference, 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

Proceedings of the 36th Computational Complexity Conference, 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

Seed Protecting Extractors.

Gil Cohen, Dean Doron, Shahar Samocha

Electron. Colloquium Comput. Complex., 2020

Spectral Sparsification via Bounded-Independence Sampling.

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

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Nearly Optimal Pseudorandomness From Hardness.

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Log-Seed Pseudorandom Generators via Iterated Restrictions.

Dean Doron, Pooya Hatami, William M. Hoza

Proceedings of the 35th Computational Complexity Conference, 2020

Near-Optimal Erasure List-Decodable Codes.

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

Proceedings of the 35th Computational Complexity Conference, 2020

On Hitting-Set Generators for Polynomials That Vanish Rarely.

Dean Doron, Amnon Ta-Shma, Roei Tell

Proceedings of the Approximation, 2020

2019

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

Dean Doron, Pooya Hatami, William M. Hoza

Proceedings of the 34th Computational Complexity Conference, 2019

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

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

Proceedings of the Approximation, 2019

2018

Randomness Extractors and Space-Bounded Computation

Dean Doron

PhD thesis, 2018

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

Avraham Ben-Aroya, 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

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

Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers.

Dean Doron, François Le Gall, Amnon Ta-Shma

Proceedings of the Approximation, 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