Quick Links:

ML Foundations | CS 229br | Intro TCS | Crypto | Complexity

I am a professor of Computer Science at Harvard University, and a member of the Harvard SEAS Theory of Computing group. Previously, I was a principal researcher at Microsoft Research New England, and before that I was an associate professor (with tenure) at Princeton University’s Computer Science department. I hold a Ph.D from the Weizmann Institute of Science, and was a postdoctoral fellow at the Institute for Advanced Study in Princeton.

I am a theoretical computer scientist, interested in computational complexity, algorithms, cryptography, quantum computing and particularly the foundations of machine learning.

See also my curriculum vitae and brief bio. I also occasionally blog and toot or tweet.

DUS: I am co director of undergraduate studies (DUS) of Computer Science at Harvard together with Prof. Stephen Chong. Please email cs-dus@seas.harvard.edu for any DUS related matters. For information about the Computer Science concentration at Harvard see the page csadvising.seas.harvard.edu. See also my contact information and office hours.

Current activities: Member of the editorial board of the Theory of Computing Journal (ToC) and the Electronic Colloquium of Computational Complexity. I am a member of the scientific board of the Simons Institute for the Theory of Computing. I am a co organizer of the Harvard Machine Learning Foundations seminar and a steering committee member and associate faculty of the Kempner Institute for the Study of Natural and Artificial Intelligence. Board member and co organizer of Addis Coder as well as Jam Coders. I am also a member of the advisory board of the wonderful Quanta magazine. See my CV for past activities.

Current students: Gustaf Ahdritz, Depen Morwani, Rosie Zhao, Natalie Abreu

Former students: Yueqi Sheng, Sharon Goldberg (co advised with Jennifer Rexford), David Xiao (co advised with Avi Wigderson), Mohammad Mahmoody, Moritz Hardt, Zhixian Lei, Preetum Nakkiran (co-advised with Madhu Sudan), Yamini Bansal (co-advised with David Cox), Chi-Ning Chou, Prayaag Venkat, Gal Kaplun.

Current postdocs: Nikhil Vyas, Samy Jelassi. I also work closely with Kempner Institute research fellows

Former postdocs: Benny Applebaum, Thomas Holenstein, Guy Rothblum, Tselil Schramm.

Former interns: Moritz Hardt, Jonah Sherman, Yuan Zhou, Li-Yang Tan , Aaron Sidford, Aaron Potechin, Pravesh Kothari, Sam Hopkins.

Funding: I am currently supported by a Simons Investigator Fellowship, NSF grant DMS-2134157, DARPA grant W911NF2010021,and DOE grant DE-SC0022199. I am also grateful for support from Oracle Labs and past support by the NSF, as well as the Packard and Sloan foundations and the BSF.

Want to work with me? I am interested in machine learning foundations and theoretical CS. In particular see the opportunities sections of the ML foundations and the Kempner Institute websites. You can see this page for how to apply for graduate studies in computer science; we also have a new Quantum Science and Engineering program. Please do not email me with your resume - if you are interested in working with me, you can indicate this on your application and it will get to me. We also have some postdoc positions in both the foundations of Machine Learning and theoretical CS. I typically announce any such positions on my blog or Twitter, and post TCS positions on the TCS jobs page. ...

Personal: I am married to Ravit Barak and father to Alma and Goren.

News

• Starting January 2024 I will be on a one-year leave from Harvard 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:

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.

• Some blog posts on AI and AI safety (see more here ):

  • AI will change the world, but won’t take it over by playing “3-dimensional chess”
  • Thoughts on AI safety
  • Reflections on “making the atomic bomb”
  • The shape of AGI: Cartoons and back of the envelope

• The uneasy relationship between deep learning and statistics - blog post. See also my deep learning foundations seminar.

• Work with what you’ve got, Nature Physics, January 21. (About experiments running the QAOA algorithm on near-term intermediate-scale noisy quantum devices (NISQ).

• The different forms of quantum computing skepticsm - blog post. See also pdf version

• The Complexity of Public-Key Cryptography - survey/tutorial on the computational assumptions landscape of cryptogrpahy. Written in honor of Oded Goldreich’s 60th birthday.

• Bayesianism, frequentism, and the planted clique, or do algorithms believe in unicorns?, April 2016. See also blog post on windows of theory blog and video of a talk at Northwestern.

• Men in Computer Science - blog post, August 2017.

• Hopes, Fears, and Software Obfuscation, Communications of the ACM, March 2016. See also preprint version and video of short interview.

• Speaking about unspeakables, Harvard Lectures that Last 2016, February 2016, see also video of lecture.

• Structure vs Combinatorics in Computational Complexity, Windows on Theory blog, October 2013. See also adapted version in the bulletin of the European Association for Theoretical Computer Science.

• Truth vs. Proof - the Unique Games Conjecture and Feige’s Hypothesis, Windows on Theory blog, July 2012. See also adapted version in logic in computer science column of the bulletin of the European Association for Theoretical Computer Science.

• My first publication: tip for Ultima IV game in Commodore Magazine, June 1988.

Teaching

All teaching

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

• Harvard CS229br: Foundations of Deep Learning, Spring 2021, Spring 2023

• Harvard CS121: Introduction to Theoretical Computer Science - Fall 2019, Fall 2018, Fall 2017, Fall 2022.

• Harvard CS127: Cryptography, Fall 2021, Spring 2020, Spring 2018, Spring 2016.

• Harvard CS229r: Physics and Computation Seminar, Fall 2018.

• Harvard CS229r / MIT 6.S898: Proofs, beliefs and algorithms through the lens of Sum of Squares - Fall 2016 - graduate course/seminar on the Sum of Squares algorithm.

• Addis Coder -summer course on algorithms and coding for high school students in Ethiopia. See also Jam Coders - a version of this course in Jamaica.

• Princeton COS 522 - (graduate) Computational Complexity - Spring 2009

• Princeton COS 598D - Mathematical Methods in Theoretical Computer Science - Spring 2008

Contact

Office hours

	Email: . For Harvard related mails (apart from DUS), please use Any emails related to my role as DUS should be sent to cs-dus@seas.harvard.edu.
	Please use or 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) dummy 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: Emma Hammack, , erhammack@g.harvard.edu
	Phone: (617) 496-1004 (I prefer email)