Thursday, June 02, 2016

CCC 2016

Earlier this week I attended the 31st Computational Complexity Conference in Tokyo. I've been to thirty of these meetings, missing only the 2012 conference in Porto. Eric Allender has attended them all.

The conference had a 130 participants with fewer women than you can count on one hand and 26 made it from the States. There were 34 accepted papers out of 91 submitted.

The proceedings are fully open access though the Dagstuhl LIPICS series, including the paper by Rahul Santhanam and myself that I presented at the meeting. The best paper by Marco Carmosino, Russell Impagliazzo, Valentine Kabanets and  Antonina Kolokolova drew a surprising strong connection between natural proofs and learning theory. In one of my favorite other talks, John Kim and Swastik Kopparty show how to decode Reed-Muller codes over an arbitrary product set instead of a structured field.

The German government will in the future no longer support LIPICS due to EU rules to prevent unfair competition with the commercial publishers. (Don't shoot the messenger) LIPICS will continue, the conferences will have to spend a little more to use them.

Next year's conference will be in Riga, Latvia July 6-9 right before ICALP in Warsaw. The 2018 meeting is likely to take place closely located to STOC in southern California.

Osamu Watanabe put together this slide show for the conference reception featuring pictures of attendees of the Complexity Conference through the ages, including the authors of this blog.

Peter van Emde Boas forwarded the call for papers and initial letters for the very first conference, originally called Structure in Complexity Theory.

1 comment:

  1. Commercial publishers have too much influence on European governments. They almost banned Google News by passing a law that forced aggregators to pay to link or display excerpts and another one which forced Google News to display them, but Google threatened to pull completely out of the German market at which point the publishers voluntarily allowed Google to display them without paying. However the Spanish law does not even allow the publishers to not to charge aggregators so Google News was closed in Spain and as a result Spanish publishers lost a significant amount of traffic to their sites.