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:00Welcome remarks
10:05Session 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:15Short break
11:30Session 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

1:00Session 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:15Short break
2:30Business meeting

Wednesday, July 21

10:00Session 4 (pre-recorded talks)
A Lower Bound on Determinantal Complexity

Mrinal Kumar and Ben Lee Volk

Hitting Sets and Reconstruction for Dense Orbits in VPe 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:15Short break
11:30Session 5

Invited Talk

How Much Information is in the Title of This Lecture? (abstract) (slides: pptx, pdf)

Eric Allender

1:00Session 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:15Short break
2:30Session 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


Thursday, July 22

10:00Session 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:15Short break
11:30Session 9 (pre-recorded talks)
Best Student Paper

A Lower Bound for Polynomial Calculus with Extension Rule

Yaroslav Alekseev

12:30Session 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:30Short break
1:45Session 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:45End of the conference

Organized by:

In Cooperation with: