Ronen Shaltiel

Electron. Colloquium Comput. Complex., 2025

Extractors for Samplable Distributions from the Two-Source Extractor Recipe.

[BibT_eX]

[DOI]

Justin Oh

Electron. Colloquium Comput. Complex., 2025

Extractors for Samplable Distributions with Low Min-Entropy.

[BibT_eX]

[DOI]

Marshall Ball

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

Multiplicative Extractors for Samplable Distributions.

[BibT_eX]

[DOI]

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2024

Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions.

[BibT_eX]

[DOI]

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

Non-malleable Codes with Optimal Rate for Poly-Size Circuits.

[BibT_eX]

[DOI]

Marshall Ball

Proceedings of the Advances in Cryptology - EUROCRYPT 2024, 2024

2022

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371).

[BibT_eX]

[DOI]

Dagstuhl Reports, September, 2022

On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization.

[BibT_eX]

[DOI]

Emanuele Viola

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

Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists).

[BibT_eX]

[DOI]

Noga Ron-Zewi

Nithin Varma

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Is It Possible to Improve Yao's XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Special Issue: APPROX-RANDOM 2016: Guest Editors' Foreword.

[BibT_eX]

[DOI]

Shiri Chechik

Theory Comput., 2019

Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 17th International Conference, 2019

Quasilinear Time List-Decodable Codes for Space Bounded Channels.

[BibT_eX]

[DOI]

Swastik Kopparty

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Computational Two-Party Correlation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols.

[BibT_eX]

[DOI]

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

Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs.

[BibT_eX]

[DOI]

Aryeh Grinberg

Emanuele Viola

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

2016

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions.

[BibT_eX]

[DOI]

Comput. Complex., 2016

Pseudorandomness When the Odds are Against You.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Parallel Hashing via List Recoverability.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Pseudorandom generators with optimal seed length for non-boolean poly-size circuits.

[BibT_eX]

[DOI]

Sergei Artemenko

Proceedings of the Symposium on Theory of Computing, 2014

Mining Circuit Lower Bound Proofs for Meta-algorithms.

[BibT_eX]

[DOI]

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

2012

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Jeff Kinne

Dieter van Melkebeek

Comput. Complex., 2012

On beating the hybrid argument.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors.

[BibT_eX]

[DOI]

Ariel Gabizon

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

An Introduction to Randomness Extractors.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Dispersers for Affine Sources with Sub-polynomial Entropy.

[BibT_eX]

[DOI]

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

Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification.

[BibT_eX]

[DOI]

Sergei Artemenko

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Typically-correct derandomization.

[BibT_eX]

[DOI]

SIGACT News, 2010

Derandomized Parallel Repetition Theorems for Free Games.

[BibT_eX]

[DOI]

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

2009

Low-End Uniform Hardness versus Randomness Tradeoffs for AM.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

On the (Im)Possibility of Arthur-Merlin Witness Hiding Protocols.

[BibT_eX]

[DOI]

Iftach Haitner

Alon Rosen

Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Pseudorandom Generators and Typically-Correct Derandomization.

[BibT_eX]

[DOI]

Jeff Kinne

Dieter van Melkebeek

Proceedings of the Approximation, 2009

Strong Parallel Repetition Theorem for Free Projection Games.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Hardness amplification proofs require majority.

[BibT_eX]

[DOI]

Emanuele Viola

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

Increasing the Output Length of Zero-Error Dispersers.

[BibT_eX]

[DOI]

Ariel Gabizon

Proceedings of the Approximation, 2008

2007

Low-end uniform hardness vs. randomness tradeoffs for AM.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Reducing The Seed Length In The Nisan-Wigderson Generator.

[BibT_eX]

[DOI]

Russell Impagliazzo

Comb., 2006

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.

[BibT_eX]

[DOI]

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

How to Get More Mileage from Randomness Extractors.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Simple extractors for all min-entropies and a new pseudorandom generator.

[BibT_eX]

[DOI]

J. ACM, 2005

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Reducing Complexity Assumptions for Statistically-Hiding Commitment.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2005

Pseudorandomness for Approximate Counting and Sampling.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances.

[BibT_eX]

[DOI]

Dan Gutfreund

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

[BibT_eX]

[DOI]

Iftach Haitner

Electron. Colloquium Comput. Complex., 2004

List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Constant-Round Oblivious Transfer in the Bounded Storage Model.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.

[BibT_eX]

[DOI]

Ariel Gabizon

Ran Raz

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

Non-interactive Timestamping in the Bounded Storage Model.

[BibT_eX]

[DOI]

Tal Moran

Proceedings of the Advances in Cryptology, 2004

2003

Uniform hardness versus randomness tradeoffs for Arthur-Merlin games.

[BibT_eX]

[DOI]

Dan Gutfreund

Comput. Complex., 2003

Computational Analogues of Entropy.

[BibT_eX]

[DOI]

Boaz Barak

Proceedings of the Approximation, 2003

Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games.

[BibT_eX]

[DOI]

Dan Gutfreund

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

True Random Number Generators Secure in a Changing Environment.

[BibT_eX]

[DOI]

Boaz Barak

Eran Tromer

Proceedings of the Cryptographic Hardware and Embedded Systems, 2003

2002

Recent Developments in Explicit Constructions of Extractors.

[BibT_eX]

Bull. EATCS, 2002

Streaming Computation of Combinatorial Objects.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Explicit constructions of pseudo-random generators and extractors (בניות מפורשות של יצרנים פסאודו-אקראיים ומזקקי אקראיות.).

[BibT_eX]

[DOI]

PhD thesis, 2001

Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator.

[BibT_eX]

[DOI]

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

Towards Proving Strong Direct Product Theorems.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Extractors and pseudo-random generators with optimal seed length.

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Extracting Randomness via Repeated Condensing.

[BibT_eX]

[DOI]

Omer Reingold

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Near-Optimal Conversion of Hardness into Pseudo-Randomness.

[BibT_eX]

[DOI]

Russell Impagliazzo