All the times are in AEDT (UTC +11). Additional (social) activities are or will be listed on the corresponding page: fun runs, walks, etc.
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) |
Approximate Nearest Neighbor Search: Bridging Theoretical Foundations and Industrial Frontiers
(organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) |
Space: Connecting Classical and Catalytic Approaches
(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) |
Approximate Nearest Neighbor Search: Bridging Theoretical Foundations and Industrial Frontiers
(organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) |
Space: Connecting Classical and Catalytic Approaches
(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) |
Approximate Nearest Neighbor Search: Bridging Theoretical Foundations and Industrial Frontiers
(organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) |
The Localization Method for High-dimensional Inequalities
(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) |
Approximate Nearest Neighbor Search: Bridging Theoretical Foundations and Industrial Frontiers
(organized by Piotr Indyk, Rajesh Jayaram, and Ravi Krishnaswamy) |
The Localization Method for High-dimensional Inequalities
(organized by Santosh S. Vempala) |
| 4:30–4:45 |
Break |
||
| 4:45–5:30 |
Graduating bits 🎓 |
||
| 6:00–8:00 |
Welcome Reception 🥂 |
||
| 9:00–10:30 | Session 1A(Blackwattle 1) | Session 1B(Blackwattle 2) | Session 1C(Blackwattle 3) |
| 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) Author: 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 Author: 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(Blackwattle 1) | Session 2B(Blackwattle 2) | Session 2C(Blackwattle 3) |
| Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time via Dynamic Representative Sets Author: J. Nederlof | Structural properties of the factorization norm 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 | ||
| 2:30–3:00 | Break ☕ | ||
| 3:00–4:12 | Session 3A(Blackwattle 1) | Session 3B(Blackwattle 2) | Session 3C(Blackwattle 3) |
| 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(Blackwattle 1) | Session 4B(Blackwattle 2) | Session 4C(Blackwattle 3) |
| 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 (Blackwattle 1) |
Session 5B (Blackwattle 2) |
Session 5C (Blackwattle 3) |
| 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 |
Characterization of Priority-Neutral Matching Lattices Authors: C. Thomas |
|
| 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 |
Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness Authors: X. Bu, B. Tao |
|
| 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 |
Beyond Regularity: Simple versus Optimal Mechanisms, Revisited Authors: Y. Feng, Y. Jin |
|
| 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 |
Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More Authors: R. Bowers, M. Garbea, E. Pountourakis, S. Taggart |
|
| 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 |
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 6A (Blackwattle 1) |
Session 6B (Blackwattle 2) |
Session 6C (Blackwattle 3) |
| 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:40 |
Plenary 2Sebastien Bubeck (OpenAI) |
||
| 2:40–3:10 |
Break ☕ |
||
| 3:10–4:22 |
Session 7A (Blackwattle 1) |
Session 7B (Blackwattle 2) |
Session 7C (Blackwattle 3) |
| 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 |
Pattern Matching under Weighted Edit Distance
Authors: P. Charalampopoulos, T. Kociumaka, P. Wellnitz |
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 (Blackwattle 1) |
Session 8B (Blackwattle 2) |
Session 8C (Blackwattle 3) |
| 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 (Blackwattle 1) |
Session 9B (Blackwattle 2) |
Session 9C (Blackwattle 3) |
| 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 (Blackwattle 1) |
Session 10B (Blackwattle 2) |
Session 10C (Blackwattle 3) |
| 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 (Blackwattle 1) |
Session 11B (Blackwattle 2) |
Session 11C (Blackwattle 3) |
| 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 |
Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance Authors: D. Das, J. Gilbert, T. Kociumaka, M. Hajiaghayi, B. Saha |
|
| 2:24–2:55 |
Break ☕ |
||
| 2:55–3:55 |
🏆 Best student papers |
||
| 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 |
|||
| 3:55–4:20 |
Break |
||
| 4:20–5:50 |
🏆 Best papers |
||
| Explicit Lossless Vertex Expanders Authors: J-T. Hsieh, A. Lubotzky, S. Mohanty, A. Reiner, R. Y. Zhang |
|||
| Quasipolynomial bounds for the corners theorem Authors: M. Jaber, Y. P. Liu, S. Lovett, A. Ostuni, M. Sawhney |
|||
| Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest Authors: A. Ahmadi, I. Gholami, M. Hajiaghayi, P. Jabbarzade, M. Mahdavi |
|||