(Unrelated update: thanks to Shachar Lovett the posting form for cstheory-jobs.org is back online. This is a great place for both posting and checking ads for academic positions in TCS.) 2018 Theory Fest: Call for Plenary Talk Suggestions STOC 2018 will be part of an expanded 50th anniversary celebration and  Theory Fest (http://acm-stoc.org/stoc2018/ ) that will also … Continue reading STOC 2018 Highlighted Plenary Talks: Call for Nominations

Avi Wigderson is one of the most prolific and creative theoretical computer scientists (in fact, he is one of the most prolific and creative scientists, period). Over the last several years, Avi had worked hard into distilling his vast knowledge of theoretical computer science and neighboring fields into a book surveying TCS, and in particular … Continue reading Must-read book by Avi Wigderson

I just came back from the Simons Foudnations annual meeting for Mathematical and Physical Sciences. Unfortunately, due to a flight delay I missed many of the talks, but the ones I did see were fascinating. One talk in particular caught my attention: Leonardo Rastelli's talk on "The Superconformal Bootstrap" who discussed the work of the Simons … Continue reading Doing Theoretical Physics with Semidefinite Programming

Following the Harvey Weinstein scandal, I'd like to believe that the academic environment at large, and theoretical computer science in particular, is a much better environment than Hollywood. But we would be misleading ourselves to think that we are completely without our issues. This story can be an opportunity for each of us, men and … Continue reading Do we have TCS “Harvey Weinsteins”?

The call for paper for STOC is up, see  http://acm-stoc.org/stoc2018/ and  here. The deadline is November 3, 2017 4:59pm Eastern Daylight Time. STOC 2018 will again be a Theory Fest and also celebrate the 50th anniversary of STOC. As part of the "retro" atmosphere, the STOC PC also asks submissions to be sent by mail in … Continue reading STOC 2018 CFP

[This is a guest blog post on behalf of MSR, communicated to me by Yuval Peres. Like everyone who knew Michael, I was incredibly shocked and saddened by the news. I had relatively few interactions with Michael, but he has made a deep impression. I was always hoping we'd get a chance to collaborate , … Continue reading Michael Cohen

This year Harvard's Center for Mathematical Sciences and Applications is running a special year on combinatorics and complexity. We have many long-term visitors and postdocs, and several events that theoretical computer scientists might wish to take part in, including four workshops: Additive Combinatorics (10/2/2017-10/6/2017); Algebraic Methods in Combinatorics (11/13/2017 -11/17/2017); Probabilistic Methods in Combinatorics (2/5/2018-2/9/2018); and Coding and Information … Continue reading Special year on combinatorics and complexity

Fall is coming, and with it the annual holiday of FOCS. FOCS 2017 will be held at Berkeley from Oct 15-17, with a day of workshops/tutorials on Oct 14th. Registrations are now open at http://focs17.simons.berkeley.edu/registration.html Early registration deadline for the conference is Sept 25th, 2017. Speaking of workshops, there is one way to guarantee that … Continue reading FOCS 2017: Registration and call for workshops

One of the mysteries of computation is that, as far as we can tell, the time complexity of many natural computational problems is either $latex poly(n)$ (with a small exponent, such as $latex 1,2$ or $latex 3$) or at least $latex 2^{\Omega(n)}$ (with a not too small coefficient in the exponent). This is perhaps the … Continue reading The intermediate complexity conjecture