This semester I taught another iteration of my "Introduction to Theoretical Computer Science" course, based on my textbook in process. The book was also used in University of Virgnia CS 3102 by David Evans and Nathan Brunelle. The main differences I made in the text and course since its original version were to make it … Continue reading Intro TCS recap

In an exciting manuscript just posted on the arxiv, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen prove that there is a 2-prover quantum protocol (with shared entanglement) for the halting problem. As a consequence they resolve negatively a host of open problems in quantum information theory and operator algebra, including refuting … Continue reading MIP*=RE, disproving Connes embedding conjecture.

I am in Tel Aviv Theory Fest this week - a fantastic collection of talks and workshops organized by Yuval Filmus , Gil Kalai, Ronen Eldan, and Muli Safra. It was a good chance to catch up with many friends and colleagues. In particular I met Elchanan Mossel and Subhash Khot, who asked me to … Continue reading A bet for the new decade

[The post below is by Dorit Aharonov who co-organized the wonderful school on quantum computing last week which I attended and greatly enjoyed. --Boaz] TL;DR: Last week we had a wonderful one-week intro course into the math of quantum computing at Hebrew U;  It included a one day crash course on the basics, and 7 mini-courses on math-oriented research … Continue reading A crash course on the math of quantum computing (guest post by Dorit Aharonov)

By Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever This is a lightly edited and expanded version of the following post on the OpenAI blog about the following paper. While I usually don't advertise my own papers on this blog, I thought this might be of interest to theorists, and … Continue reading Deep Double Descent (cross-posted on OpenAI blog)

[Guest post by Yossi Azar - I attended HALG once and enjoyed it quite a lot; I highly recommend people make such nominations --Boaz] Call for Invited Talk Nominations :5th Highlights of Algorithms conference (HALG 2020) ETH Zurich, June 3-5, 2020​http://2020.highlightsofalgorithms.org/ The HALG 2020 conference seeks high-quality nominations for invited talks that will highlight recent advances in algorithmic research. … Continue reading HALG 2020 call for nominations (guest post by Yossi Azar)

Harvard Computer Science is seeking a Lecturer/Assistant Director of Undergraduate Studies. A great candidate would be someone passionate about teaching and mentoring and excited to build a diverse and inclusive Undergraduate Computer Science community at Harvard. The position requires a Ph.D and is open to all areas of computer science and related fields, but of course … Continue reading Harvard opportunity: lecturing / advising position

It is often said that "we don't understand deep learning" but it is not as often clarified what is it exactly that we don't understand. In this post I try to list some of the "puzzles" of modern machine learning, from a theoretical perspective. This list is neither comprehensive nor authoritative. Indeed, I only started … Continue reading Puzzles of modern machine learning

Hi, once again it is the time of the year to advertise the Michael O. Rabin postdoctoral fellowship at Harvard, see https://toc.seas.harvard.edu/rabin-postdoc for more details. The deadline to apply is December 2, 2019. For any questions please email theory-postdoc-apply (at) seas dot harvard dot edu

(For better info, see Scott's Supreme Quantum Superiority FAQ and also his latest post on the Google paper; also this is not really an FAQ but was inspired by a question about the Google paper from a former CS 121 student) "Suppose aliens invade the earth and threaten to obliterate it in a year's time … Continue reading Boaz’s inferior classical inferiority FAQ