Computational Complexity Conference

CCC'26 Program

Schedule.  The program runs from Monday, August 3 to Thursday, August 6, 2026. The slots for contributed talks are 30 minutes (including 5 minutes for questions and changing speakers), and the Test-of-Time talk on Monday has a duration of one hour. The business meeting is on Monday evening.

All times below are local Lisbon time.

Monday, August 3

09:00

Test of time talk

10:00

Best student paper: Randomized separations in black-box TFNP

Fyodor Kiselyov

10:30 Break
11:00

Separations Above TFNP From Sherali-Adams Lower Bounds

Noah Fleming, Anna Gal, Deniz Imrek, Christophe Marciot

11:30

Efficient adversaries

Erfan Khaniki, Jan Pich, Dmitry Sokolov

12:00

Resolution Width Lifts to Near-Quadratic-Depth Res(⊕) Size

Dmitry Itsykson, Vladimir Podolskii, Alexander Shekhovtsov

12:30 Lunch
14:00

Wide Replacement Products Meet Gray Codes: Toward Optimal Small-Bias Sets

Gil Cohen, Itay Cohen

14:30

A Simple Sub-Polynomial Degree Coboundary Expander

Max Hopkins, Arka Ray

15:00

Faux Determinism

Shalev Ben-David, M. H. Ebtehaj

15:30 Break
16:00

Improved Bounds on the Space Complexity of Circuit Evaluation

Yakov Shalunov

16:30

Frontier Space-Time Algorithms Using Only Full Memory

Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal

17:00

Hardness of Computing Nondeterministic Kolmogorov Complexity

Jinqiao Hu, Zhenjian Lu, Igor Oliveira

17:30 Business meeting

Tuesday, August 4

09:00

Best paper: A weak regularity lemma for polynomials

Guy Moshkovitz, Dora Woodruff

09:30

When Hilbert approximates: A Strong Nullstellensatz for Approximate Polynomial Satisfiability

Sanyam Agarwal, Sagnik Dutta, Anurag Pandey, Himanshu Shukla

10:00

On Factorization of Sparse Polynomials of Bounded Individual Degree

Aminadav Chuyoon, Amir Shpilka

10:30 Break
11:00

Quantum–Classical Equivalence for AND-Functions

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

11:30

The Log-Rank Conjecture: New Equivalent Formulations

Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley

12:00

Bounds for Hardness Condensation in the Query Model

Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli, Manaswi Parashaar, Karthikeya Polisetty, Jayalal Sarma, Nitin Saurabh

12:30 Lunch
14:00

Probabilistically Checking Quantum Proofs, with Interaction

Baocheng Sun, Thomas Vidick

14:30

Derandomised tensor product gap amplification for quantum Hamiltonians

Thiago Bergamaschi, Tony Metger, Thomas Vidick, Tina Zhang

15:00

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen

15:30 Break
16:00

Strong Inapproximability of Monotone Circuit Size and Hardness of Monotone Learning under Worst-case Assumptions

Bruno Cavalar, Susanna de Rezende, Matthew Gray, Rahul Santhanam

16:30

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Yang P. Liu, Shachar Lovett, Kunal Mittal

17:00

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH

Rishav Gupta, Bingkai Lin, Xin Zheng

Wednesday, August 5

09:00

The Rate-Immediacy Barrier in Explicit Tree Code Constructions

Gil Cohen, Leonard Schulman, Piyush Srivastava

09:30

Trace Hermitian codes have vanishing bias

Amnon Ta-Shma, Swastik Kopparty, Kedem Yakirevitch

10:00

Optimal Testing of Reed-Muller Codes with an Online Adversary

Esty Kelman, Uri Meir, Kai Zhe Zheng

10:30 Break
11:00

Polynomial Identity Testing for Read-4 Arithmetic Formulas

Nimrod Kaplan, Amir Shpilka

11:30

Rank bounds and polynomial-time PIT for depth-4 circuits with bounded top fan-in and bottom fan-in bounded by 2

Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta, Nir Shalmon, Amir Shpilka

12:00

Constant-depth circuits for polynomial GCD over any characteristic

Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

12:30 Lunch
14:00

Asymptotic Rank Speedup Theorems, Revisited

Josh Alman, Baitian Li

14:30

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?

Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, Jiaheng Wang

15:00

Fixed-Parameter Degree Bounds and Complexity of the Orbit Closure Intersection Problem for Tensors

Rafael Oliveira, Levent Dogan, John Maar, Youming Qiao

15:30 Break
16:00

Plethysm is in #BQP

Aram W. Harrow, Matthias Christandl, Greta Panova, Pietro M. Posta, Michael Walter

16:30

Non-Clifford Gates are Required for Long-Term Memory

Joel Rajakumar, Jon Nelson, Michael Gullans

17:00

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

Thursday, August 6

09:00

Multiplicative Pseudorandom Generators For Nondeterministic Circuits

Alon Dermer, Ronen Shaltiel

09:30

All Polynomial Generators Preserve Distance with Mutual Correlated Agreement

Sarah Bordage, Alessandro Chiesa, Ziyi Guan, Ignacio Manzur

10:00

Condensing and Extracting Against Online Adversaries

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio

10:30 Break
11:00

Derandomized Graph Sampling With Applications to Deterministic Parallel Basis Finding

Aaron Putterman, Salil Vadhan, Vadim Zaripov

11:30

Systematic Data Structure Lower Bounds via the Query-with-Sketch Model

Sumegha Garg, Songhua He, Periklis A. Papakonstantinou, Yuanzhi Li, Xin Yang

12:00

Optimal Depth-Three Circuits for Inner Product

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Navid Talebanfard

12:30 Lunch
14:00

Multilinear Formula Lower Bounds for Sparse Determinants

Pruthvi Boyapati, Suryajith Chillara, Pratyush Vempati

14:30

Multilinear Algebraic Branching Programs and the Min-Partition Rank Method

Théo Fabris, Nutan Limaye, Srikanth Srinivasan, Amir Yehudayoff

[Updated: June 5, 2026]

Organized by:

 

In cooperation with:
EATCS
ACM

SIGACT

ATL Logo