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:00Opening Reception

Friday June 22

9:00 Tutorial (part 1)
Constraints, Consistency, and Complexity (abstract, slides, video)

Andrei Krokhin

10:00Coffee 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

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:30Coffee 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:15Business meeting

Saturday June 23

9:00 Tutorial (part 2)
Constraints, Consistency, and Complexity (abstract, slides, video)

Andrei Krokhin

10:00Coffee 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

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:30Coffee 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:15Rump session

Sunday June 24

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:30Coffee 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

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:00End of the conference

Organized by:

In Cooperation with:


Sponsored by:

Microsoft Research