News

  • I am currently on leave from Harvard and at OpenAI

  • See the Harvard ML foundations group website for our seminar and other activities in the foundations of machine learning. In particular the opportunities section there contains information about positions for undergraduate students, graduate students, postdocs, and faculty.

Selected Publications

All publications

Below are some of my papers, click here to see all my publications:

generated by bibbase.org
  yes (18)
Trading Inference-Time Compute for Adversarial Robustness. Zaremba, W.; Nitishinskaya, E.; Barak, B.; Lin, S.; Toyer, S.; Yu, Y.; Dias, R.; Wallace, E.; Xiao, K.; Heidecke, J.; and Glaese, A. 2025.
Trading Inference-Time Compute for Adversarial Robustness [link]Paper   link   bibtex   3 downloads  
Deliberative Alignment: Reasoning Enables Safer Language Models. Guan, M. Y.; Joglekar, M.; Wallace, E.; Jain, S.; Barak, B.; Helyar, A.; Dias, R.; Vallone, A.; Ren, H.; Wei, J.; Chung, H. W.; Toyer, S.; Heidecke, J.; Beutel, A.; and Glaese, A. 2025.
Deliberative Alignment: Reasoning Enables Safer Language Models [link]Paper   link   bibtex   1 download  
Watermarks in the Sand: Impossibility of Strong Watermarking for Large Language Models. Zhang, H.; Edelman, B. L.; Francati, D.; Venturi, D.; Ateniese, G.; and Barak, B. ICML 2024, abs/2311.04378. 2024.
Watermarks in the Sand: Impossibility of Strong Watermarking for Large Language Models [link]Paper   Watermarks in the Sand: Impossibility of Strong Watermarking for Large Language Models [link] blog   Watermarks in the Sand: Impossibility of Strong Watermarking for Large Language Models [link] paper   doi   link   bibtex  
Scaling Data-Constrained Language Models. Muennighoff, N.; Rush, A. M.; Barak, B.; Scao, T. L.; Piktus, A.; Tazi, N.; Pyysalo, S.; Wolf, T.; and Raffel, C. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. Outstanding Main Track Paper award, Runner-Up
Scaling Data-Constrained Language Models [link] paper   link   bibtex   18 downloads  
On Provable Copyright Protection for Generative Models. Vyas, N.; Kakade, S. M.; and Barak, B. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202, of Proceedings of Machine Learning Research, pages 35277–35299, 2023. PMLR
On Provable Copyright Protection for Generative Models [link]Paper   On Provable Copyright Protection for Generative Models [link] paper   On Provable Copyright Protection for Generative Models [link] blog   link   bibtex   7 downloads  
Deep Double Descent: Where Bigger Models and More Data Hurt. Nakkiran, P.; Kaplun, G.; Bansal, Y.; Yang, T.; Barak, B.; and Sutskever, I. In ICLR 2020, 2020. Also appeared in Journal of Statistical Mechanics, 2021
Deep Double Descent: Where Bigger Models and More Data Hurt [link]Paper   Deep Double Descent: Where Bigger Models and More Data Hurt [link] blog   link   bibtex   31 downloads  
SGD on Neural Networks Learns Functions of Increasing Complexity. Nakkiran, P.; Kaplun, G.; Kalimeris, D.; Yang, T.; Edelman, B. L.; Zhang, F.; and Barak, B. In NeurIPS 2019 (spotlight), volume abs/1905.11604, 2019.
SGD on Neural Networks Learns Functions of Increasing Complexity [link]Paper   link   bibtex   13 downloads  
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). Barak, B.; Brakerski, Z.; Komargodski, I.; and Kothari, P. In EUROCRYPT, 2018.
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) [link] paper   link   bibtex   7 downloads  
Quantum entanglement, sum of squares, and the log rank conjecture. Barak, B.; Kothari, P.; and Steurer, D. In STOC, 2017.
Quantum entanglement, sum of squares, and the log rank conjecture [link] paper   link   bibtex   16 downloads  
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Barak, B.; Hopkins, S. B.; Kelner, J. A.; Kothari, P. K.; Moitra, A.; and Potechin, A. SIAM J. Comput., 48(2): 687–735. 2019. Special issue for FOCS 2016
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem [link] paper   doi   link   bibtex   10 downloads  
A zero-knowledge protocol for nuclear warhead verification. Glaser, A.; Barak, B.; and Goldston, R. J. Nature, 510: 497-502. 2014. See also article by R. Stone (Science, June 2014)
A zero-knowledge protocol for nuclear warhead verification [link] paper   link   bibtex   8 downloads  
Fractional Sylvester–Gallai theorems. Barak, B.; Dvir, Z.; Wigderson, A.; and Yehudayoff, A. 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''
Fractional Sylvester–Gallai theorems [pdf] paper   link   bibtex   5 downloads  
Computational complexity and information asymmetry in financial products. Arora, S.; Barak, B.; Brunnermeier, M.; and Ge, R. Commun. ACM, 54(5): 101-107. 2011.
Computational complexity and information asymmetry in financial products [link] paper   link   bibtex   10 downloads  
Subexponential Algorithms for Unique Games and Related problems. Arora, S.; Barak, B.; and Steurer, D. In Proc. of FOCS, pages 563–572, 2010.
Subexponential Algorithms for Unique Games and Related problems [pdf] paper   link   bibtex   7 downloads  
How to Compress Interactive Communication. Barak, B.; Braverman, M.; Chen, X.; and Rao, A. SIAM J. Comput., 42(3): 1327-1363. 2013. Preliminary version in STOC 2010
How to Compress Interactive Communication [pdf] paper   link   bibtex   2 downloads  
2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction. Barak, B.; Rao, A.; Shaltiel, R.; and Wigderson, A. Annals of Mathematics, 176(3): 1483–1543. 2012. Preliminary version in STOC '06
2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction [pdf] paper   link   bibtex   5 downloads  
How to go beyond the black-box simulation barrier. Barak, B. In Proceedings of FOCS '01, pages 106–115, 2001. Winner, FOCS 2021 Test of Time Award
How to go beyond the black-box simulation barrier [pdf] paper   link   bibtex   24 downloads  
On the (im)possibility of obfuscating programs. Barak, B.; Goldreich, O.; Impagliazzo, R.; Rudich, S.; Sahai, A.; Vadhan, S. P.; and Yang, K. J. ACM, 59(2): 6. 2012. Preliminary version in CRYPTO 2001
On the (im)possibility of obfuscating programs [pdf] paper   link   bibtex   23 downloads  

Writing

All Writing

I wrote a graduate textbook with Sanjeev Arora: Computational Complexity: A Modern Approach. I am currently writing an undergraduate textbook: Introduction to Theoretical Computer Science. I also wrote extensive notes on an intense introduction to cryptography and on the sum of squares algorithm (with David Steurer). I occasionally blog on the Windows on Theory blog and Tweet.

Some surveys and essays I wrote are below. See here for more of my less technical writing.

Teaching

All teaching

Here are some of the courses / lectures I (Co) taught (see here for all courses):

Contact

Office hours

Email: b@boazbarak.org . For Harvard related mails (apart from DUS), please use boaz@seas.harvard.edu Any emails related to my role as DUS should be sent to cs-dus@seas.harvard.edu.
Please use reference@boazbarak.org or referee@boazbarak.org for reference letter or manuscript review requests respectively. (emails to these addresses are forwarded to my main inbox, but are also tagged appropriately so I don't lose track of them. Emails to the reference address are also forwarded to my faculty coordinator.)

Upcoming office hours: (see all hours and schedule appointments)

  • Loading...

Physical Location: Office 3.309 in Harvard Allston SEC complex, 150 Western Avenue, Boston, MA.
Mailing Address: Professor Boaz Barak, Harvard University SEAS, SEC Building Office 3.309, 150 Western Avenue, Boston, MA 02134
Administrative assistant: Kristin Maple , kmaple@seas.harvard.edu
Phone: (617) 496-1004 (I prefer email)