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.

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)

Andrei Krokhin

10:00Coffee break
10:30 Pseudorandom Generators from Polarizing Random Walks

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

Dean Doron, Amnon Ta-Shma, Avraham Ben-Aroya, Eshan Chattopadhyay and Xin Li

12:00 Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs

Venkatesan Guruswami, Nicolas Resch and Chaoping Xing

14:00 NP-Hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

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

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

Sampath Kannan, Elchanan Mossel, Swagato Sanyal and Grigory Yaroslavtsev

16:30 Communication Complexity with Small Advantage

Thomas Watson

17:15Business meeting

Saturday June 23

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

Andrei Krokhin

10:00Coffee break
10:30 Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity

Zeyu Guo, Nitin Saxena and Amit Sinhababu

11:00 Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

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

Chi-Ning Chou, Mrinal Kumar and Noam Solomon

14:00 On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Lijie Chen

14:30 Hardness of Function Composition for Semantic Read once Branching Programs

Jeff Edmonds, Venkatesh Medabalimi and Toniann Pitassi

15:00 Reordering Rule Makes OBDD Proof Systems Stronger

Sam Buss, Dmitry Itsykson, Alexander Knop and Dmitry Sokolov

15:30Coffee break
16:00 Testing Linearity against Non-Signaling Strategies

Alessandro Chiesa, Peter Manohar and Igor Shinkar

16:30 Earthmover Resilience and Testing in Ordered Structures

Omri Ben-Eliezer and Eldar Fischer

17:15Rump session

Sunday June 24

9:00 New Hardness Results for the Permanent Using Linear Optics

Daniel Grier and Luke Schaeffer

9:30 Two-player Entangled Games are NP-Hard

Anand Natarajan and Thomas Vidick

10:00 Complexity Classification of Conjugated Clifford Circuits

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

Yi-Hsiu Chen, Mika Goos, Salil Vadhan and Jiapeng Zhang

12:00 Worst-Case to Average Case Reductions for the Distance to a Code

Eli Ben-Sasson, Swastik Kopparty and Shubhangi Saraf

14:00 The Complexity of the Cayley Semigroup Membership Problem

Lukas Fleischer

14:30 Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth

Andrzej Lingas

15:00 Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers

Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao

15:30 Dimension Reduction for Polynomials over Gaussian Space and Applications

Badih Ghazi, Pritish Kamath and Prasad Raghavendra

16:00End of the conference

Organized by:

In Cooperation with:


Sponsored by:

Microsoft Research