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.
| 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 |
| 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 |
| 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 |
| 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 |
