David Zuckerman

Electron. Colloquium Comput. Complex., 2024

Improved Condensers for Chor-Goldreich Sources.

[BibT_eX]

[DOI]

Jesse Goodman

Xin Li

Electron. Colloquium Comput. Complex., 2024

Online Condensing of Unpredictable Sources via Random Walks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

2022

Extractors for Images of Varieties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Almost Chor-Goldreich Sources and Adversarial Random Walks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

The Space Complexity of Sampling.

[BibT_eX]

[DOI]

Jesse Goodman

Electron. Colloquium Comput. Complex., 2021

2020

Simple Optimal Hitting Sets for Small-Success RL.

[BibT_eX]

[DOI]

William M. Hoza

SIAM J. Comput., 2020

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

[BibT_eX]

[DOI]

Ashutosh Kumar

Electron. Colloquium Comput. Complex., 2020

Spectral Sparsification via Bounded-Independence Sampling.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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]

Electron. Colloquium Comput. Complex., 2019

Nearly Optimal Pseudorandomness From Hardness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

XOR Lemmas for Resilient Functions Against Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

Improved Extractors for Recognizable and Algebraic Sources.

[BibT_eX]

[DOI]

Fu Li

Electron. Colloquium Comput. Complex., 2018

Existence of Simple Extractors.

[BibT_eX]

[DOI]

Xue Chen

Electron. Colloquium Comput. Complex., 2018

2016

Rectangles Are Nonnegative Juntas.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

Robust Fourier and Polynomial Curve Fitting.

[BibT_eX]

[DOI]

Venkatesan Guruswami

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

2015

New Extractors for Interleaved Sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Explicit Two-Source Extractors and Resilient Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Mining Circuit Lower Bound Proofs for Meta-Algorithms.

[BibT_eX]

[DOI]

Comput. Complex., 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

Non-Malleable Codes Against Constant Split-State Tampering.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2013

Pseudorandom Generators for Polynomial Threshold Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Pseudorandom Generators for Combinatorial Shapes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Robust Pseudorandom Generators.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Pseudorandomness from Shrinkage.

[BibT_eX]

[DOI]

Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2012

2011

Deterministic extractors for small-space sources.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Non-malleable extractors via character sums

[BibT_eX]

[DOI]

Trevor D. Wooley

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

Fooling functions of halfspaces under product distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Can Random Coin Flips Speed Up a Computer?

[BibT_eX]

[DOI]

CoRR, 2010

Optimal Testing of Reed-Muller Codes.

[BibT_eX]

[DOI]

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

2009

Testing low-degree polynomials over prime fields.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2009

Optimal testing of Reed-Muller codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

[BibT_eX]

[DOI]

Jesse Kamp

SIAM J. Comput., 2007

Lossless Condensers, Unbalanced Expanders, And Extractors.

[BibT_eX]

[DOI]

Christopher Umans

Comb., 2007

2006

Extractors from Reed-Muller codes.

[BibT_eX]

[DOI]

Shmuel Safra

J. Comput. Syst. Sci., 2006

Random Selection with an Adversarial Majority.

[BibT_eX]

[DOI]

Ronen Gradwohl

Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2006

2005

Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Compression of Samplable Sources.

[BibT_eX]

[DOI]

Luca Trevisan

Salil P. Vadhan

Comput. Complex., 2005

2004

Extractor codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2004

2002

Combinatorial bounds for list decoding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2002

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

[BibT_eX]

[DOI]

Alexander Russell

Michael E. Saks

SIAM J. Comput., 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

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

2000

Low discrepancy sets yield approximate min-wise independent permutation families.

[BibT_eX]

[DOI]

Inf. Process. Lett., 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

Computing with Very Weak Random Sources.

[BibT_eX]

[DOI]

Aravind Srinivasan

SIAM J. Comput., 1999

Tight Analyses of Two Local Load Balancing Algorithms.

[BibT_eX]

[DOI]

Bhaskar Ghosh

Frank Thomson Leighton

SIAM J. Comput., 1999

Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications.

[BibT_eX]

[DOI]

Avi Wigderson

Comb., 1999

1998

Lower Bounds for Randomized Mutual Exclusion.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension.

[BibT_eX]

[DOI]

Comb., 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

Simulating BPP Using a General Weak Random Source.

[BibT_eX]

[DOI]

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

1993

Optimal Speedup of Las Vegas Algorithms.

[BibT_eX]

[DOI]

Michael Luby

Alistair Sinclair

Inf. Process. Lett., 1993

More deterministic simulation in logspace.

[BibT_eX]

[DOI]

Noam Nisan

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 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

1992

A Technique for Lower Bounding the Cover Time.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1992

1991

On the Time to Traverse all Edges of a Graph.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1991

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