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