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

See Scott Aaronson's blog. It seems like researchers in John Martinis's group at Google might have managed to demonstrate that a quantum computer can produce samples passing a certain statistical test for which we know no efficient classical algorithm to do so. Of course I can't help but posting again the fake nytimes headline I … Continue reading Is quantum supremacy here?