All the times are in AEDT (UTC +11). Additional (social) activities are or will be listed on the corresponding page: fun runs, walks, etc. A mobile-friendly schedule site is available 🔗 at this address.
The planned events on Day 1 include Workshops and a Welcome Reception.
Workshop Session A | Workshop Session B | Workshop Session C | |
| 8:30–9:00 | Welcome tea and registration ☕ | ||
|---|---|---|---|
| 9:00–10:00 | Breaking and Making Quantum Speedups (organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty) | (organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) | (organized by Ian Mertz and Ted Pyne ) |
| 10:00–10:30 | Break ☕ | ||
| 10:30–12:00 | Breaking and Making Quantum Speedups (organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty) | (organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) | (organized by Ian Mertz and Ted Pyne ) |
| 12:00–1:30 | Lunch (provided) 🍽️ | ||
| 1:30–3:00 | Breaking and Making Quantum Speedups (organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty) | (organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) | (organized by Santosh S. Vempala) |
| 3:00–3:30 | Break ☕ | ||
| 3:30–4:30 | Breaking and Making Quantum Speedups (organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty) | (organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) | (organized by Santosh S. Vempala) |
| 4:30–4:45 | Break | ||
| 4:45–5:30 | Graduating bits 🎓 | ||
| 5:30–6:00 | Welcome to Country | ||
| 6:00–8:00 | Welcome Reception 🥂 | ||
| 9:00–10:30 | Session 1A | Session 1B | Session 1C |
| Online Edge Coloring: Sharp Thresholds Authors: J. Blikstad, O. Svensson, R. Vintan, D. Wajc | Integer multiplication is at least as hard as matrix transposition Authors: D. Harvey, J. van der Hoeven | Group Order is in QCMA Authors: F. Le Gall, H. Nishimura, D. Thakkar | |
| Edge-weighted Matching in the Dark Authors: Z. Huang, E. Sun, X. Wu, J. Zhao | Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings) Authors: L. Wulf | Exponential improvements to the average-case hardness of BosonSampling Authors: A. Bouland, S. Datta, B. Fefferman, F. Hernandez | |
| Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives Authors: T. Kesselheim, M. Molinaro, K. Patton, S. Singla | Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration Authors: S. Hirahara, N. Ohsaka | RE-completeness of entangled constraint satisfaction problems Authors: E. Culf, K. Mastel | |
| Optimal 4-Approximation for the Correlated Pandora’s Problem Authors: N. Bansal, Z. Huang, Z. Zhu | Ineffectiveness for Search and Undecidability of PCSP Meta-Problems Authors: A. Larrauri | Gap-preserving reductions and RE-completeness of Independent Set Games Authors: L. Mančinska, P. Spaas, T. Spirig, M. Vernooij | |
| A Little Clairvoyance Is All You Need Authors: A. Gupta, H. Kaplan, A. Lindermayr, J. Schlöter, S. Yingchareonthawornchai | Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices Authors: V. Bhattiprolu, V. Guruswami, E. Lee, X. Ren | Incompressibility and spectral gaps of random circuits Authors: C. Chen, J. Haah, J. Haferkamp, Y. Liu, T. Metger, X. Tan | |
| 10:30–10:50 | Break ☕ | ||
|---|---|---|---|
| 10:50–12:02 | Session 2A | Session 2B | Session 2C |
| Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time via Dynamic Representative Sets Author: J. Nederlof | Factorization Norms and an Inverse Theorem for MaxCut Authors: I. Balla, L. Hambardzumyan, I. Tomon | The Sponge is Quantum Indifferentiable Authors: G. Alagic, J. Carolan, C. Majenz, S. Tokat | |
| Improved 2-Approximate Shortest Paths for close vertex pairs Author: M. Gupta | More efficient sifting for grid norms, and applications to multiparty communication complexity Authors: Z. Kelley, X. Lyu | Parallel Repetition for Post-Quantum Arguments Authors: A. Huang, Y. Kalai | |
| Paths and Intersections: Exact Emulators for Planar Graphs Authors: G. Li, Z. Tan, T. Zhang | Sign-Rank of k-Hamming Distance is Constant Authors: M. Göös, N. Harms, V. Imbach, D. Sokolov | On the Impossibility of SNARGs with Short CRS (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting) Authors: L. Chen, Z. Jin | |
| Distance Approximating Minors for Planar and Minor-Free Graphs Authors: H. Chang, J. Conroy | Direct Product Theorems for Randomized Query Complexity Authors: S. Ben-David, E. Blais | On Succinct Obfuscation via Propositional Logic (or: How to use pv-IO) Authors: A. Jain, Z. Jin, S. Mathialagan, O. Paneth | |
| 12:02–1:30 | Lunch (provided) 🍽️ | ||
| 1:30–2:30 | Plenary 1Shafi Goldwasser, MIT and Berkeley | ||
| 2:30–3:00 | Break ☕ | ||
| 3:00–4:12 | Session 3A | Session 3B | Session 3C |
| An Improved Greedy Approximation for (Metric) $k$-Means Authors: M. Charikar, V. Cohen-Addad, R. Gao, F. Grandoni, E. Lee, E. van Wijland | Deterministic factorization of constant-depth algebraic circuits in subexponential time Authors: S. Bhattacharjee, M. Kumar, V. Ramanathan, R. Saptharishi, S. Saraf | Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions Authors: R. Ilango, A. Lombardi | |
| Stochastic Knapsack without Relaxing the Capacity Authors: A. De, S. Khanna, N. White | Rank Bounds and PIT for $\Sigma^3 \Pi \Sigma \Pi^d$ circuits via a non-linear Edelstein-Kelly theorem Authors: A. Garg, R. Oliveira, A. Sengupta | Solving Linear Inequalities over Convex Sets & its Applications to Cryptography and Hydrodynamics Authors: S. Basu, H. Khorasgani, H. Maji, H. Nguyen | |
| Adaptivity Gaps for Stochastic Probing with Subadditive Functions Authors: J. Li, Y. Liu, Y. Zhang | Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum Authors: J. Alman, B. Li | Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions Authors: G. Lu, J. Silbak, D. Wichs | |
| Stochastic scheduling with Bernoulli-type jobs through policy stratification Authors: A. Antoniadis, R. Hoeksma, K. Schewior, M. Uetz | Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness Authors: V. Lysikov, M. Walter | Succinct Homomorphic MACs from Groups and Applications Authors: Y. Ishai, H. Li, H. Lin | |
| 4:12–4:30 | Break | ||
| 4:30–5:24 | Session 4A | Session 4B | Session 4C |
| Faster Mixing of the Jerrum-Sinclair Chain Authors: X. Chen, W. Feng, Z. Ju, T. Miao, Y. Yin, X. Zhang | Bipartite Matching is in Catalytic Logspace Authors: A. Agarwala, I. Mertz | A distillation–teleportation protocol for fault-tolerant QRAM Authors: A. Dalzell, C. Hann, A. Gilyén, S. McArdle, G. Salton, Q. Nguyen, A. Kubica, F. Brandao | |
| Rapid Mixing on Random Regular Graphs beyond Uniqueness Authors: X. Chen, Z. Chen, Z. Chen, Y. Yin, X. Zhang | Collapsing Catalytic Classes Authors: M. Koucky, I. Mertz, E. Pyne, S. Sami | Adversarially robust quantum state learning and testing Authors: M. Aliakbarpour, V. Braverman, N. Chia, Y. Liu | |
| Deterministic counting from coupling independence Authors: X. Chen, W. Feng, H. Guo, X. Zhang, Z. Zou | Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations Authors: M. Naor, B. Menuhin | Learning quantum Gibbs states locally and efficiently Authors: C. Chen, A. Anshu, Q. Nguyen | |
| 5:24–6:00 | Break | ||
| 6:00–7:30 | Business meeting 📊 | ||
| 9:00–10:30 | Session 5A | Session 5B | Session 5C |
Near-Optimal Fault-Tolerant Strong Connectivity Preservers Authors: G. Hoppenworth, T. Saranurak, B. Wang | Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent Authors: M. Levi, J. Mosheiff, N. Shagrithaya | An Improved Bound for the Beck-Fiala Conjecture Authors: N. Bansal, H. Jiang | |
Deterministic Almost-Linear-Time Gomory-Hu Trees Authors: A. Abboud, R. Kyng, J. Li, D. Panigrahi, M. Probst, T. Saranurak, W. Yuan, W. Yuan | Maximally Extendable Product Codes are Good Coboundary Expanders Authors: G. Kalachev, P. Panteleev | A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number Authors: R. Bourneuf, P. Charbit, S. Thomasse | |
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs Authors: A. Bernstein, J. Blikstad, J. Li, T. Saranurak, T. Tu | Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks Authors: L. Golowich, V. Guruswami | Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa Authors: B. Bedert, T. Nakajima, K. Okrasa, S. Zivny | |
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs Authors: S. Jiang, M. Kapralov, L. Er Lu, A. Sidford | A k^{q/q-2} Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs Authors: O. Janzer, P. Manohar | Cycle-factors of regular graphs via entropy Authors: E. Hurley, A. Girao, L. Michel, N. Draganic, A. Müyesser, M. Christoph | |
Almost Tight Additive Guarantees for $k$-Edge-Connectivity Authors: N. Kumar, C. Swamy | Improved Lower Bounds for all Odd-Query Locally Decodable Codes Authors: A. Basu, J. Hsieh, P. Kothari, A. Lin | Polynomial Bounds for the Graph Minor Structure Theorem Authors: M. Gorsky, M. Seweryn, S. Wiederrecht | |
| 10:30–10:50 | Break ☕ | ||
|---|---|---|---|
| 10:50–12:02 | Session 6A | Session 6B | Session 6C |
The Power of Recursive Embeddings for $\ell_p$ Metrics Authors: R. Krauthgamer, N. Petruschka, S. Sapir | Undirected Multicast Network Coding Gaps via Locally Decodable Codes Authors: Z. He, M. Braverman | How Global Calibration Strengthens Multiaccuracy Authors: S. Casacuberta, P. Gopalan, V. Kanade, O. Reingold | |
Embeddings into Similarity Measures for Nearest Neighbor Search Authors: A. Andoni, N. Nosatzki | Constant Rate Codes for Adaptive Broadcasts Do Not Exist Authors: K. Efremenko, G. Kol, D. Paramonov, R. Saxena | High dimensional online calibration in polynomial time Authors: B. Peng | |
Average-Distortion Sketching Authors: Y. Bao, A. Baweja, N. Menand, E. Waingarten, N. White, T. Zhang | List Decoding Expander-Based Codes up to Capacity in Near-Linear Time Authors: S. Srivastava, M. Tulsiani | Near-Optimal Algorithms for Omniprediction Authors: P. Okoroafor, B. Kleinberg, M. Kim | |
Query-Efficient Fixpoints of $\ell_p$-Contractions Authors: S. Haslebacher, J. Lill, P. Schnider, S. Weber | Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes Authors: S. Garg, A. Sengupta | Density Measures for Language Generation Authors: J. Kleinberg, F. Wei | |
| 12:02–1:30 | Lunch (provided) 🍽️ | ||
| 1:30–2:30 | Plenary 2Sebastien Bubeck, OpenAI (remote) | ||
| 2:30–3:10 | Break ☕ | ||
| 3:10–4:22 | Session 7A | Session 7B | Session 7C |
Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair Authors: L. Beretta, V. Cohen-Addad, R. Jayaram, E. Waingarten | Fingerprint Filters are Optimal Authors: W. Kuszmaul, J. Liang, R. Zhou | Overcomplete Tensor Decomposition via Koszul-Young Flattenings Authors: P. Kothari, A. Moitra, A. Wein | |
Root Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation Authors: D. Woodruff, T. Yasuda | Static Retrieval Revisited: To Optimality and Beyond Authors: Y. Hu, W. Kuszmaul, J. Liang, H. Yu, J. Zhang, R. Zhou | Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models Authors: I. Diakonikolas, D. Kane | |
Perfect L_p Sampling with Polylogarithmic Update Time Authors: W. Swartworth, D. Woodruff, S. Zhou | Stronger Cell Probe Lower Bounds via Local PRGs Authors: O. Korten, T. Pitassi, R. Impagliazzo | Robust Learning of Multi-index Models via Iterative Subspace Approximation Authors: I. Diakonikolas, G. Iakovidis, D. Kane, N. Zarifis | |
ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling Authors: N. Fischer, V. Nakos | Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance | Solving Zero-Sum Games with Fewer Matrix-Vector Products Authors: I. Karmarkar, L. O’Carroll, A. Sidford | |
| 4:22–4:40 | Break | ||
| 4:40–5:34 | Session 8A | Session 8B | Session 8C |
Fast Algorithms for Graph Arboricity and Related Problems Authors: R. Cen, H. Fleischmann, G. Li, J. Li, D. Panigrahi | Ramanujan bigraphs and applications Authors: S. Evra, B. Feigon, O. Parzanchevski, K. Maurischat | Faster exact learning of k-term DNFs with membership and equivalence queries Authors: J. Alman, S. Nadimpalli, S. Patel, R. Servedio | |
Dynamic Treewidth in Logarithmic Time Author: T. Korhonen | Extractors for Samplable Distributions with Polynomially Small Min-Entropy Authors: R. Shaltiel | Computational-Statistical Tradeoffs from NP-hardness Authors: G. Blanc, C. Koch, C. Strassle, L. Tan | |
Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ1-Oblivious Routings Authors: M. Probst, R. Kyng, T. Rieder | Finding Colorings in One-Sided Expanders Authors: R. Buhai, Y. Hua, D. Steurer, A. Vári-Kakas | Theoretical limitations of multi-layer Transformer Authors: L. Chen, B. Peng, H. Wu | |
| 5:24–6:00 | Break | ||
| 6:00–9:00 | Banquet @ Squire Landing 🍴🍷 | ||
| 9:00–10:30 | Session 9A | Session 9B | Session 9C |
| Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set Authors: M. Ghaffari, C. Grunau | On Inverse Theorems and Combinatorial Lines Authors: A. Bhangale, S. Khot, Y. Liu, D. Minzer | Characterization of Priority-Neutral Matching Lattices Authors: C. Thomas | |
| Parallel $(1+\epsilon)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work Authors: B. Haeupler, Y. Jiang, Y. Long, T. Saranurak, S. Wang | NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions Authors: S. Hirahara, R. Ilango | Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness Authors: X. Bu, B. Tao | |
| On the Parallel Complexity of Finding a Matroid Basis Authors: S. Khanna, A. Putterman, J. Song | The Proof Analysis Problem Authors: N. Arteche, A. Atserias, S. de Rezende, E. Khaniki | Beyond Regularity: Simple versus Optimal Mechanisms, Revisited Authors: Y. Feng, Y. Jin | |
| Constant Approximation of Arboricity in Near-Optimal Sublinear Time Authors: J. Dai, M. Ghaffari, J. Portmann | High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich Authors: R. Gao, A. Hollender, A. Rubinstein | Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More Authors: R. Bowers, M. Garbea, E. Pountourakis, S. Taggart | |
| Lower Bounds for Non-adaptive Local Computation Algorithms Authors: A. Azarmehr, S. Behnezhad, A. Ghafari, M. Sudan | Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences Authors: J. Leake, K. Lindberg, S. Gharan | Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade Authors: S. Di Gregorio, P. Duetting, F. Fusco, C. Schwiegelshohn | |
| 10:30–10:50 | Break ☕ | ||
|---|---|---|---|
| 10:50–12:02 | Session 10A | Session 10B | Session 10C |
| Radial Isotropic Position via an Implicit Newton’s Method Authors: A. Jambulapati, J. Li, K. Tian | Distributed Triangle Detection is Hard in Few Rounds Authors: S. Assadi, J. Sundaresan | On optimal distinguishers for Planted Clique Authors: A. Nagda, P. Raghavendra | |
| Faster logconcave sampling from a cold start in high dimension Authors: Y. Kook, S. Vempala | Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching Authors: S. Khoury, A. Schild | Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses Authors: M. Sellke | |
| Optimal Smoothed Analysis of the Simplex Method Authors: E. Bach, S. Huiberts | Multi-Pass Streaming Lower Bounds for Approximating Max-Cut Authors: Y. Fei, D. Minzer, S. Wang | The Quasi-Polynomial Low-Degree Conjecture is False Authors: R. Buhai, J. Hsieh, A. Jain, P. Kothari | |
| Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics Authors: H. An, M. Kao, C. Lee, M. Lee | A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams Authors: S. Khanna, A. Padaki, K. Singal, E. Waingarten | PTF Testing Lower Bounds for Non-Gaussian Component Analysis Authors: I. Diakonikolas, D. Kane, S. Liu, T. Pittas | |
| 12:02–1:30 | Lunch (provided) 🍽️ | ||
| 1:30–2:24 | Session 11A | Session 11B | Session 11C |
| Near-Optimal Property Testers for Pattern Matching Authors: C. Jin, T. Kociumaka | Efficiently Batching Unambiguous Interactive Proofs Authors: B. Berger, R. Goyal, M. Hong, Y. Kalai | Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension Authors: T. Chan, H. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D. Zheng | |
| Tight Pair Query Lower Bounds for Matching and Earth Mover’s Distance Authors: A. Azarmehr, S. Behnezhad, M. Roghani, A. Rubinstein | Improved Round-by-round Soundness IOPs via Reed-Muller Codes Authors: D. Minzer, K. Zheng | Shortest Paths on Convex Polyhedral Surfaces Authors: H. Wang | |
| Instance-Optimal Uniformity Testing and Tracking Authors: G. Blanc, C. Canonne, E. Waingarten | Proving Natural Distribution Properties is Harder than Testing Them Authors: T. Herman, G. Rothblum | Pattern Matching under Weighted Edit Distance Authors: P. Charalampopoulos, T. Kociumaka, P. Wellnitz | |
| 2:24–2:55 | Break ☕ | ||
| 2:55–4:25 | 🏆 Session 12Session chair: Rotem Oshman | ||
| Godel in Cryptography: Effectively Zero Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness Author: R. Ilango | |||
| Obfuscation of Unitary Quantum Programs Authors: M-Y. Huang, E-C. Tang | |||
| Explicit Lossless Vertex Expanders Authors: J-T. Hsieh, A. Lubotzky, S. Mohanty, A. Reiner, R. Y. Zhang | |||
| 4:25–4:50 | Break | ||
| 4:50–5:50 | 🏆 Session 13Session chair: Ran Raz | ||
| Quasipolynomial bounds for the corners theorem Authors: M. Jaber, Y. P. Liu, S. Lovett, A. Ostuni, M. Sawhney | |||
| Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest Authors: A. Ahmadi, I. Gholami, M. Hajiaghayi, P. Jabbarzade, M. Mahdavi | |||