This fall I will be teaching a graduate seminar on the Sum of Squares algorithm. Actually, it will be two "sister seminars". In the Cambridge/Boston area, I (with possibly some guest lectures by Pablo Parrilo) will be teaching the course on Fridays 10am-1pm, alternating between Harvard and MIT. In Princeton, David Steurer and Pravesh Kothari … Continue reading Proofs, beliefs and algorithms through the lens of Sum of Squares

Following the proud tradition of previous STOC/FOCS conferences, FOCS'16 will also have a (half) day of workshop/tutorials on Saturday, October 8th, right before the conference starts. You are invited to submit your proposal of workshop or tutorial by August 31st; see details here. In short: you just need to propose an exciting theme and arrange the speakers. We will … Continue reading Call for proposals for FOCS’16 workshop/tutorial (half-)day

(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