(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

Today we witnessed an exciting moment for privacy, CS theory, and many friends and contributors of this blog. The definition of differential privacy, first articulated in a TCC paper just 10 short years ago, became a top-level feature of iOS, announced today at the Apple keynote address. Check this out for yourself: You may be intrigued as … Continue reading Differential Privacy in Your Pocket

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

LifeHacker is a website dedicated to tricks, especially technology related, to make people more efficient or productive. The signal to noise ratio in that website is not particularly high, but I think it is a good idea to share tricks that can save time and effort. In particular, are there tools or tricks that made a difference in your … Continue reading Theory Life-Hacks

Aleksander Madry asks me to announce that registration for the Highlights of Algorithms conference he posted about is open. The registration link is http://highlightsofalgorithms.org/registration/. (Early registration is due April 30.) Also, the preliminary program is available at http://highlightsofalgorithms.org/program/. The program is packed with 28 invited talks and with even a larger number of short contributions. Those interested in attending … Continue reading Highlights of Algorithms registration