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?

[The following is a guest post by Benny Applebaum announcing a new conference on information theoretic cryptography - an area with both beautiful math and important applications. --Boaz] Deal friends,We are happy to announce the birth of a new conference on Information-Theoretic Cryptography (ITC). Information-theoretic cryptography studies security in the presence of computationally unbounded adversaries … Continue reading Information-Theoretic Cryptography (ITC) conference (guest post by Benny Applebaum)

[Guest post by David Steurer - seems like a great opportunity! --Boaz] The Swiss Winter School on Lower Bounds and Communication Complexity (10-14 February 2020, https://theory.epfl.ch/WinterSchool2020/ ) is the first in a series of annual winter schools in Theoretical Computer Science jointly organized by EPFL and ETH Zurich. The goal of the school is to … Continue reading Swiss TCS winter school (guest post by David Steurer)

Microsoft Powerpoint has a surprisingly powerful equation editor, which also allows to use latex macros such as \alpha to get $latex \alpha$. I've blogged about the equation editor before but one pet peeve of mine was that I like to have my math in a different color, but never found a way to do this … Continue reading Make equations blue in powerpoint