2025
Trading Inference-Time Compute for Adversarial Robustness.
,
,
,
,
,
,
,
,
,
,
CoRR, January, 2025
2024
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
CoRR, 2024
Deliberative Alignment: Reasoning Enables Safer Language Models.
,
,
,
,
,
,
,
,
,
,
,
,
,
,
CoRR, 2024
An Economic Solution to Copyright Challenges of Generative AI.
CoRR, 2024
Watermarks in the Sand: Impossibility of Strong Watermarking for Language Models.
Proceedings of the Forty-first International Conference on Machine Learning, 2024
Distinguishing the Knowable from the Unknowable with Language Models.
Proceedings of the Forty-first International Conference on Machine Learning, 2024
Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning.
Proceedings of the Forty-first International Conference on Machine Learning, 2024
2023
Trans. Mach. Learn. Res., 2023
Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models.
IACR Cryptol. ePrint Arch., 2023
On the works of Avi Wigderson.
CoRR, 2023
Robust reconstruction of single-cell RNA-seq data with iterative gene weight updates.
Bioinform., 2023
Scaling Data-Constrained Language Models.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023
On Provable Copyright Protection for Generative Models.
Proceedings of the International Conference on Machine Learning, 2023
Deconstructing Distributions: A Pointwise Framework of Learning.
Proceedings of the Eleventh International Conference on Learning Representations, 2023
2022
Noisy tensor completion via the sum-of-squares hierarchy.
Math. Program., 2022
Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
2021
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage.
CoRR, 2021
Playing unique games on certified small-set expanders.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
Revisiting Model Stitching to Compare Neural Representations.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021
For self-supervised learning, Rationality implies generalization, provably.
Proceedings of the 9th International Conference on Learning Representations, 2021
2020
On Higher-Order Cryptography (Long Version).
CoRR, 2020
Deep Double Descent: Where Bigger Models and More Data Hurt.
Proceedings of the 8th International Conference on Learning Representations, 2020
On Higher-Order Cryptography.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
2019
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
SIAM J. Comput., 2019
SGD on Neural Networks Learns Functions of Increasing Complexity.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
2018
Sum-of-Squares Meets Program Obfuscation, Revisited.
IACR Cryptol. ePrint Arch., 2018
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture.
Electron. Colloquium Comput. Complex., 2018
2017
Merkle's Key Agreement Protocol is Optimal: An O(n<sup>2</sup>) Attack on Any Key Agreement from Random Oracles.
J. Cryptol., 2017
The Complexity of Public-Key Cryptography.
IACR Cryptol. ePrint Arch., 2017
Quantum entanglement, sum of squares, and the log rank conjecture.
Electron. Colloquium Comput. Complex., 2017
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation).
Electron. Colloquium Comput. Complex., 2017
The Complexity of Public-Key Cryptograph.
Electron. Colloquium Comput. Complex., 2017
The Complexity of Public-Key Cryptography.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017
2016
Hopes, Fears and Software Obfuscation: A Survey.
IACR Cryptol. ePrint Arch., 2016
Computer science should stay young.
Commun. ACM, 2016
A breakthrough in software obfuscation: technical perspective.
Commun. ACM, 2016
Hopes, fears, and software obfuscation.
Commun. ACM, 2016
2015
Path-Quality Monitoring in the Presence of Adversaries: The Secure Sketch Protocols.
IEEE/ACM Trans. Netw., 2015
Making the Long Code Shorter.
SIAM J. Comput., 2015
Subexponential Algorithms for Unique Games and Related Problems.
J. ACM, 2015
Beating the random assignment on constraint satisfaction problems of bounded degree.
Electron. Colloquium Comput. Complex., 2015
Tensor Prediction, Rademacher Complexity and Random 3-XOR.
CoRR, 2015
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015
Sum of Squares Lower Bounds from Pairwise Independence.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015
Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk).
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015
2014
Sum-of-squares proofs and the quest toward optimal algorithms.
Electron. Colloquium Comput. Complex., 2014
2013
How to Compress Interactive Communication.
SIAM J. Comput., 2013
Protecting Obfuscation Against Algebraic Attacks.
IACR Cryptol. ePrint Arch., 2013
Obfuscation for Evasive Functions.
IACR Cryptol. ePrint Arch., 2013
Rounding Sum-of-Squares Relaxations.
Electron. Colloquium Comput. Complex., 2013
Structure vs Combinatorics in Computational Complexity.
Electron. Colloquium Comput. Complex., 2013
Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword.
Comput. Complex., 2013
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.
Proceedings of the Innovations in Theoretical Computer Science, 2013
2012
Proof vs. Truth in Computational Complexity.
Electron. Colloquium Comput. Complex., 2012
Truth vs. Proof in Computational Complexity.
Bull. EATCS, 2012
Hypercontractivity, sum-of-squares proofs, and their applications.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
2011
Secure Computation Without Authentication.
J. Cryptol., 2011
Leftover Hash Lemma, Revisited.
IACR Cryptol. ePrint Arch., 2011
Rounding Semidefinite Programming Hierarchies via Global Correlation.
Electron. Colloquium Comput. Complex., 2011
Making the long code shorter, with applications to the Unique Games Conjecture.
Electron. Colloquium Comput. Complex., 2011
Computational complexity and information asymmetry in financial products.
Commun. ACM, 2011
Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
Subsampling Mathematical Relaxations and Average-case Complexity.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
2010
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors.
Electron. Colloquium Comput. Complex., 2010
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.
Electron. Colloquium Comput. Complex., 2010
Public-key cryptography from different assumptions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract).
Proceedings of the Innovations in Computer Science, 2010
2009
Bounded Key-Dependent Message Security.
IACR Cryptol. ePrint Arch., 2009
Subsampling Semidefinite Programs and Max-Cut on the Sphere.
Electron. Colloquium Comput. Complex., 2009
Direct Sums in Randomized Communication Complexity.
Electron. Colloquium Comput. Complex., 2009
The uniform hardcore lemma via approximate Bregman projections.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Merkle Puzzles Are Optimal - An <i>O</i>(<i>n</i><sup>2</sup>)-Query Attack on Any Key Exchange from a Random Oracle.
Proceedings of the Advances in Cryptology, 2009
Strong Parallel Repetition Theorem for Free Projection Games.
Proceedings of the Approximation, 2009
Computational Complexity - A Modern Approach.
Cambridge University Press, ISBN: 978-0-521-42426-4, 2009
2008
Universal Arguments and their Applications.
SIAM J. Comput., 2008
Public Key Cryptography from Different Assumptions.
IACR Cryptol. ePrint Arch., 2008
Lower Bounds on Signatures From Symmetric Primitives.
IACR Cryptol. ePrint Arch., 2008
Merkle Puzzles are Optimal.
IACR Cryptol. ePrint Arch., 2008
Path-quality monitoring in the presence of adversaries.
Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2008
Rounding Parallel Repetitions of Unique Games.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
On Basing Lower-Bounds for Learning on Worst-Case Assumptions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Protocols and Lower Bounds for Failure Localization in the Internet.
Proceedings of the Advances in Cryptology, 2008
2007
Derandomization in Cryptography.
SIAM J. Comput., 2007
Privacy, accuracy, and consistency too: a holistic solution to contingency table release.
Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007
2006
Extracting Randomness Using Few Independent Sources.
SIAM J. Comput., 2006
Lower bounds for non-black-box zero knowledge.
J. Comput. Syst. Sci., 2006
Concurrent Non-Malleable Zero Knowledge.
IACR Cryptol. ePrint Arch., 2006
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Non-black-box Techniques in Cryptography.
Proceedings of the Computer Science, 2006
2005
A model and architecture for pseudo-random generation with applications to /dev/random.
IACR Cryptol. ePrint Arch., 2005
How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation
Electron. Colloquium Comput. Complex., 2005
2004
Strict Polynomial-Time in Simulation and Extraction.
SIAM J. Comput., 2004
Protocol Initialization for the Framework of Universal Composability.
IACR Cryptol. ePrint Arch., 2004
On the Possibility of One-Message Weak Zero-Knowledge.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004
Universally Composable Protocols with Relaxed Set-Up Assumptions.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
2003
Computational Analogues of Entropy.
Proceedings of the Approximation, 2003
True Random Number Generators Secure in a Changing Environment.
Proceedings of the Cryptographic Hardware and Embedded Systems, 2003
2002
A Probabilistic-Time Hierarchy Theorem for "Slightly Non-uniform" Algorithms.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002
Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Resettably-Sound Zero-Knowledge and its Applications.
IACR Cryptol. ePrint Arch., 2001
On the (Im)possibility of Obfuscating Programs
Electron. Colloquium Comput. Complex., 2001
How to Go Beyond the Black-Box Simulation Barrier.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
2000
Clock synchronization with faults and recoveries (extended abstract).
Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000
1999
The Proactive Security Toolkit and Applications.
Proceedings of the CCS '99, 1999