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 (, 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