Now that the important event of the STOC deadline has passed, we can talk about trivial matters such as the future of the free world (but of course, like a broken record, I will come back to talking about sum of squares by the end of the post). A priori predicting the result of the … Continue reading Post-deadline diversion: Election predictions

As mentioned before on this blog,   STOC 2017 will be part of an expanded “Theory Fest” (http://acm-stoc.org/stoc2017/) which is being planned by a small committee (Sanjeev Arora, Paul Beame, Avrim Blum, and Ryan Williams, as well as SIGACT chair Michael Mitzenmacher and STOC’17 PC chair Valerie King).   One component of Theory Fest would be a series of … Continue reading Theory Fest short presentations – call for suggestions

I hope to see many readers of this blog in person tomorrow for the workshop in honor of Avi Wigderson 60th birthday (Wed-Sat), which will feature a collection of great speakers talking on a variety of areas in theoretical computer science and mathematics. But, if you can't make it in person, the talks will be streamed … Continue reading Live from Princeton, NJ: Avi60

(see also here) STOC Theory Fest 2017 (Montreal June 19-23) Sanjeev Arora, Paul Beame, Avrim Blum, Ryan Williams   SIGACT Chair Michael Mitzenmacher announced at the STOC’16 business meeting that starting in 2017, STOC will turn into a 5-day event, a Theory Fest. This idea was discussed at some length in a special session at … Continue reading TheoryFest 2017 – guest post by Sanjeev Arora

STOC 2016 just ended and it included many great results with one highlight of course being Laci Babai’s quasipolynomial time algorithm for graph isomorphism. But today I wanted to mention another paper that I found quite interesting and reminded me of the famous Tolstoy quote that Happy families are all alike; every unhappy family is unhappy … Continue reading Area Laws, Reed Muller Codes and Tolstoy

On October 5-8 (right before FOCS 2016) there will be a workshop in Princeton in honor of Avi Wigderson's 60th birthday. Avi is one of the most productive, generous and collaborative researchers in our community (see mosiac below of his collaborators). So, it's not surprising that we were able to get a great lineup of speakers to … Continue reading Avi Wigderson 60th celebration

By Boaz Barak and Omer Reingold Yesterday Hillary Clinton became the first woman to be (presumptively) nominated for president by a major party. But in the eyes of many, the Republican Party was first to make history this election season by breaking the "qualifications ceiling" (or perhaps floor) in their own (presumptive) nomination. Though already predicted in 2000 by … Continue reading Politics on technical blogs

The last few weeks have seen amazing results in additive combinatorics, where following a breakthrough by Croot, Lev and Pach, several longstanding open questions have been resolved using short simple proofs. I haven’t been following this progress, but fortunately Bobby Kleinberg gave an excellent talk yesterday in our reading group about some of these works, … Continue reading Yet another post on a.p. free set bounds

Actually, not really... Northwestern University held a workshop on semidefinite programming hierarchies and sum of squares.  Videos of the talks by Prasad Raghavendra, David Steurer and myself are available from the link above. The content to unicorns ratio in Prasad and David's talks is much higher ☺

Tomorrow, Wednesday May 25, is the international Towel Day in honor of Douglas Adams, author of the 5-book trilogy "The hitchhiker's Guide to the Galaxy". In his book (and his prior 1978 radio series) Adams gave a nice illustration of computational complexity and non uniform computation in his story about the "deep thought" computer who took 7.5 million … Continue reading Happy towel day