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)

[Guest post by Moshe Babaioff --Boaz] "Highlights Beyond EC" Session at EC 2019: Call for Nominations Committee: Mohammad Akbarpour, Moshe Babaioff, Shengwu Li and Ariel Procaccia Following a new tradition started last year, the 2019 ACM Conference on Economics and Computation (EC’19) will host a special session highlighting some of the best work in economics … Continue reading Highlights beyond EC: Call for nominations

[Guest post by Piotr Sankowski --Boaz] Call for Nominations - 4th Highlights of Algorithms conference (HALG 2019) Copenhagen, June 14-16, 2019 http://www.halgdiku.dk/ The HALG 2019 conference seeks high-quality nominations for invited talks that will highlight recent advances in algorithmic research. Similarly to previous years, there are two categories of invited talks: A. survey (60 minutes): a … Continue reading HALG 2019 Call for nominations

Guest post by Shuchi Chawla One of the best ways to serve the US-based TCS community is to take up a position at the NSF. Beginning as early as 2019, NSF/CCF is seeking at least one program director for the Algorithmic Foundations core program. This is a rotator position, which is generally two or three years in … Continue reading Be a program director at NSF!

[Message from Adi Rosen --Boaz] This is a kind reminder that the deadline for the early rate registration fees for FOCS 2018 is this Sunday, September 9, 2018. =================================== FOCS 2018 - Second Call for Participation =================================== https://www.irif.fr/~focs2018/ The 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018) will take place in Paris, France, … Continue reading FOCS early registration deadline