David Zuckerman

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

Near-Optimal Averaging Samplers and Matrix Samplers.

[BibT_eX]

[DOI]

Zhiyang Xun

Proceedings of the 40th Computational Complexity Conference, 2025

Online Condensing of Unpredictable Sources via Random Walks.

[BibT_eX]

[DOI]

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Small-Space Spectral Sparsification via Bounded-Independence Sampling.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2024

Near-Optimal Averaging Samplers.

[BibT_eX]

[DOI]

Zhiyang Xun

Electron. Colloquium Comput. Complex., 2024

Improved Condensers for Chor-Goldreich Sources.

[BibT_eX]

[DOI]

Jesse Goodman

Xin Li

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Extractors for Images of Varieties.

[BibT_eX]

[DOI]

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

Almost Chor-Goldreich Sources and Adversarial Random Walks.

[BibT_eX]

[DOI]

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

2022

The Space Complexity of Sampling.

[BibT_eX]

[DOI]

Jesse Goodman

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2020

Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing.

[BibT_eX]

[DOI]

Ashutosh Kumar

Electron. Colloquium Comput. Complex., 2020

XOR lemmas for resilient functions against polynomials.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Spectral Sparsification via Bounded-Independence Sampling.

[BibT_eX]

[DOI]

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

Randomness Efficient Noise Stability and Generalized Small Bias Sets.

[BibT_eX]

[DOI]

Dana Moshkovitz

Justin Oh

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Nearly Optimal Pseudorandomness From Hardness.

[BibT_eX]

[DOI]

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

Extractors and Secret Sharing Against Bounded Collusion Protocols.

[BibT_eX]

[DOI]

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

2019

Certifiably Pseudorandom Financial Derivatives.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Improved Extractors for Recognizable and Algebraic Sources.

[BibT_eX]

[DOI]

Fu Li

Proceedings of the Approximation, 2019

2018

Existence of Simple Extractors.

[BibT_eX]

[DOI]

Xue Chen

Electron. Colloquium Comput. Complex., 2018

Simple Optimal Hitting Sets for Small-Success RL.

[BibT_eX]

[DOI]

William Hoza

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2016

Bitcoin Beacon.

[BibT_eX]

[DOI]

Iddo Bentov

Ariel Gabizon

CoRR, 2016

Special issue "Computational Complexity Conference 2015" Guest Editors' Foreword.

[BibT_eX]

[DOI]

Zeev Dvir

Comput. Complex., 2016

Explicit two-source extractors and resilient functions.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Robust Fourier and Polynomial Curve Fitting.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

New Extractors for Interleaved Sources.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Rectangles Are Nonnegative Juntas.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Deterministic Extractors for Additive Sources: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

Privacy Amplification and Nonmalleable Extractors Via Character Sums.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Deterministic Extractors for Additive Sources.

[BibT_eX]

[DOI]

CoRR, 2014

On Low Discrepancy Samplings in Product Spaces of Motion Groups.

[BibT_eX]

[DOI]

CoRR, 2014

Non-malleable Codes against Constant Split-State Tampering.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Mining Circuit Lower Bound Proofs for Meta-algorithms.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Robust Pseudorandom Generators.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Pseudorandomness from Shrinkage.

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Non-malleable extractors via character sums

[BibT_eX]

[DOI]

Trevor D. Wooley

CoRR, 2011

Pseudorandom generators for combinatorial shapes.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Pseudorandom financial derivatives.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Privacy Amplification and Non-malleable Extractors via Character Sums.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More).

[BibT_eX]

[DOI]

Oded Goldreich

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010

Can Random Coin Flips Speed Up a Computer?

[BibT_eX]

[DOI]

CoRR, 2010

Pseudorandom generators for polynomial threshold functions.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Optimal Testing of Reed-Muller Codes.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Optimal Testing of Reed-Muller Codes.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Fooling Functions of Halfspaces under Product Distributions.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Small-Bias Spaces for Group Products.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

List-decoding reed-muller codes over small fields.

[BibT_eX]

[DOI]

Parikshit Gopalan

Adam R. Klivans

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Network Extractor Protocols.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Extractors for Three Uneven-Length Sources.

[BibT_eX]

[DOI]

Anup Rao

Proceedings of the Approximation, 2008

2007

Interaction in Quantum Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2007

Lossless Condensers, Unbalanced Expanders, And Extractors.

[BibT_eX]

[DOI]

Christopher Umans

Comb., 2007

2006

Linear degree extractors and the inapproximability of max clique and chromatic number.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Deterministic extractors for small-space sources.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Random Selection with an Adversarial Majority.

[BibT_eX]

[DOI]

Ronen Gradwohl

Salil P. Vadhan

Proceedings of the Advances in Cryptology, 2006

2004

Testing Low-Degree Polynomials over Prime Fields.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

Compression of Samplable Sources.

[BibT_eX]

[DOI]

Luca Trevisan

Salil P. Vadhan

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography.

[BibT_eX]

[DOI]

Jesse Kamp

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

2002

Combinatorial bounds for list decoding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2002

Expander Graphs for Digital Stream Authentication and Robust Overlay Networks.

[BibT_eX]

[DOI]

Dawn Xiaodong Song

J. D. Tygar

Proceedings of the 2002 IEEE Symposium on Security and Privacy, 2002

2001

Perfect Information Leader Election in log* n+O (1) Rounds.

[BibT_eX]

[DOI]

Alexander Russell

J. Comput. Syst. Sci., 2001

Extractor codes.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Loss-less condensers, unbalanced expanders, and extractors.

[BibT_eX]

[DOI]

Christopher Umans

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Interaction in quantum communication and the complexity of set disjointness.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Extractors from Reed-Muller Codes.

[BibT_eX]

[DOI]

Shmuel Safra

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Interaction in Quantum Communication Complexity

[BibT_eX]

[DOI]

Ashwin Nayak

CoRR, 2000

1999

Asymptotically good codes correcting insertions, deletions, and transpositions.

[BibT_eX]

[DOI]

Leonard J. Schulman

IEEE Trans. Inf. Theory, 1999

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.

[BibT_eX]

[DOI]

Alexander Russell

Michael E. Saks

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

1998

Extractors for Weak Random Sources and Their Applications.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1998

Perfect Information Leader Election in log*n + O(1) Rounds.

[BibT_eX]

[DOI]

Alexander Russell

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Randomness-optimal oblivious sampling.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1997

Another proof that BPP subseteq PH (and more).

[BibT_eX]

[DOI]

Oded Goldreich

Electron. Colloquium Comput. Complex., 1997

Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (Preliminary Version).

[BibT_eX]

[DOI]

Leonard J. Schulman

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

On Unapproximable Versions of NP-Complete Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Multiple cover time.

[BibT_eX]

[DOI]

Peter Winkler

Random Struct. Algorithms, 1996

Randomness is Linear in Space.

[BibT_eX]

[DOI]

Noam Nisan

J. Comput. Syst. Sci., 1996

Randomness-Optimal Sampling, Extractors, and Constructive Leader Election.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

Derandomized Graph Products.

[BibT_eX]

[DOI]

Comput. Complex., 1995

Tight analyses of two local load balancing algorithms.

[BibT_eX]

[DOI]

Bhaskar Ghosh

Frank Thomson Leighton

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1994

Computing with Very Weak Random Sources

[BibT_eX]

[DOI]

Aravind Srinivasan

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Expanders that beat the eigenvalue bound: explicit construction and applications.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

More deterministic simulation in logspace.

[BibT_eX]

[DOI]

Noam Nisan

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Efficient construction of a small hitting set for combinatorial rectangles in high dimension.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Lower bounds for randomized mutual exclusion.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Optimal Speedup of Las Vegas Algorithms.

[BibT_eX]

[DOI]

Michael Luby

Alistair Sinclair

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

NP-Complete Problems Have a Version That's Hard to Approximate.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1991

On the Time to Traverse all Edges of a Graph.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1991

Simulating BPP Using a General Weak Random Source

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

A Technique for Lower Bounding the Cover Time

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

General Weak Random Sources

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Security Preserving Amplification of Hardness

[BibT_eX]

[DOI]

Oded Goldreich

Russell Impagliazzo

Leonid A. Levin

Ramarathnam Venkatesan

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

How to Recycle Random Bits

[BibT_eX]

[DOI]

Russell Impagliazzo