Computational Complexity Conference

CCC'21 Program

Schedule: The talk for an award winning paper is 30 minutes long, including the time for questions. The talks for the other accepted papers are 10 minutes long, with two additional minutes for questions.

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

There is an invited talk on Wednesday, 11:30 am – 12:30 pm. There is a business meeting on Tuesday, at 2:30 pm, and a virtual social on Wednesday, 3:15 pm.

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.

Proceedings: The official version is openly accessible via LIPIcs.

Tuesday, July 20

10:00	Welcome remarks
10:05	Session 1 (pre-recorded talks)
	Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing Oded Goldreich and Avi Wigderson
	GSF-locality is not sufficient for proximity-oblivious testing Isolde Adler, Noleen Köhler, and Pan Peng
	Junta Distance Approximation with Sub-Exponential Queries Vishnu Iyer, Avishay Tal, and Michael Whitmeyer
	The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications Alexander Golovnev and Ishay Haviv
	On the Cut Dimension of a Graph Troy Lee, Tongyang Li, Miklos Santha and Shengyu Zhang
11:15	Short break
11:30	Session 2 (pre-recorded talks)
	An Improved Protocol for the Exactly-N Problem Nati Linial and Adi Shraibman
	Communication Complexity with Defective Randomness Marshall Ball, Oded Goldreich, and Tal Malkin
	Hardness of Constant-round Communication Complexity Shuichi Hirahara, Rahul Ilango, and Bruno Loff
	A Simple Proof of a New Set Disjointness with Applications to Data Streams Akshay Kamath, Eric Price, and David P. Woodruff
12:30	Break
1:00	Session 3 (pre-recorded talks)
	Quantum Complexity of Minimum Cut Simon Apers and Troy Lee
	A Direct Product Theorem for One-way Quantum Communication Rahul Jain and Srijita Kundu
	On Query-to-Communication Lifting for Adversary Bounds Anurag Anshu, Shalev Ben-David, and Srijita Kundu
	Fourier Growth of Parity Decision Trees Uma Girish, Avishay Tal, and Kewen Wu
	A Majority Lemma for Randomised Query Complexity Mika Göös and Gilbert Maystre
2:15	Short break
2:30	Business meeting

Wednesday, July 21

10:00	Session 4 (pre-recorded talks)
	A Lower Bound on Determinantal Complexity Mrinal Kumar and Ben Lee Volk
	Hitting Sets and Reconstruction for Dense Orbits in VP_e and Î£Î Î£ Circuits Dori Medini and Amir Shpilka
	Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena
	Variety Evasive Subspace Families Zeyu Guo
	Separating ABPs and Some Structured Formulas in the Non-Commutative Setting Prerona Chatterjee
11:15	Short break
11:30	Session 5
	Invited Talk How Much Information is in the Title of This Lecture? (abstract) (slides: pptx, pdf) Eric Allender Just as the title of this talk is an investigation into the title, so also is meta-complexity a complexity-theoretic investigation into computational complexity itself. In stark contrast to the title, meta-complexity has led to important insights. This lecture will survey a sampling of the developments in this rapidly-advancing area.
12:30	Break
1:00	Session 6 (pre-recorded talks)
	Hardness of KT Characterizes Parallel Cryptography Hanlin Ren and Rahul Santhanam
	Error Reduction For Weighted PRGs Against Read Once Branching Programs Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma
	Pseudodistributions That Beat All Pseudorandom Generators Edward Pyne and Salil Vadhan
	Fractional Pseudorandom Generators from Any Fourier Level Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty
	Rate Amplification and Query-Efficient Distance Amplification for linear LCC and LDC Gil Cohen and Tal Yankovitz
2:15	Short break
2:30	Session 7 (pre-recorded talks)
	Barriers for Recent Methods in Geodesic Optimization W. Cole Franks and Philipp Reichenbach
	On p-Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors Joshua A. Grochow and Youming Qiao
	Polynomial Time Algorithms in Invariant Theory for Torus Actions Peter Bürgisser, M. Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson
3:15	Social

Thursday, July 22

10:00	Session 8 (pre-recorded talks)
	On the Pseudo-deterministic Query Complexity of NP Search Problems Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam
	On the Power and Limitations of Branch and Cut Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson
	Proof Complexity of Natural Formulas via Communication Arguments Dmitry Itsykson and Artur Riazanov
	Branching Programs with Bounded Repetitions and Flow Formulas Anastasia Sofronova and Dmitry Sokolov
	The Power of Negative Reasoning Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Dmitry Sokolov
11:15	Short break
11:30	Session 9 (pre-recorded talks)
	Best Student Paper A Lower Bound for Polynomial Calculus with Extension Rule Yaroslav Alekseev
12:00	Break
12:30	Session 10 (pre-recorded talks)
	A Stress-Free Sum-of-Squares Lower Bound for Coloring Pravesh K. Kothari and Peter Manohar
	SOS Lower Bound for Exact Planted Clique Shuo Pang
	Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies Mark Braverman and Dor Minzer
	Toward Better Depth Lower Bounds: the XOR-KRW Conjecture Ivan Mihajlin and Alexander Smal
1:30	Short break
1:45	Session 11 (pre-recorded talks)
	Shadows of Newton Polytopes Pavel Hrubes and Amir Yehudayoff
	Arithmetic Circuit Complexity of Division and Truncation Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu
	On the Complexity of Evaluating Highest Weight Vectors Markus Bläser, Julian Dörfler, and Christian Ikenmeyer
	Matrix Rigidity Depends on the Target Field Laszlo Babai and Bohdan Kivva
2:45	End of the conference