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* (abstract) 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 (abstract) 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 Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira
	Sum of Squares Bounds for the Ordering Principle Aaron Potechin
2:15	End of the conference