Computational Complexity Conference

CCC'20 Program

Schedule: The talks for the award winning papers are 30 minutes long and the talks for the other accepted papers are 10 minutes long. The time slots include the time for questions.

All times below are in Eastern Daylight Time (EDT).

There are invited talks on Tuesday and Thursday, 11:30 am – 12:30 pm. There is a business meeting on Tuesday, 2:30 – 3 pm, and a virtual social on Wednesday, 2:15 pm. Mixers between junior and senior participants will be held during the conference. Information on the mixers will be shared with the registered participants.

Venue: All live events except the social will take place using Zoom. The social will be held with Gather. A discussion board will be available on Slack. Access to these will be provided to the registered participants separately.

Videos: Half-hour videos of the talks are available publicly on the CCC YouTube channel. Recordings of the invited talks will be posted after the conference.

Proceedings: The official version is openly accessible via LIPIcs.

Tuesday, July 28

10:00 Welcome remarks

10:05 Session 1

Near-Optimal Erasure List-Decodable Codes

Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma

Log-Seed Pseudorandom Generators via Iterated Restrictions

Dean Doron, Pooya Hatami, and William M. Hoza

Hitting Sets Give Two-Sided Derandomization of Small Space

Kuan Cheng and William M. Hoza

Optimal Error Pseudodistributions for Read-Once Branching Programs

Eshan Chattopadhyay and Jyun-Jie Liao

Palette-Alternating Tree Codes

Gil Cohen and Shahar Samocha

Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions

Shuichi Hirahara

11:15 Short break

11:30 Session 2

Invited talk

MIP* = RE: Verifying the halting problem with quantum provers ()

Thomas Vidick

I will present joint work with Ji, Natarajan, Yuen and Wright (arXiv:2001.04383) in which we show that the class MIP* of languages that can be decided by a classical polynomial-time verifier interacting with untrusted quantum entangled provers is exactly the class RE of recursively enumerable languages. I will motivate this result by describing intertwined lines of work in quantum information and operator algebras that lead to it, and present some of the key ideas that go in the proof.

12:30 Break

1:00 Session 3

Factorization of Polynomials Given by Arithmetic Branching Programs

Amit Sinhababu and Thomas Thierauf

A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

Nikhil Gupta, Chandan Saha, and Bhargav Thankey

Algebraic Hardness versus Randomness in Low Characteristic

Robert Andrews

Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan

Lower Bounds for Matrix Factorization

Mrinal Kumar and Ben Lee Volk

Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh

2:15 Short break

2:30 Business meeting

Wednesday, July 29

10:00 Session 4

A Quadratic Lower Bound for Algebraic Branching Programs

Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk

Geometric Rank of Tensors and Subrank of Matrix Multiplication

Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam

On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem

Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis

Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings

Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson

A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials

Shir Peleg and Amir Shpilka

Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems

Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß

11:15 Short break

11:30 Session 5

Best student paper award

Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas

Rahul Ilango

Best paper award

On the Complexity of Branching Proofs

Daniel Dadush and Samarth Tiwari

12:30 Break

1:00 Session 6

Hardness of Bounded Distance Decoding on Lattices in $\ell_p$ Norms

Huck Bennett and Chris Peikert

Statistical Physics Approaches to Unique Games

Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts

Approximability of the Eight-Vertex Model

Jin-Yi Cai, Tianyu Liu, Pinyan Lu, and Jing Yu

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler

On the Quantum Complexity of Closest Pair and Related Problems

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang

Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, and Manaswi Paraashar

2:15 Social

Thursday, July 30

10:00 Session 7

Super Strong ETH is True for Strong PPSZ with Small Resolution Width

Dominik Scheder, and Navid Talebanfard

Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut

Amey Bhangale and Subhash Khot

Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams

Jacques Dark and Christian Konrad

Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction

Marvin Künnemann and Dániel Marx

NP-Hardness of Circuit Minimization for Multi-Output Functions

Rahul Ilango, Bruno Loff, and Igor C. Oliveira

Circuit Lower Bounds from NP-Hardness of MCSP under Turing Reductions

Michael Saks and Rahul Santhanam

11:15 Short break

11:30 Session 8

Invited Talk

Mild random restrictions ()

Shachar Lovett

Random restrictions are a commonly used tool in boolean function analysis. A well known example is the Håstad switching lemma, which shows that DNFs (and more generally, AC0 circuits) simplify when most of the inputs are fixed. I will describe two new approaches to analyze "mild" random restrictions, which fix only a small fraction of the inputs. These underlie two recent results - improved bounds for the sunflower lemma and tight bounds for DNF compression (and more generally, for decision list compression). In this talk, I will mostly focus on the random restriction aspect and not on the applications.

Based on joint works with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.

12:30 Break

1:00 Session 9

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov

Sign Rank vs Discrepancy

Hamed Hatami, Kaave Hosseini, and Shachar Lovett

Limits of Preprocessing

Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler

Multiparty Karchmer-Wigderson Games and Threshold Circuits

Alexander Kozachinskiy and Vladimir Podolskii

Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates