| Publication | Date of Publication | Type |
|---|
| Constant-round coin-tossing with a man in the middle or realizing the shared random string model | 2026-05-29 | Paper |
| Lower bounds for non-black-box zero knowledge | 2026-05-29 | Paper |
| Universally composable protocols with relaxed set-up assumptions | 2026-05-29 | Paper |
| Extracting randomness using few independent sources | 2026-05-29 | Paper |
| Concurrent non-malleable zero knowledge | 2026-05-29 | Paper |
| How to go beyond the black-box simulation barrier | 2026-05-08 | Paper |
| Resettably-sound zero-knowledge and its applications | 2026-05-08 | Paper |
Computational complexity of deep learning: fundamental limitations and empirical phenomena
Journal of Statistical Mechanics: Theory and Experiment | 2026-04-23 | Paper |
| Spoofing linear cross-entropy benchmarking in shallow quantum circuits | 2026-04-15 | Paper |
| On higher-order cryptography | 2026-03-18 | Paper |
| A nearly tight sum-of-squares lower bound for the planted clique problem | 2025-08-06 | Paper |
| Making the long code shorter | 2025-05-05 | Paper |
| Subexponential algorithms for unique games and related problems | 2025-04-29 | Paper |
scientific article; zbMATH DE number 7829246 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
Playing unique games on certified small-set expanders
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Small-set expansion in shortcode graph and the 2-to-2 conjecture
(available as arXiv preprint) | 2022-07-18 | Paper |
Noisy tensor completion via the sum-of-squares hierarchy
Mathematical Programming. Series A. Series B | 2022-06-14 | Paper |
The Complexity of Public-Key Cryptography
Tutorials on the Foundations of Cryptography | 2022-01-12 | Paper |
Deep double descent: where bigger models and more data hurt*
Journal of Statistical Mechanics: Theory and Experiment | 2022-01-03 | Paper |
| Sum-of-squares meets program obfuscation, revisited | 2020-02-04 | Paper |
| Structure vs combinatorics in computational complexity | 2019-07-03 | Paper |
A nearly tight sum-of-squares lower bound for the planted clique problem
SIAM Journal on Computing | 2019-05-07 | Paper |
| The uniform hardcore lemma via approximate Bregman projections | 2019-05-06 | Paper |
| Truth vs. proof in computational complexity | 2018-09-04 | Paper |
Subexponential algorithms for unique games and related problems
Journal of the ACM | 2018-08-02 | Paper |
| Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation) | 2018-07-09 | Paper |
Sum-of-squares proofs and the quest toward optimal algorithms
(available as arXiv preprint) | 2017-11-06 | Paper |
Merkle's key agreement protocol is optimal: an \(O(n^2)\) attack on any key agreement from random oracles
Journal of Cryptology | 2017-10-12 | Paper |
| Subsampling mathematical relaxations and average-case complexity | 2017-09-29 | Paper |
Quantum entanglement, sum of squares, and the log rank conjecture
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Making the Long Code Shorter
SIAM Journal on Computing | 2015-11-04 | Paper |
Sum of squares lower bounds from pairwise independence (extended abstract)
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Dictionary learning and tensor decomposition via the sum-of-squares method
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Rounding sum-of-squares relaxations
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Clock synchronization with faults and recoveries (extended abstract)
Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing | 2015-03-03 | Paper |
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
How to compress interactive communication
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Public-key cryptography from different assumptions
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Rounding Semidefinite Programming Hierarchies via Global Correlation
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Fractional Sylvester–Gallai theorems
Proceedings of the National Academy of Sciences | 2014-07-25 | Paper |
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Protecting obfuscation against algebraic attacks
Advances in Cryptology – EUROCRYPT 2014 | 2014-05-27 | Paper |
Hypercontractivity, sum-of-squares proofs, and their applications
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Obfuscation for evasive functions
Theory of Cryptography | 2014-02-18 | Paper |
On the (im)possibility of obfuscating programs
Journal of the ACM | 2014-02-17 | Paper |
How to compress interactive communication
SIAM Journal on Computing | 2013-09-25 | Paper |
2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
Annals of Mathematics. Second Series | 2013-01-03 | Paper |
Secure computation without authentication
Journal of Cryptology | 2012-01-13 | Paper |
Leftover Hash Lemma, Revisited
Advances in Cryptology – CRYPTO 2011 | 2011-08-12 | Paper |
Simulating independence
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Strict polynomial-time in simulation and extraction
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
Journal of the ACM | 2010-07-14 | Paper |
Bounded key-dependent message security
Advances in Cryptology – EUROCRYPT 2010 | 2010-06-01 | Paper |
Computational analogues of entropy
Lecture Notes in Computer Science | 2010-05-26 | Paper |
True random number generators secure in a changing environment.
Lecture Notes in Computer Science | 2010-03-09 | Paper |
Universal Arguments and their Applications
SIAM Journal on Computing | 2009-11-06 | Paper |
Strong Parallel Repetition Theorem for Free Projection Games
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
Advances in Cryptology - CRYPTO 2009 | 2009-10-20 | Paper |
| Computational Complexity | 2009-07-22 | Paper |
Theory of Cryptography
Lecture Notes in Computer Science | 2009-05-14 | Paper |
Derandomization in Cryptography
SIAM Journal on Computing | 2008-04-22 | Paper |
Protocols and Lower Bounds for Failure Localization in the Internet
Advances in Cryptology – EUROCRYPT 2008 | 2008-04-15 | Paper |
Secure Computation Without Authentication
Advances in Cryptology – CRYPTO 2005 | 2008-03-17 | Paper |
Advances in Cryptology - CRYPTO 2003
Lecture Notes in Computer Science | 2007-11-28 | Paper |
Extracting Randomness Using Few Independent Sources
SIAM Journal on Computing | 2007-09-07 | Paper |
Lower bounds for non-black-box zero knowledge
Journal of Computer and System Sciences | 2006-04-28 | Paper |
| A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph | 2006-01-26 | Paper |
Strict Polynomial-Time in Simulation and Extraction
SIAM Journal on Computing | 2005-02-21 | Paper |
| scientific article; zbMATH DE number 2019635 (Why is no real title available?) | 2003-12-17 | Paper |
| scientific article; zbMATH DE number 1842483 (Why is no real title available?) | 2002-12-08 | Paper |
