ITCS 2026 Program and Schedule

Welcome to ITCS 2026. The conference will run in a single track and all sessions will take place in room N01 on the ground floor of the Leonardo Del Vecchio Building (Velodromo) on the main Bocconi campus. For directions and more details see here.

NOTE: January 26th, 2:00–6:00 pm, Trevisan Prize. The inaugural Trevisan Prize for Outstanding Work in the Theory of Computing is co-located with ITCS 2026 and will take place at Bocconi. Registration is free: form to participate. More details can be found here.

All timings are in Central European Time (CET). Each talk can be at most ten minutes long.

Tuesday, January 27th
8:55am–9:00am	Welcome remarks
Session 1 9:00am–10:30am Chair: TBA	Higher-order Delsarte Dual LPs: Lifting, Constructions and Completeness L. Coregliano, F. Jeronimo, C. Jones, N. Linial, E. Loyfer List Decoding Reed–Solomon Codes in the Lee, Euclidean, and Other Metrics C. Peikert, A. Veliche Limitations to computing quadratic functions on Reed-Solomon encoded data K. Blackwell, M. Wootters Linear time encodable binary code achieving GV bound with linear time encodable dual achieving GV bound M. Brehm, N. Resch Time and Space Efficient Deterministic List Decoding J. Cook, D. Moshkovitz Range Avoidance and Remote Point: New Algorithms and Hardness Y. Zhong, X. Li, S. Huang A General Framework for Low Soundness Homomorphism Testing T. Mittal, S. Roy
10:30am–11:00am	Break (coffee and refreshments)
Session 2 11:00am–12:30pm Chair: TBA	Samplability makes learning easier G. Blanc, C. Koch, J. Lange, C. Strassle, L. Tan Limitations of Membership Queries in Testable Learning J. Lange, M. Qiao Topological dimension of extremal concept classes A. Blondal, H. Hatami, P. Hatami, C. Lalov, S. Tretiak Fairness in the k-Server Problem M. Daneshvaramoli, H. Karisani, S. Kamali, C. Musco, M. Hajiesmaili Auditability and the Landscape of Distance to Multicalibration N. Derhake, S. Devic, D. Hansen, K. Liu, V. Sharan Bayesian Perspective on Memorization and Reconstruction H. Kaplan, Y. Mansour, k. nissim, U. Stemmer Differential privacy from axioms G. Blanc, W. Pires, T. Pitassi Uniformity Testing under User-Level Local Privacy C. Canonne, A. Gentle, V. Singhal
12:30pm–2:00pm	Lunch break (on your own)
Session 3 2:00pm–3:30pm Chair: TBA	The Mixed Birth-death/death-Birth Moran Process D. Brewster, Y. Huang, M. Mitzenmacher, M. Nowak Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems S. Dughmi, Y. Kalayci, X. Liu Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region S. Shao, K. Shi Dimension-Free Correlated Sampling for the Hypersimplex S. Naor, N. Raju, A. Shetty, A. Srinivasan, R. Valieva, D. Wajc Weighted chairman assignment and flow-time scheduling S. Liu, V. Reis Fixed-Parameter Tractable Submodular Maximization over a Matroid S. Nematollahi, A. Vladu, J. Zhao FPT Approximations for Connected Maximum Coverage T. Inamdar, S. Jana, M. Kundu, D. Lokshtanov, S. Saurabh, M. Zehavi
3:30pm–4:00pm	Break (coffee and refreshments)
Session 4 4:00pm–5:30pm Chair: TBA	Lower Bounds Beyond DNF of Parities A. Riazanov, A. Sofronova, D. Sokolov Supercritical Tradeoff Between Size and Depth for Resolution over Parities D. Itsykson, A. Knop Lower Bounds and Separations for Torus Polynomials V. Krishan, S. Vishwanathan Linear Matroid Intersection is in Catalytic Logspace A. Vinciguerra, A. Agarwala, Y. Alekseev Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds Y. Alekseev, N. Gaevoy Optimal Two-Round Communication Lower bound for Graph Connectivity via Pointer Chasing J. Radhakrishnan, C. Reddy, R. Venkat New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String L. Chen, Y. Hu, H. Ren Total Search Problems in ZPP N. Fleming, S. Grosser, S. Jain, J. Li, H. Ren, M. Shirley, W. Yuan
5:30pm–7:00pm	Welcome reception
Wednesday, January 28th
Session 5 9:00am–10:30am Chair: TBA	Discrepancy Beyond Additive Functions with Applications to Fair Division A. Hollender, P. Manurangsi, R. Meka, W. Suksompong Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions W. Ma, C. MacRury, J. Zhang Analyzing the Economic Impact of Decentralization on Users A. Levy, S. Weinberg, C. Zhou Robust Resource Allocation via Competitive Subsidies D. Lin, G. Fikioris, S. Banerjee, E. Tardos One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts M. Feldman, Y. Gal-Tzur, T. Ponitka, M. Schlesinger The Secretary Problem with Predictions and a Chosen Order H. Karisani, M. Daneshvaramoli, C. Musco, H. Beyhaghi, M. Hajiesmaili Prior-Independent and Subgame Optimal Online Algorithms J. Hartline, a. johnsen, A. Shah Characterizing Off-Chain Influence-Proof Transaction Fee Mechanisms A. Ganesh, C. Thomas, S. Weinberg
10:30am–11:00am	Break (coffee and refreshments)
Session 6 11:00am–12:30pm Chair: TBA	Smoothed Analysis of Dynamic Graph Algorithms U. Meir, A. Paz Triangle Detection in H-free Graphs N. Wallheimer, A. Abboud, R. Safier Hardness of Dynamic Tree Edit Distance and Friends B. Hu, B. Saha, J. Nogler On the PTAS Complexity of Multidimensional Knapsack I. Doron-Arad, P. Manurangsi, A. Kulik Range Longest Increasing Subsequence and its Relatives K. S., R. Saladi A Parameterized-Complexity Framework for Finding Local Optima R. Ganian, H. Hoang, C. Komusiewicz, N. Morawietz
12:30pm–2:00pm	Graduating Bits and Pizza 🍕🍕🍕 [Form to participate]
Session 7 2:00pm–3:30pm Chair: TBA	Lower Bounds on FSS from Dynamic Data Structures D. Weber, N. Gilboa Dudeney's Dissection is Optimal E. Demaine, T. Kamata, R. Uehara Computing Equilibrium Points of Electrostatic Potentials A. Ghosh, P. Goldberg, A. Hollender Delaunay Triangulations with Predictions S. Cabello, T. Chan, P. Giannopoulos General Computation using Slidable Tiles with Deterministic Global Forces A. Avila-Jimenez, D. Barreda, S. Evans, A. Luchsinger, A. Massie, R. Schweller, E. Tomai, T. Wylie Average Sensitivity of Geometric Algorithms M. Ebbens, Y. Yoshida Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion Y. Li, E. Vitercik, M. Yang
3:30pm–4:00pm	Break (coffee and refreshments)
Session 8 4:00pm–5:30pm Chair: TBA	Fourier Sparsity of Delta Functions and Matching Vector PIRs F. Ghasemi, S. Kopparty Recovering Communities in Structured Random Graphs M. Kapralov, L. Trevisan, W. Wrzos-Kaminska Efficient Catalytic Graph Algorithms J. Cook, E. Pyne New Bounds for Circular Trace Reconstruction A. Burudgunte, P. Valiant, H. Wang Interactive Proofs For Distribution Testing With Conditional Oracles A. Biswas, M. Bun, C. Canonne, S. Sivakumar Query Lower Bounds for Correlation Clustering under Memory Constraints S. He, S. Garg, P. Papakonstantinou Decoding Balanced Linear Codes With Preprocessing A. Bogdanov, R. Chatterjee, Y. Li, P. Vasudevan One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity Y. Liu, R. Pass
Thursday, January 29th
Session 9 9:00am–10:30am Chair: TBA	Markov Chain Robustness D. Zuckerman Lower Bounds on Tree Covers Y. Chen, Z. Tan, H. Xu Maximum-Flow and Minimum Cut Sensitivity Oracles for Directed Graphs M. Ahi, K. Choudhary, S. Pande, Pushpraj, L. Saggi Semi-Random Graphs, Robust Asymmetry, and Reconstruction J. Asilis, X. Chen, D. Hansen, S. Teng New Greedy Spanners and Applications E. Tzailk, E. Popova Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem J. Cai, B. Young A Combinatorial Characterization of Constant Mixing Time R. Liu, L. Lau
10:30am–11:00am	Break (coffee and refreshments)
Session 10 11:00am–12:30pm Chair: TBA	Multi-Quadratic Sum-of-Squares Lower Bounds Imply VNC¹≠VNP B. Rossman, D. Zhu AC0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard J. Lu, R. Santhanam, I. Tzameret Lower Bounds for Noncommutative Circuits with Low Syntactic Degree P. Shastri Symmetric Algebraic Circuits and Homomorphism Polynomials A. Dawar, B. Pago, T. Seppelt On Closure Properties of Read-Once Oblivious Algebraic Branching Programs R. Andrews, J. Armand, P. Dwivedi, M. Hansen, N. Limaye, S. Srinivasan, S. Tavenas Debordering Closure Results in Determinantal and Pfaffian Ideals A. Dey, Z. Guo Slice rank and partition rank of the determinant A. Lampert, G. Moshkovitz Identity Testing for Circuits with Exponentiation Gates J. Li, M. Wu
12:30pm–2:00pm	Lunch break (on your own)
Session 11 2:00pm–3:30pm Chair: TBA	Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election Y. Chang, L. Chen, H. Zhou A Simple and Robust Protocol for Distributed Counting E. Cohen, M. Shechner, U. Stemmer Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations R. Ravi, B. Haeupler, M. Kaufmann, U. Schaller Perfect Simulation of Las Vegas Algorithms via Local Computation X. Fu, Y. Jiang, Y. Yin Robust Streaming Against Low-Memory Adversaries O. Ben-Eliezer, K. Onak, S. Silwal Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length A. Gal, G. Kol, R. Saxena, H. Yu Model-Generic Incrementally Verifiable Computation from Updatable BARGs E. Tshuva, R. Oshman
3:30pm–4:00pm	Break (coffee and refreshments)
Session 12 4:00pm–5:30pm Chair: TBA	Efficient Algorithms for the Disjoint Shortest Paths Problem and its Extensions K. Choudhary, A. Kumar, L. Saggi Pseudodeterministic Algorithms for Minimum Cut Algorithms A. Agarwala, N. Varma Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs K. Efremenko, G. Kol, R. Saxena, Z. Zhang Testable algorithms for approximately counting edges and triangles T. Eden, R. Rubinfeld, A. Vasilyan On approximating the f-divergence between two Ising models W. Feng, Y. Fu Dimension Reduction for Clustering: The Curious Case of Discrete Centers S. Jiang, R. Krauthgamer, S. Sapir, S. Silwal, D. Yue On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time T. Kwok, Z. Wei, M. Yang
5:30pm–7:00pm	Business meeting
Friday, January 30th
Session 13 9:00am–10:30am Chair: TBA	Decentralized Data Archival: New Definitions and Constructions E. Shi, R. Silver, C. Mu Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits H. Ren, Y. Wang, Y. Zhong Diffie--Hellman Key Exchange from Commutativity to Group Laws D. Duong, Y. Qiao, C. Zhang Ideal Private Simultaneous Messages Schemes and Their Applications R. Eriguchi, K. Hiwatashi On the power of Computationally Sound Interactive Proofs of Proximity H. Strauss How to Use Nondeterminism in Cryptography M. Ball, P. Crawford-Kahrl Improved Rate for Non-Malleable Codes and Time-Lock Puzzles C. Freitag, I. Komargodski, M. Kondapaneni, J. Silbak
10:30am–11:00am	Break (coffee and refreshments)
Session 14 11:00am–12:30pm Chair: TBA	The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class between QMA and QMA(2) J. Kamminga, D. Rudolph Commuting Local Hamiltonians Beyond 2D J. Bostanci, Y. Hwang Oracle Separations for the Quantum-Classical Polynomial Hierarchy A. Agarwal, S. Ben-David Symmetric quantum computation D. Castro-Silva, T. Gur, S. Strelchuk The Hardness of Learning Quantum Circuits and its Cryptographic Applications B. Fefferman, S. Ghosh, M. Sinha, H. Yuen Forrelation Is Extremally Hard U. Girish, R. Servedio An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem M. Aldi, S. Gharibian, D. Rudolph Two bases suffice for QMA1 completneess H. Ma, A. Natarajan
12:30pm–2:00pm	Lunch break (on your own)
Session 15 2:00pm–3:30pm Chair: TBA	The Learning Stabilizers with Noise problem A. Poremba, Y. Quek, P. Shor Cloning Games, Black Holes and Cryptography A. Poremba, S. Ragavan, V. Vaikuntanathan Unconditional Pseudorandomness against Shallow Quantum Circuits S. Ghosh, S. Subramanian, W. Zhan Unitary Complexity and the Uhlmann Transformation Problem J. Bostanci, Y. Efron, T. Metger, A. Poremba, L. Qian, H. Yuen Fully Quantum Computational Entropies T. Hahn, N. Avidan, R. Arnon, J. Renes Random Unitaries in Constant (Quantum) Time B. Foxman, N. Parham, F. Vasconcelos, H. Yuen The curious case of "XOR repetition" of monogamy-of-entanglement games A. Coladangelo, Q. Liu, Z. Xie
3:30pm–4:00pm	Break (coffee and refreshments)
Session 16 4:00pm–5:30pm Chair: TBA	Unconditional Quantum Advantage for Sampling with Shallow Circuits A. Watts, N. Parham Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits B. Fefferman, S. Ghosh, W. Zhan Local transformations of bipartite entanglement are rigid J. Bostanci, T. Metger, H. Yuen Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals D. Grier, D. Kane, J. Morris, A. Ostuni, K. Wu Algorithmic Polynomial Freiman-Ruzsa Theorems S. Arunachalam, D. Castro-Silva, A. Dutt, T. Gur On the complexity of unique quantum witnesses and quantum approximate counting A. Anshu, J. Haferkamp, Y. Hwang, Q. Nguyen Identity check problem for shallow quantum circuits S. Bravyi, N. Parham, Minh Testing classical properties from quantum data J. Slote, P. Naik, M. Caro
	End of conference