Computational Complexity Conference

CCC'16 - Program

Schedule   Sunday and Monday have four sessions: 9-10:30, 11-12:30, 14:30-16, and 16:30-17:{15,30}. Tuesday and Wednesday have two sessions: 9-10:30, and 11-13. All slots are 30 minutes (including 5 minutes for questions and changing speakers) except those for the best paper award winner and the invited talk. The invited talk is on Tuesday at 16:30. There is a business meeting Sunday at 17:30, and a rump session Monday at 17:45.

Workshops   Satellite workshops are held the day before the conference (May 28) in Tokyo, and for two days after the conference (June 2-3) in Kyoto. See the local arrangements page for details.

Online Proceedings   Click the title of a paper in the program to view the full paper, and the word "abstract" to show or hide the abstract. You may also download the complete Proceedings of CCC'16, as published with open access by the Leibniz International Proceedings in Informatics (LIPIcs).

Slides   Click the word "slides" in the program to see the presentations that the authors agreed to post on this website.

Saturday May 28


Sunday May 29

9:00Average-case lower bounds and satisfiability algorithms for small threshold circuits (abstract, slides)

Ruiwen Chen (University of Edinburgh), Rahul Santhanam (University of Edinburgh and University of Oxford), Srikanth Srinivasan (IIT Bombay)

9:30Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation (abstract, slides)

Ryan Williams (Stanford University)

10:00Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity (abstract, slides)

Irit Dinur (Weizmann Institute of Science), Or Meir (Haifa University)

10:30Coffee break
11:00Nearly optimal separations between communication (or query) complexity and partitions (abstract, slides)

Andris Ambainis (University of Latvia), Mārtiņš Kokainis (University of Latvia), Robin Kothari (MIT)

11:30A composition theorem for conical juntas (abstract, slides)

Mika Göös (University of Toronto), T.S. Jayram (IBM Almaden)

12:00Tight bounds for communication assisted agreement distillation (abstract, slides)

Venkatesan Guruswami (Carnegie Mellon University), Jaikumar Radhakrishnan (Tata Institute of Fundamental Research)

12:30Lunch (on your own)
14:30Pseudorandomness when the odds are against you (abstract, slides)

Sergei Artemenko (University of Haifa), Russell Impagliazzo (UC San Diego), Valentine Kabanets (Simon Fraser University), Ronen Shaltiel (University of Haifa)

15:00New non-uniform lower bounds for uniform classes (abstract, slides)

Lance Fortnow (Georgia Institute of Technology), Rahul Santhanam (University of Edinburgh and University of Oxford)

15:30Coffee break
16:30Best paper award winner

Learning algorithms from natural proofs (abstract, slides)

Marco Carmosino (UC San Diego), Russell Impagliazzo (UC San Diego), Valentine Kabanets (Simon Fraser University) and Antonina Kolokolova (Memorial University of Newfoundland)

17:45Business meeting

Monday May 30

9:00Decoding Reed-Muller codes over product sets (abstract, slides)

John Kim (Rutgers University), Swastik Kopparty (Rutgers University)

9:30Lower bounds for constant query affine-invariant LCCs and LTCs (abstract, slides)

Arnab Bhattacharyya (Indian Institute of Science), Sivakanth Gopi (Princeton University)

10:00Degree and sensitivity: tails of two distributions (abstract, slides)

Parikshit Gopalan (Microsoft Research), Rocco Servedio (Columbia University), Avi Wigderson (Institute for Advanced Study)

10:30Coffee break
11:00New hardness results for graph and hypergraph colorings (abstract, slides)

Joshua Brakensiek (Carnegie Mellon University), Venkatesan Guruswami (Carnegie Mellon University)

11:30Invariance principle on the slice (abstract)

Yuval Filmus (Technion), Guy Kindler (Hebrew University of Jerusalem), Elchanan Mossel (Pennsylvania University and UC Berkeley), Karl Wimmer (Duquesne University)


Harmonicity and Invariance on Slices of the Boolean Cube (abstract, slides)

Yuval Filmus (Technion), Elchanan Mossel (Pennsylvania University and UC Berkeley)

12:00On the sum-of-squares degree of symmetric quadratic functions (abstract, slides)

Troy Lee (Nanyang Technological University), Anupam Prakash (Nanyang Technological University), Ronald de Wolf (CWI and University of Amsterdam), Henry Yuen (MIT)

12:30Lunch (on your own)
14:30Limits of minimum circuit size problem as oracle (abstract, slides)

Shuichi Hirahara (University of Tokyo), Osamu Watanabe (Tokyo Institute of Technology)

15:00New extractors for interleaved sources (abstract)

Eshan Chattopadhyay (UT Austin), David Zuckerman (UT Austin)

15:30New characterizations in turnstile streams with applications (abstract, slides)

Yuqing Ai (Tsinghua University), Wei Hu (Tsinghua University), Yi Li (Facebook Inc.), David P. Woodruff (IBM Almaden)

16:00Coffee break
16:30Invited talk

Evolution and computation

Nisheeth Vishnoi (EPFL)

17:30Non-malleable extractors - new tools and improved constructions (abstract, slides)

Gil Cohen (California Institute of Technology)

18:30Rump session

Tuesday May 31

9:00Tight SoS-degree bounds for approximate Nash equilibria (abstract)

Aram Harrow (MIT), Anand Natarajan (MIT), Xiaodi Wu (University of Oregon)

9:30Understanding PPA-completeness (abstract)

Xiaotie Deng (Shanghai Jiao Tong University), Jack Edmonds, Zhe Feng (Shanghai Jiao Tong University), Zhengyang Liu (Shanghai Jiao Tong University), Qi Qi (Hong Kong University of Science and Technology), Zeying Xu (Shanghai Jiao Tong University)

10:00Polynomial bounds for decoupling, with applications (abstract, slides)

Ryan O'Donnell (Carnegie Mellon University), Yu Zhao (Carnegie Mellon University)

10:30Coffee break
11:00Polynomials, quantum query complexity, and Grothendieck's inequality (abstract, slides)

Scott Aaronson (MIT), Andris Ambainis (University of Latvia), Jānis Iraids (University of Latvia), Mārtiņš Kokainis (University of Latvia), Juris Smotrovs (University of Latvia)

11:30Sculpting quantum speedups (abstract)

Scott Aaronson (MIT), Shalev Ben-David (MIT)

12:00A linear time algorithm for quantum 2-SAT (abstract, slides)

Niel de Beaudrap (University of Oxford), Sevag Gharibian (Virginia Commonwealth University)

12:30Complexity classification of two-qubit commuting hamiltonians (abstract, slides)

Adam Bouland (MIT), Laura Mancinska (National University of Singapore), Xue Zhang (MIT)

13:00Lunch and Excursion

Wednesday June 1

9:00Identity testing for constant-width, and commutative, read-once oblivious ABPs (abstract, slides)

Rohit Gurjar (IIT Kanpur), Arpita Korwar (IIT Kanpur), Nitin Saxena (IIT Kanpur)

9:30Identity testing and lower bounds for read-k oblivious algebraic branching programs (abstract, slides)

Matthew Anderson (Union College), Michael A. Forbes (Princeton University), Ramprasad Saptharishi (Tel Aviv University), Amir Shpilka (Tel Aviv University), Ben Lee Volk (Tel Aviv University)

10:00Reconstruction of real depth-3 circuits with top fan-in 2 (abstract)

Gaurav Sinha (California Institute of Technology)

10:30Coffee break
11:00Proof complexity lower bounds from algebraic circuit complexity (abstract, slides)

Michael A. Forbes (Princeton University), Amir Shpilka (Tel Aviv University), Iddo Tzameret (Royal Holloway, University of London), Avi Wigderson (Institute for Advanced Study)

11:30Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity (abstract, slides)

Michael A. Forbes (Princeton University), Mrinal Kumar (Rutgers University), Ramprasad Saptharishi (Tel Aviv University)

12:00Arithmetic circuits with locally low algebraic rank (abstract, slides)

Mrinal Kumar (Rutgers University), Shubhangi Saraf (Rutgers University)

12:30Sums of products of polynomials in few variables : lower bounds and polynomial identity testing (abstract, slides)

Mrinal Kumar (Rutgers University), Shubhangi Saraf (Rutgers University)

13:00End of the conference

Organized by:

Computational Complexity Foundation Inc.

Exploring the Limits of Computation (ELC), KAKENHI Japan

In Cooperation with:


Sponsored by:

Microsoft Research