Computational Complexity Conference

CCC'18 - Program

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

Venue All activities except the reception take place at the University of California, San Diego, Qualcomm Institute (CaliIT2), Atkinson Hall. The reception takes place at the Bella Vista cafe .

Slides and Videos Click the word "slides" in the program to see the presentations that the authors agreed to post on this website. Videos of the invited tutorials can be viewed by clicking on the word "video".

Proceedings The official version is openly accessible via LIPIcs.

Thursday June 21

18:00 - 20:00

Opening Reception

Friday June 22

8:00	Breakfast
9:00	Tutorial (part 1) Constraints, Consistency, and Complexity (abstract, slides, video) Andrei Krokhin In this tutorial, I will first explain the general philosophy of the algebraic approach to dealing with complexity-theoretic questions about Constraint Satisfaction Problems (CSPs). This approach will be be at the heart of the tutorial. I will then focus on algorithms based on probably the most natural algorithmic approach to dealing with CSPs - local propagation. In the context of CSPs, any version of local propagation either refutes an instance or establishes some form of local consistency. Solvability by local propagation has equivalent characterisations in terms of refutation systems, homomorphism dualities, pebble games, descriptive complexity, database language Datalog, etc. For decision CSPs, local propagation is one of two main algorithmic principles used in polynomial time algorithms. I will discuss the power of local propagation as an algorithmic principle, i.e. which CSPs are solvable by some version of local propagation/consistency, and relate this topic to a new way of designing approximation algorithms for CSPs. If time allows, I will briefly discuss the recent resolution of the CSP Dichotomy Conjecture and describe a new exciting direction in the complexity of CSP that goes far beyond the recently resolved conjecture.
10:00	Coffee break
10:30	Pseudorandom Generators from Polarizing Random Walks (slides) Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini and Shachar Lovett
11:00	A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in $\epsilon$ and Logarithmic in $n$ Daniel Kane and Sankeerth Rao Karingula
11:30	A New Approach for Constructing Low-Error, Two-Source Extractors (slides) Dean Doron, Amnon Ta-Shma, Avraham Ben-Aroya, Eshan Chattopadhyay and Xin Li
12:00	Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs (slides) Venkatesan Guruswami, Nicolas Resch and Chaoping Xing
12:30	Lunch
14:00	NP-Hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits (slides) Shuichi Hirahara, Igor Oliveira and Rahul Santhanam
14:30	Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials (slides) Ryan Williams
15:00	The Power of Natural Properties as Oracles Russell Impagliazzo, Valentine Kabanets and Ilya Volkovich
15:30	Coffee break
16:00	Linear Sketching over F_2 (slides) Sampath Kannan, Elchanan Mossel, Swagato Sanyal and Grigory Yaroslavtsev
16:30	Communication Complexity with Small Advantage (slides) Thomas Watson
17:00	Break
17:15	Business meeting

Saturday June 23

8:00	Breakfast
9:00	Tutorial (part 2) Constraints, Consistency, and Complexity (abstract, slides, video) Andrei Krokhin In this tutorial, I will first explain the general philosophy of the algebraic approach to dealing with complexity-theoretic questions about Constraint Satisfaction Problems (CSPs). This approach will be be at the heart of the tutorial. I will then focus on algorithms based on probably the most natural algorithmic approach to dealing with CSPs - local propagation. In the context of CSPs, any version of local propagation either refutes an instance or establishes some form of local consistency. Solvability by local propagation has equivalent characterisations in terms of refutation systems, homomorphism dualities, pebble games, descriptive complexity, database language Datalog, etc. For decision CSPs, local propagation is one of two main algorithmic principles used in polynomial time algorithms. I will discuss the power of local propagation as an algorithmic principle, i.e. which CSPs are solvable by some version of local propagation/consistency, and relate this topic to a new way of designing approximation algorithms for CSPs. If time allows, I will briefly discuss the recent resolution of the CSP Dichotomy Conjecture and describe a new exciting direction in the complexity of CSP that goes far beyond the recently resolved conjecture.
10:00	Coffee break
10:30	Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity (slides) Zeyu Guo, Nitin Saxena and Amit Sinhababu
11:00	Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits (slides) Noga Alon, Mrinal Kumar and Ben Lee Volk
11:30	Hardness Amplification for Non-Commutative Arithmetic Circuits Marco Carmosino, Russel Impagliazzo, Shachar Lovett and Ivan Mihajlin
12:00	Hardness vs Randomness for Bounded Depth Arithmetic Circuits (slides) Chi-Ning Chou, Mrinal Kumar and Noam Solomon
12:30	Lunch
14:00	On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product (slides) Lijie Chen
14:30	Hardness of Function Composition for Semantic Read once Branching Programs (slides) Jeff Edmonds, Venkatesh Medabalimi and Toniann Pitassi
15:00	Reordering Rule Makes OBDD Proof Systems Stronger (slides) Sam Buss, Dmitry Itsykson, Alexander Knop and Dmitry Sokolov
15:30	Coffee break
16:00	Testing Linearity against Non-Signaling Strategies (slides) Alessandro Chiesa, Peter Manohar and Igor Shinkar
16:30	Earthmover Resilience and Testing in Ordered Structures (slides) Omri Ben-Eliezer and Eldar Fischer
17:00	Break
17:15	Rump session

Sunday June 24

8:00	Breakfast
9:00	New Hardness Results for the Permanent Using Linear Optics (slides) Daniel Grier and Luke Schaeffer
9:30	Two-player Entangled Games are NP-Hard (slides) Anand Natarajan and Thomas Vidick
10:00	Complexity Classification of Conjugated Clifford Circuits (slides) Adam Bouland, Joseph Fitzsimons and Dax Enshan Koh
10:30	Coffee break
11:00	Efficient Batch Verification for UP Omer Reingold, Guy Rothblum and Ron Rothblum
11:30	Tight Lower Bound for Entropy Flattening (slides) Yi-Hsiu Chen, Mika Goos, Salil Vadhan and Jiapeng Zhang
12:00	Worst-Case to Average Case Reductions for the Distance to a Code (slides) Eli Ben-Sasson, Swastik Kopparty and Shubhangi Saraf
12:30	Lunch
14:00	The Complexity of the Cayley Semigroup Membership Problem (slides) Lukas Fleischer
14:30	Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth (slides) Andrzej Lingas
15:00	Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers (slides) Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao
15:30	Dimension Reduction for Polynomials over Gaussian Space and Applications (slides) Badih Ghazi, Pritish Kamath and Prasad Raghavendra
16:00	End of the conference