CCC 2014

I'm returning from the 2014 IEEE Conference on Computational Complexity in Vancouver, unfortunately missing the last day. Several very nice talks including a wonderful survey by Shubhangi Saraf on recent problems on lower bounds in algebraic circuits (addition and multiplication gates). In short, the interesting case is depth-4 algebraic circuits with bottom fan-in √n computing homogeneous polynomials. Kayal, Saha and Saptharishi showed a 2^{Ω(√n log n)} lower bound. Any improvement (changing the Ω to a ω) would separate VNP from VP (the algebraic version of the P v NP problem), or equivalently show the permanent cannot be computed by poly-size algebraic circuits.

At the business meeting, we discussed the plans for independence from IEEE. 60% of 189 voted for independence with open access as the main reason stated. There has been great support from the community both in volunteers to help with an independent conference and money ($42K) raised to get started. Future proceedings will likely be in the Dagstuhl LIPIcs series. Timing and a new conference name are a few of the many issues still to be worked out. Whether or not you support independence, the conference organizers, particularly steering committee chair (and my former student) Dieter van Melkebeek, are doing a strong job coordinating the efforts.

Other highlights from the business meeting.

• 29 accepted papers out of 94 submissions. A good number.
• There was no best paper. The best student paper went to Alexander Belov for Quantum Algorithms for Learning Symmetric Juntas.
• 66 registered participants including 29 students. A bit low probably due to the proximity to STOC in time but not distance.
• 2015 CCC will be June 17-19 as part of the FCRC conference in Portland, Oregon.
• There were three good bids for the 2016 CCC from Tokyo, Saarbrücken and Riga. Tokyo was the overwhelming winner.
• CCC 2017 may be part of a federated theory conference including STOC, EC and SPAA.