I am interested in all areas of theoretical computer science, particularly cryptography and computational complexity. Electronic versions of my papers are below. See also non-technical writing - surveys, presentations, including essays for a non-expert audience. You can also download my thesis Non-Black-Box Techniques in Cryptography (pdf, 186 pages, 1.9MB) and view a draft our my complexity textbook with Sanjeev Arora.

Boaz Barak's Publications

 

B. Barak and A. Moitra. Tensor Prediction, Rademacher Complexity and Random 3-XOR . In COLT, 2016.
[ bib | link ]

 

B. Barak, S. Hopkins, J. Kelner, P. Kothari, A. Moitra, and A. Potechin. A nearly tight Sum-of-Squares lower bound for the Planted Clique problem . 2016.
[ bib | link ]

 

B. Barak. Hopes, Fears, and Software Obfuscation . Communications of the ACM, 59(3):88-96, 2016.
[ bib | link ]

 

B. Barak, A. Moitra, R. O'Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, and J. Wright. Beating the random assignment on constraint satisfaction problems of bounded degree . In RANDOM-APPROX, 2015.
[ bib | eccc ]

 

B. Barak, S. O. Chan, and P. Kothari. Sum of Squares Lower Bounds from Pairwise Independence . In STOC, 2015.
[ bib | link ]

 

B. Barak, J. A. Kelner, and D. Steurer. Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method . In STOC, 2015.
[ bib | link ]

 

A. Glaser, B. Barak, and R. J. Goldston. A zero-knowledge protocol for nuclear warhead verification . Nature, 510:497-502, 2014.
[ bib | link ]

 

B. Barak and D. Steurer. Sum-of-squares proofs and the quest toward optimal algorithms . In Proceedings of International Congress of Mathematicians (ICM), 2014. To appear.
[ bib | eccc ]

 

B. Barak. Fun and Games with Sums of Squares . Also appeared on the ``Windows on Theory'' blog, 2014.
[ bib | .pdf ]

 

B. Barak, J. A. Kelner, and D. Steurer. Rounding sum-of-squares relaxations . In STOC, pages 31-40, 2014.
[ bib | eccc ]

 

B. Barak, N. Bitansky, R. Canetti, Y. T. Kalai, O. Paneth, and A. Sahai. Obfuscation for Evasive Functions . In TCC, pages 26-51, 2014.
[ bib | eprint ]

 

B. Barak, S. Garg, Y. T. Kalai, O. Paneth, and A. Sahai. Protecting Obfuscation against Algebraic Attacks . In EUROCRYPT, volume 8441 of Lecture Notes in Computer Science, pages 221-238. Springer, 2014.
[ bib | eprint ]

 

B. Barak. Structure vs. Combinatorics in Computational Complexity . Survey, also posted on Windows on Theory blog at https://windowsontheory.org/2013/10/07/structure-vs-combinatorics-in-computational-complexity/, 2013.
[ bib | eccc ]

 

A. Glaser, B. Barak, and R. J. Goldston. Toward a Secure Inspection System for Nuclear Warhead Verication Without Information Barrier . Presented at 54th Annual INMM (Institute of Nuclear Materials Management) meeting, 2013.
[ bib ]

 

B. Barak, G. Kindler, and D. Steurer. On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction . In R. D. Kleinberg, editor, ITCS, pages 197-214. ACM, 2013.
[ bib | .pdf ]

 

B. Barak, M. Braverman, X. Chen, and A. Rao. How to Compress Interactive Communication . SIAM J. Comput., 42(3):1327-1363, 2013. Preliminary version in STOC 2010.
[ bib | .pdf ]

 

B. Barak. Truth vs. Proof in Computational Complexity . Bulletin of the European Association for Theoretical Computer Science, (108), October 2012. Appeared in Logic in Computer Science column. Adaptation of the blog post https://windowsontheory.org/2012/07/31/truth-vs-proof-the-unique-games-conjecture-and-feiges-hypothesis/.
[ bib | .pdf ]

 

A. Glaser, B. Barak, and R. J. Goldston. A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol . Presented at 53rd Annual INMM (Institute of Nuclear Materials Management) meeting, 2012.
[ bib | powerpoint | .pdf ]

 

B. Barak, Z. Dvir, A. Wigderson, and A. Yehudayoff. Fractional Sylvester-Gallai theorems . Proceedings of the National Academy of Sciences, 2012. Journal version of STOC '11 paper ``Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes''.
[ bib | .pdf ]

 

B. Barak, P. Gopalan, J. Håstad, R. Meka, and P. Raghavendra. Making the Long Code Shorter . In FOCS, 2012.
[ bib | eccc ]

 

B. Barak, F. G. S. L. Brandao, A. W. Harrow, J. A. Kelner, D. Steurer, and Y. Zhou. Hypercontractivity, sum-of-squares proofs, and their applications . In STOC, pages 307-326, 2012.
[ bib | arxiv ]

 

B. Barak, A. Rao, R. Shaltiel, and A. Wigderson. 2-source dispersers for no (1) entropy, and Ramsey graphs beating the Frankl-Wilson construction . Annals of Mathematics, 176(3):1483-1543, 2012. Prelimninary version in STOC '06.
[ bib | .pdf ]

 

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs . J. ACM, 59(2):6, 2012. Preliminary version in CRYPTO 2001.
[ bib | powerpoint | .pdf ]

 

B. Barak, P. Raghavendra, and D. Steurer. Rounding Semidefinite Programming Hierarchies via Global Correlation . In FOCS, pages 472-481, 2011.
[ bib | arxiv ]

 

B. Barak, Y. Dodis, H. Krawczyk, O. Pereira, K. Pietrzak, F.-X. Standaert, and Y. Yu. Leftover Hash Lemma, Revisited . In CRYPTO, 2011. According to the New Yorker, this was one of the more obscure titles in the CRYPTO '11 conference, see highlighted text in the 4th page here https://www.cs.nyu.edu/~dodis/ps/lhl-newyorker-oct-2011.pdf.
[ bib | .pdf ]

 

S. Arora, B. Barak, M. Brunnermeier, and R. Ge. Computational complexity and information asymmetry in financial products . Commun. ACM, 54(5):101-107, 2011.
[ bib | link ]

 

B. Barak, M. Hardt, T. Holenstein, and D. Steurer. Subsampling Mathematical Programs and Average-Case Complexity . In SODA, 2011.
[ bib | .pdf ]

 

S. Arora, B. Barak, and D. Steurer. Subexponential Algorithms for Unique Games and Related problems . In Proc. of FOCS, pages 563-572, 2010.
[ bib | powerpoint | .pdf ]

 

B. Applebaum, B. Barak, and A. Wigderson. Public Key Cryptography from Different Assumptions . In Proc. of STOC, 2010. Preliminary version as cryptology eprint report 2008/335 by Barak and Wigderson, https://eprint.iacr.org/2008/335.
[ bib | .pdf ]

 

B. Barak, I. Haitner, D. Hofheinz, and Y. Ishai. Bounded Key-Dependent Message Security . In EUROCRYPT, 2010.
[ bib | www: ]

 

S. Arora, B. Barak, M. Brunnermeier, and R. Ge. Computational Complexity and Information Asymmetry in Financial Products . In Innovations in Computer Science (ICS) conference, 2010.
[ bib | .pdf ]

 

B. Barak, A. Rao, R. Raz, R. Rosen, and R. Shaltiel. Strong Parallel Repetition Theorem for Free Projection Games . In Proceedings RANDOM 2009, page 365. Springer, 2009.
[ bib | .pdf ]

 

B. Barak, M. Hardt, and S. Kale. The Uniform Hardcore Lemma via Approximate Bregman Projections . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.
[ bib | .pdf ]

 

B. Barak and M. Mahmoody-Ghidary. Merkle Puzzles are Optimal - an O(n²) attack on key exchange from a random oracle . In Proceedings of CRYPTO '09, 2009.
[ bib | powerpoint | .pdf ]

 

B. Barak, M. Hardt, I. Haviv, A. Rao, O. Regev, and D. Steurer. Rounding Parallel Repetitions of Unique Games . In Proceedings of 49th FOCS, 2008.
[ bib | .pdf ]

 

B. Applebaum, B. Barak, and D. Xiao. On Basing Lower-Bounds for Learning on Worst-Case Assumptions . In Proceedings of 49th FOCS, 2008.
[ bib | .pdf ]

 

B. Barak, S. Goldberg, and D. Xiao. Protocols and Lower Bounds for Failure Localization in the Internet . In Proceedings of Eurocrypt 2008, 2008.
[ bib | .pdf ]

 

S. Goldberg, D. Xiao, E. Tromer, B. Barak, and J. Rexford. Path-Quality Monitoring in the Presence of Adversaries . In Proceedings of SIGMETRICS 2008, 2008.
[ bib | .pdf ]

 

B. Barak and O. Goldreich. Universal Arguments and their Applications . SIAM Journal on Computing, 38(5):1661-1694, 2008. Preliminary version in CCC' 02.
[ bib | powerpoint | .ps ]

 

B. Barak and M. Mahmoody-Ghidary. Lower bounds on signatures from symmetric primitives . In Proc. 48th Foundations of Computer Science (FOCS). IEEE, 2007.
[ bib | .pdf ]

 

B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release . In L. Libkin, editor, Proceedings of ACM PODS, pages 273-282. ACM, 2007.
[ bib | .pdf ]

 

B. Barak, M. Prabhakaran, and A. Sahai. Concurrent Non-Malleable Zero Knowledge . In Proc. 47th Foundations of Computer Science (FOCS). IEEE, 2006.
[ bib | .pdf ]

 

B. Barak, R. Impagliazzo, and A. Wigderson. Extracting Randomness Using Few Independent Sources . SIAM Journal on Computing, 36(4):1095-1118, 2006. Preliminary version in FOCS' 04.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak, Y. Lindell, and S. Vadhan. Lower bounds for non-black-box zero knowledge . J. Comput. Syst. Sci, 72(2):321-391, 2006. Preliminary version in FOCS' 03.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak and S. Halevi. An architecture for robust pseudo-random generation and Applications to /dev/random . In ACM, editor, Proc. Computing and Communication Security (CCS), 2005.
[ bib | .ps | .pdf ]

 

B. Barak and A. Sahai. How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation . In Proc. 46th FOCS. IEEE, 2005.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak, R. Canetti, Y. Lindell, R. Pass, and T. Rabin. Secure Computation Without Authentication . In Crypto '05, 2005. LNCS Volume 3621.
[ bib | link ]

 

B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors . In Proc. 37th STOC. ACM, 2005.
[ bib | .ps | .pdf ]

 

B. Barak and Y. Lindell. Strict Polynomial-Time in Simulation and Extraction . SIAM Journal on Computing, 33(4):783-818, Aug. 2004. Extended abstract appeared in STOC 2002.
[ bib | link | .ps | .pdf ]

 

B. Barak. Non-Black-Box Techniques in Cryptography. PhD thesis, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, 2004.
[ bib ]

 

B. Barak, R. Canetti, J. B. Nielsen, and R. Pass. Universally Composable Protocols with Relaxed Set-Up Assumptions . In Proc. 45th FOCS, pages 186-195. IEEE, 2004.
[ bib | .ps | .pdf ]

 

B. Barak and R. Pass. On the Possibility of One-Message Weak Zero-Knowledge . In First Theory of Cryptography Conference (TCC), 2004.
[ bib | .ps | .pdf ]

 

B. Barak, R. Shaltiel, and E. Tromer. True Random Number Generators Secure in a Changing Environment . In Workshop on Cryptographic Hardware and Embedded Systems (CHES), number 2779 in LNCS, pages 166-180, 2003.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak, R. Shaltiel, and A. Wigderson. Computational analogues of entropy . In Proc. of 7th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2003. See erratum note in abstract.
[ bib | powerpoint | .pdf ]

 

B. Barak, S. J. Ong, and S. Vadhan. Derandomization in Cryptography . In Crypto '03, 2003.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak. A Probabilistic-Time Hierarchy Theorem for ``Slightly Non-Uniform'' Algorithms . In Proc. of 6th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2002.
[ bib | .ps ]

 

B. Barak. Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model . In Proc. 43rd FOCS. IEEE, 2002. See also my thesis.
[ bib | powerpoint | .pdf ]

 

B. Barak. Delegateable Signatures . Technical report, 2001.
[ bib | .ps ]

 

B. Barak, O. Goldreich, S. Goldwasser, and Y. Lindell. Resettably-Sound Zero-Knowledge and its Applications . In Proc. 42nd FOCS, pages 116-125. IEEE, 2001.
[ bib | .ps ]

 

B. Barak. How to go beyond the black-box simulation barrier . In Proc. 42nd FOCS, pages 106-115. IEEE, 2001. See also my thesis.
[ bib | powerpoint | .pdf ]

 

B. Barak, S. Halevi, A. Herzberg, and D. Naor. Clock Synchronization with Faults and Recoveries . In Proc. of 19th ACM Principles of Distributed Computing (PODC). ACM, 2000.
[ bib | .ps ]

 

B. Barak, A. Herzberg, D. Naor, and E. Shai. The Proactive Security Toolkit and Applications . In Proc. of 6^th ACM Conference on Computer and Communications Security (CCS). ACM, 1999.
[ bib | .ps ]

This file has been generated by bibtex2html 1.74