2025
Securing Unbounded Differential Privacy Against Timing Attacks.
CoRR, June, 2025
Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regression.
Proc. Priv. Enhancing Technol., 2025
Obituary for Luca Trevisan.
Bull. EATCS, 2025
2024
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs.
Algorithmica, October, 2024
Small-Space Spectral Sparsification via Bounded-Independence Sampling.
ACM Trans. Comput. Theory, 2024
Membership Inference Attacks and Privacy in Topic Modeling.
Trans. Mach. Learn. Res., 2024
"I inherently just trust that it works": Investigating Mental Models of Open-Source Libraries for Differential Privacy.
Proc. ACM Hum. Comput. Interact., 2024
The Randomness Complexity of Differential Privacy.
Electron. Colloquium Comput. Complex., 2024
Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs.
CoRR, 2024
Characterizing the Distinguishability of Product Distributions through Multicalibration.
CoRR, 2024
Concurrent Composition for Continual Mechanisms.
CoRR, 2024
Programming Frameworks for Differential Privacy.
CoRR, 2024
Complexity-Theoretic Implications of Multicalibration.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
A Framework for Differential Privacy Against Timing Attacks.
Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, 2024
2023
Differentially Private Hypothesis Testing for Linear Regression.
J. Mach. Learn. Res., 2023
On the Power of Regular and Permutation Branching Programs.
Electron. Colloquium Comput. Complex., 2023
Black-Box Training Data Identification in GANs via Detector Networks.
CoRR, 2023
On the works of Avi Wigderson.
CoRR, 2023
Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification.
CoRR, 2023
Concurrent Composition Theorems for Differential Privacy.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Don't Look at the Data! How Differential Privacy Reconfigures the Practices of Data Science.
Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, 2023
Concurrent Composition for Interactive Differential Privacy with Adaptive Privacy-Loss Parameters.
Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, 2023
2022
Differentially Private Simple Linear Regression.
Proc. Priv. Enhancing Technol., 2022
Fourier Growth of Regular Branching Programs.
Electron. Colloquium Comput. Complex., 2022
Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs.
Electron. Colloquium Comput. Complex., 2022
Concurrent Composition Theorems for all Standard Variants of Differential Privacy.
CoRR, 2022
Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size.
Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022
Hypothesis Testing for Differentially Private Linear Regression.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
Widespread Underestimation of Sensitivity in Differentially Private Libraries and How to Fix It.
Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022
2021
Deterministic Approximation of Random Walks in Small Space.
Adv. Math. Commun., 2021
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
SIAM J. Comput., 2021
Concurrent Composition of Differential Privacy.
IACR Cryptol. ePrint Arch., 2021
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator against Permutation Branching Programs.
Electron. Colloquium Comput. Complex., 2021
Pseudodistributions That Beat All Pseudorandom Generators.
Electron. Colloquium Comput. Complex., 2021
Monotone Branching Programs: Pseudorandomness and Circuit Complexity.
Electron. Colloquium Comput. Complex., 2021
Canonical Noise Distributions and Private Hypothesis Tests.
CoRR, 2021
Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract).
Proceedings of the 36th Computational Complexity Conference, 2021
Pseudorandom Generators for Read-Once Monotone Branching Programs.
Proceedings of the Approximation, 2021
2020
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing.
Theory Comput., 2020
ACM Trans. Economics and Comput., 2020
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs.
Electron. Colloquium Comput. Complex., 2020
Spectral Sparsification via Bounded-Independence Sampling.
Electron. Colloquium Comput. Complex., 2020
Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions.
CoRR, 2020
High-precision Estimation of Random Walks in Small Space.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
When Simple Hash Functions Suffice.
Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020
2019
Differential Privacy on Finite Computers.
J. Priv. Confidentiality, 2019
Unifying computational entropies via Kullback-Leibler divergence.
IACR Cryptol. ePrint Arch., 2019
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
2018
The Complexity of Computing the Optimal Composition of Differential Privacy.
Theory Comput., 2018
Fingerprinting Codes and the Price of Approximate Differential Privacy.
SIAM J. Comput., 2018
Deterministic Public-Key Encryption for Adaptively-Chosen Plaintext Distributions.
J. Cryptol., 2018
A Tight Lower Bound for Entropy Flattening.
Electron. Colloquium Comput. Complex., 2018
Usable Differential Privacy: A Case Study with PSI.
CoRR, 2018
Finite Sample Differentially Private Confidence Intervals.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018
2017
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs.
Theory Comput., 2017
The Many Entropies in One-Way Functions.
Electron. Colloquium Comput. Complex., 2017
Computational Notions of Quantum Min-Entropy.
CoRR, 2017
On Learning vs. Refutation.
Proceedings of the 30th Conference on Learning Theory, 2017
The Complexity of Differential Privacy.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017
The Many Entropies in One-Way Functions.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017
2016
Truthful Mechanisms for Agents That Value Privacy.
ACM Trans. Economics and Comput., 2016
Separating Computational and Statistical Differential Privacy in the Client-Server Model.
IACR Cryptol. ePrint Arch., 2016
PSI (Ψ): a Private data Sharing Interface.
CoRR, 2016
Towards a Privacy Research Roadmap for the Computing Community.
CoRR, 2016
Locating a Small Cluster Privately.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016
Privacy Odometers and Filters: Pay-as-you-Go Composition.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016
Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing.
Proceedings of the 33nd International Conference on Machine Learning, 2016
2015
Pseudorandomness for Read-Once, Constant-Depth Circuits.
CoRR, 2015
Robust Traceability from Trace Amounts.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
Differentially Private Release and Learning of Threshold Functions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
2014
Redrawing the boundaries on purchasing data from privacy-sensitive individuals.
Proceedings of the Innovations in Theoretical Computer Science, 2014
2013
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream.
Theory Comput., 2013
Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions.
SIAM J. Comput., 2013
On extractors and exposure-resilient functions for sublogarithmic entropy.
Random Struct. Algorithms, 2013
A Uniform Min-Max Theorem with Applications in Cryptography.
Electron. Colloquium Comput. Complex., 2013
Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Electron. Colloquium Comput. Complex., 2013
Locally Testable Codes and Cayley Graphs.
Electron. Colloquium Comput. Complex., 2013
Interactive proofs of proximity: delegating computation in sublinear time.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Publicly verifiable proofs of sequential work.
Proceedings of the Innovations in Theoretical Computer Science, 2013
2012
Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).
SIAM J. Comput., 2012
Differential Privacy with Imperfect Randomness.
IACR Cryptol. ePrint Arch., 2012
Found. Trends Theor. Comput. Sci., 2012
Better pseudorandom generators from milder pseudorandom restrictions.
Electron. Colloquium Comput. Complex., 2012
Special issue from RANDOM'09: Editors' Foreword.
Comput. Complex., 2012
Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources.
Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012
Characterizing pseudoentropy.
Proceedings of the 2012 IEEE Information Theory Workshop, 2012
Faster Algorithms for Privately Releasing Marginals.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
The Privacy of the Analyst and the Power of the State.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
Computational Complexity.
Proceedings of the Encyclopedia of Cryptography and Security, 2nd Ed., 2011
Deterministic extractors for small-space sources.
J. Comput. Syst. Sci., 2011
Non-Interactive Time-Stamping and Proofs of Work in the Random Oracle Model.
IACR Cryptol. ePrint Arch., 2011
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions.
Electron. Colloquium Comput. Complex., 2011
The Limits of Two-Party Differential Privacy.
Electron. Colloquium Comput. Complex., 2011
On the complexity of computational problems regarding distributions (a survey).
Electron. Colloquium Comput. Complex., 2011
PCPs and the Hardness of Generating Private Synthetic Data.
Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011
Time-Lock Puzzles in the Random Oracle Model.
Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011
Simplified Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On the Complexity of Computational Problems Regarding Distributions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
2010
A Lower Bound on List Size for List Decoding.
IEEE Trans. Inf. Theory, 2010
Universal One-Way Hash Functions via Inaccessible Entropy.
IACR Cryptol. ePrint Arch., 2010
Improved Delegation of Computation using Fully Homomorphic Encryption.
IACR Cryptol. ePrint Arch., 2010
PCPs and the Hardness of Generating Synthetic Data.
Electron. Colloquium Comput. Complex., 2010
On Approximating the Entropy of Polynomial Mappings.
Electron. Colloquium Comput. Complex., 2010
Are PCPs Inherent in Efficient Arguments?
Comput. Complex., 2010
Boosting and Differential Privacy.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
2009
Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function.
SIAM J. Comput., 2009
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.
J. ACM, 2009
Proofs of Retrievability via Hardness Amplification.
IACR Cryptol. ePrint Arch., 2009
Composition of Zero-Knowledge Proofs with Efficient Provers.
IACR Cryptol. ePrint Arch., 2009
Electron. Colloquium Comput. Complex., 2009
On the complexity of differentially private data release: efficient algorithms and hardness results.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009
Computational Differential Privacy.
Proceedings of the Advances in Cryptology, 2009
Pseudorandom Bit Generators That Fool Modular Sums.
Proceedings of the Approximation, 2009
2008
The Round Complexity of Two-Party Random Selection.
SIAM J. Comput., 2008
Simpler Session-Key Generation from Short Random Passwords.
J. Cryptol., 2008
Fairness with an Honest Minority and a Rational Majority.
IACR Cryptol. ePrint Arch., 2008
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Electron. Colloquium Comput. Complex., 2008
Dense Subsets of Pseudorandom Sets.
Electron. Colloquium Comput. Complex., 2008
Limitations of Hardness vs. Randomness under Uniform Reductions.
Electron. Colloquium Comput. Complex., 2008
An Equivalence Between Zero Knowledge and Commitments.
Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008
Why simple hash functions work: exploiting the entropy in a data stream.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Tight Bounds for Hashing Block Sources.
Proceedings of the Approximation, 2008
The Complexity of Distinguishing Markov Random Fields.
Proceedings of the Approximation, 2008
2007
The unified theory of pseudorandomness: guest column.
SIGACT News, 2007
Derandomization in Cryptography.
SIAM J. Comput., 2007
The hardness of the Expected Decision Depth problem.
Inf. Process. Lett., 2007
Interactive and Noninteractive Zero Knowledge Coincide in the Help Model.
IACR Cryptol. ePrint Arch., 2007
Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model.
IACR Cryptol. ePrint Arch., 2007
S-T Connectivity on Digraphs with a Known Stationary Distribution.
Electron. Colloquium Comput. Complex., 2007
Pseudorandomness and Average-Case Complexity Via Uniform Reductions.
Comput. Complex., 2007
Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword.
Comput. Complex., 2007
The Complexity of Zero Knowledge.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007
Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
Proceedings of the Advances in Cryptology, 2007
2006
An Unconditional Study of Computational Zero Knowledge.
SIAM J. Comput., 2006
Using Nondeterminism to Amplify Hardness.
SIAM J. Comput., 2006
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.
SIAM J. Comput., 2006
Lower bounds for non-black-box zero knowledge.
J. Comput. Syst. Sci., 2006
Zero Knowledge and Soundness are Symmetric.
Electron. Colloquium Comput. Complex., 2006
Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
Electron. Colloquium Comput. Complex., 2006
Extractors and condensers from univariate polynomials.
Electron. Colloquium Comput. Complex., 2006
Random Selection with an Adversarial Majority.
Electron. Colloquium Comput. Complex., 2006
Pseudorandom walks on regular digraphs and the RL vs. L problem.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Zero knowledge with efficient provers.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
2005
Computational Complexity.
Proceedings of the Encyclopedia of Cryptography and Security, 2005
Concurrent Zero Knowledge without Complexity Assumptions
Electron. Colloquium Comput. Complex., 2005
Derandomized Squaring of Graphs
Electron. Colloquium Comput. Complex., 2005
The Computational Complexity of Nash Equilibria in Concisely Represented Games
Electron. Colloquium Comput. Complex., 2005
Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Electron. Colloquium Comput. Complex., 2005
Compression of Samplable Sources.
Comput. Complex., 2005
Short PCPs Verifiable in Polylogarithmic Time.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005
2004
Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.
J. Cryptol., 2004
Notions of Reducibility between Cryptographic Primitives.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004
Probabilistic proof systems - Part I.
Proceedings of the Computational Complexity Theory., 2004
2003
Extractors: optimal up to constant factors.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More.
Proceedings of the Advances in Cryptology, 2003
2002
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
J. Comput. Syst. Sci., 2002
The Power of a Pebble: Exploring and Mapping Directed Graphs.
Inf. Comput., 2002
An Improved Pseudorandom Generator Based on Hardness of Factoring.
IACR Cryptol. ePrint Arch., 2002
On interactive proofs with a laconic prover.
Comput. Complex., 2002
Randomness conductors and constant-degree lossless expanders.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Randomness Extractors and their Many Guises.
Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002
2001
The Complexity of Counting in Sparse, Regular, and Planar Graphs.
SIAM J. Comput., 2001
Pseudorandom Generators without the XOR Lemma.
J. Comput. Syst. Sci., 2001
On the (Im)possibility of Obfuscating Programs
Electron. Colloquium Comput. Complex., 2001
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Electron. Colloquium Comput. Complex., 2001
Order in Pseudorandomness.
Proceedings of the Approximation, 2001
2000
A Complete Problem for Statistical Zero Knowledge
Electron. Colloquium Comput. Complex., 2000
Simplified derandomization of BPP using a hitting set generator.
Electron. Colloquium Comput. Complex., 2000
On transformation of interactive proofs that preserve the prover's complexity.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Extracting Randomness from Samplable Distributions.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000
1999
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK
Electron. Colloquium Comput. Complex., 1999
Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999
Error Reduction for Extractors.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
Verifiable Random Functions.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
Pseudorandom Generators without the XOR Lemma (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999
1998
Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems.
IACR Cryptol. ePrint Arch., 1998
Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK
Electron. Colloquium Comput. Complex., 1998
Extracting All the Randomness from a Weakly Random Source
Electron. Colloquium Comput. Complex., 1998
Checking Polynomial Identities over any Field: Towards a Derandomization?
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Many-to-One Trapdoor Functions and Their Ralation to Public-Key Cryptosystems.
Proceedings of the Advances in Cryptology, 1998
1997
A Complete Promise Problem for Statistical Zero-Knowledge.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997
Manipulating statistical difference.
Proceedings of the Randomization Methods in Algorithm Design, 1997