Computational Complexity Conference

CCC'17 - Program

Schedule   The slots for contributed talks are 30 minutes (including 5 minutes for questions and changing speakers). In addition there are tutorial sessions by Avi Wigderson on Thursday, Friday, and Saturday, 10:30-12:30. There is also a reception Wednesday at 18:00, a business meeting Thursday at 20:30, a rump session Friday at 18:15, and an excursion Saturday at 16:30.

Venue   All activities except the excursion and banquet take place at the University of Latvia, Raina bulv. 19. The talks are in Auditorium 13 on the 3rd floor; the business meeting and rump session are in Auditorium 16 on the same floor. The banquet takes place in restaurant Andaluzijas suns, Elizabetes iela 83.

Online Proceedings   A preliminary version of the proceedings is openly accessible via LIPIcs.

Wednesday July 5

18:00-20:00Reception

Thursday July 6

8:30 Random resolution refutations (abstract)

Pavel Pudlák (Czech Academy of Sciences), Neil Thapen (Czech Academy of Sciences)

9:00 Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases (abstract)

Massimo Lauria (Sapienza - Universita di Roma), Jakob Nordstrom (KTH Royal Institute of Technology)

9:30 Representations of monotone Boolean functions by linear programs (abstract)

Mateus De Oliveira Oliveira (University of Bergen), Pavel Pudlák (Czech Academy of Sciences)

10:00Coffee break
10:30 Tutorial (part 1)
Operator scaling: theory, applications and connections (abstract)

Avi Wigderson (Institute for Advanced Study)

12:30Lunch
14:30 A note on amortized branching program complexity (abstract)

Aaron Potechin (Institute for Advanced Study)

15:00 Derandomizing isolation in space-bounded settings (abstract)

Dieter van Melkebeek (University of Wisconsin-Madison), Gautam Prakriya (University of Wisconsin-Madison)

15:30 The computational complexity of integer programming with alternations (abstract)

Danny Nguyen (UCLA), Igor Pak (UCLA)

16:00Coffee break
16:30 On the average-case complexity of MCSP and its variants (abstract)

Shuichi Hirahara (University of Tokyo), Rahul Santhanam (University of Oxford)

17:00 Easiness amplification and uniform circuit lower bounds (abstract)

Cody Murray (MIT), Ryan Williams (MIT)

17:30 PPSZ for general k-SAT — making Hertli’s analysis simpler and 3-SAT faster (abstract)

Dominik Scheder (Shanghai Jiaotong University), John Steinberger (Tsinghua University)

18:00Break
20:30Business meeting

Friday July 7

8:30 Noise stability is computable and approximately low-dimensional (abstract)

Anindya De (Northwestern University), Elchanan Mossel (MIT), Joe Neeman (UT Austin)

9:00 From weak to strong LP gaps for all CSPs (abstract)

Mrinalkanti Ghosh (TTI Chicago), Madhur Tulsiani (TTI Chicago)

9:30 Query-to-communication lifting for P^NP (abstract)

Mika Göös (Harvard University), Pritish Kamath (MIT), Toniann Pitassi (University of Toronto), Thomas Watson (University of Memphis)

10:00Coffee break
10:30 Tutorial (part 2)
Operator scaling: theory, applications and connections (abstract)

Avi Wigderson (Institute for Advanced Study)

12:30Lunch
14:30 Improved bounds for quantified derandomization of constant-depth circuits and polynomials (abstract)

Roei Tell (Weizmann Institute of Science)

15:00 Bounded independence plus noise fools products (abstract)

Elad Haramaty (Harvard University), Chin Ho Lee (Northeastern University), Emanuele Viola (Northeastern University)

15:30 Tight bounds on The Fourier spectrum of AC0 (abstract)

Avishay Tal (Institute for Advanced Study)

16:00Coffee break
16:30 Complexity-theoretic foundations of quantum supremacy experiments (abstract)

Scott Aaronson (UT Austin), Lijie Chen (Tsinghua University)

17:00 Stochasticity in algorithmic statistics for polynomial time (abstract)

Alexey Milovanov (National Research University Higher School of Economics), Nikolay Vereshchagin (National Research University Higher School of Economics)

17:30 Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness (abstract)

Igor Carboni Oliveira (Charles University Prague), Rahul Santhanam (University of Oxford)

18:00Break
18:15Rump session

Saturday July 8

8:30 A quadratic lower bound for homogeneous algebraic branching programs (abstract)

Mrinal Kumar (Rutgers University)

9:00 On algebraic branching programs of small width (abstract)

Karl Bringmann (Max-Planck-Institut für Informatik), Christian Ikenmeyer (Max-Planck-Institut für Informatik), Jeroen Zuiddam (CWI)

9:30 Reconstruction of full rank algebraic branching programs (abstract)

Neeraj Kayal (Microsoft Research India), Vineet Nair (Indian Institute of Science), Chandan Saha (Indian Instituite of Science), Sebastien Tavenas (University of Savoie Mont Blanc)

10:00Coffee break
10:30 Tutorial (part 3)
Operator scaling: theory, applications and connections (abstract)

Avi Wigderson (Institute for Advanced Study)

12:30Lunch
14:30 Trading information complexity for error (abstract)

Yuval Dagan (Technion), Yuval Filmus (Technion), Hamed Hatami (McGill University), Yaqiao Li (McGill University)

15:00 Augmented index and quantum streaming algorithms for DYCK(2) (abstract)

Ashwin Nayak (University of Waterloo), Dave Touchette (University of Waterloo and Perimeter Institute)

15:30 Separating quantum communication and approximate rank (abstract)

Anurag Anshu (National University of Singapore), Shalev Ben-David (MIT), Ankit Garg (MSR New England), Rahul Jain (National University of Singapore and MajuLab), Robin Kothari (MIT), Troy Lee (Nanyang Technological University, Centre for Quantum Technologies, and MajuLab)

16:00 Optimal quantum sample complexity of learning algorithms (abstract)

Srinivasan Arunachalam (CWI), Ronald de Wolf (CWI and University of Amsterdam)

16:30Excursion
20:00Banquet

Sunday July 9

8:30 Settling the query complexity of non-adaptive junta testing (abstract)

Xi Chen (Columbia University), Rocco A. Servedio (Columbia University), Li-Yang Tan (TTI Chicago), Erik Waingarten (Columbia University), Jinyu Xie (Columbia University)

9:00 An adaptivity hierarchy theorem for property testing (abstract)

Clément Canonne (Columbia University), Tom Gur (Weizmann Institute of Science)

9:30 Distribution testing lower bounds via reductions from communication complexity (abstract)

Eric Blais (University of Waterloo), Clément Canonne (Columbia University), Tom Gur (Weizmann Institute of Science)

10:00 Exponentially small soundness for the direct product Z-test (abstract)

Irit Dinur (Weizmann Institute of Science), Inbal Livni Navon (Weizmann Institute of Science)

10:30Coffee break
11:00 On the polynomial parity argument complexity of the combinatorial Nullstellensatz (abstract)

Aleksandrs Belovs (University of Latvia), Gabor Ivanyos (Hungarian Academy of Sciences), Youming Qiao (University of Technology Sydney), Miklos Santha (CNRS, Université Paris Diderot, and National University of Singapore), Siyi Yang (National University of Singapore)

11:30 An exponential lower bound for homogeneous depth-5 circuits over finite fields (abstract)

Mrinal Kumar (Rutgers University), Ramprasad Saptharishi (TIFR Bombay)

12:00 Complete derandomization of identity testing and reconstruction of read-once formulas (abstract)

Daniel Minahan (University of Michigan), Ilya Volkovich (University of Michigan)

12:30 Greedy strikes again: A deterministic PTAS for commutative rank of matrix spaces (abstract)

Markus Blaeser (Saarland University), Gorav Jindal (Max-Planck-Institute for Informatics), Anurag Pandey (Max-Planck-Institute for Informatics)

13:00End of the conference

Organized by:

Computational Complexity Foundation Inc.

University of Latvia

In Cooperation with:

EATCS

Sponsored by:

Microsoft Research