[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)

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)

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

[Guest post by Sandy Irani; see also the new website http://safetoc.org for more information on this initiative. --Boaz ] Update and follow-up on the Safe ToC initiative:  Last year, a group of us served on an ad hoc committee to combat harassment and discrimination in the Theory of Computing community.  In our report, we suggested … Continue reading Update on the Safe ToC initiative (guest post by Sandy Irani)

In a recent breakthrough, Hao Huang gave a 6 page paper proving the longstanding sensitivity conjecture. (Hat tip, Scott Aaronson and Gil Kalai. See this stackexchange post and this paper of Avishai for some links to the literature on this.) The proof is beautiful and simple. I will write a few words here, but it … Continue reading Sensitivity conjecture proved!

[Guest post by Virgi Vassilevska Williams on the TCS women program at STOC. In particular the TCS Women Spotlight workshop has a great program and is open to all. --Boaz] Dear all, The TCS Women 2019 program is finalized: https://sigact.org/tcswomen/tcs-women-2019/. Here are some details: On June 23rd, we have our TCS Women Spotlight workshop from 2 … Continue reading TCS Women at STOC (guest post by Virginia Williams)