All the times are in CDT (UTC-05:00). The program given below shows the schedule of talks. The schedule of workshops and other activities will be updated later. You can download each day as a separate pdf here: day1.pdf, day2.pdf, day3.pdf, and day4.pdf. The abstracts of the plenary talks can be found here.
The planned events on Day 1 include Workshops, Graduating Bits and an Industry Workshop. The schedule of the workshops is as follows.
Workshop Session A | Workshop Session B | Workshop Session C | |
| 9:00am – 10:30am | Shang-Hua Teng Fest (organized by Dan Spielman and Xiaorui Sun) | Workshop on Calibration (organized by Jason Hartline, Jamie Morgenstern, Aaron Roth and Yifan Wu) | Recent Advances in Quantum Learning (organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li) |
| 10:30 – 11:00am | Break | ||
|---|---|---|---|
| 11:00am – 12:00pm | Shang-Hua Teng Fest (organized by Dan Spielman and Xiaorui Sun) | Workshop on Calibration (organized by Jason Hartline, Jamie Morgenstern, Aaron Roth and Yifan Wu) | Recent Advances in Quantum Learning (organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li) |
| 12:00pm – 2:00pm | Graduating Bits and | ||
| 2:00pm – 3:30pm | Shang-Hua Teng Fest (organized by Dan Spielman and Xiaorui Sun) | Distortion in Social Choice (organized by Moses Charikar, Prasanna Ramakrishnan, Nisarg Shah, and Kangning Wang) | Recent Advances in Quantum Learning (organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li) |
| 3:30pm – 4:00pm | Break | ||
| 4:00pm – 5:00pm | Shang-Hua Teng Fest (organized by Dan Spielman and Xiaorui Sun) | Distortion in Social Choice (organized by Moses Charikar, Prasanna Ramakrishnan, Nisarg Shah, and Kangning Wang) | Recent Advances in Quantum Learning (organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li) |
| 5:30pm – 8:00pm | Industry Workshop and Dinner | ||
9:00 – 10:30am | Session 1A | Session 1B | Session 1C |
| Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem Authors: M. Garlet Milani, S. Kreutzer, I. Muzi, M. Hatzel | O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold Authors: T. Bell, A. Frieze | On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication Authors: Y. Liu | |
| First-Order Model Checking on Monadically Stable Graph Classes Authors: J. Dreier, I. Eleftheriadis, N. Mählmann, R. McCarty, M. Pilipczuk, S. Toruńczyk | Fast Mixing in Sparse Random Ising Models Authors: K. Liu, S. Mohanty, A. Rajaraman, D. Wu | Fully Dynamic k-Clustering with Fast Update Time and Small Recourse Authors: S. Bhattacharya, M. Costa, N. Garg, S. Lattanzi, N. Parotsidis | |
| Obstructions to Erdős-Pósa Dualities for Minors Authors: C. Paul, E. Protopapas, D. Thilikos, S. Wiederrecht | A Sampling Lovász Local Lemma for Large Domain Sizes Authors: C. Wang, Y. Yin | Predict to Minimize Swap Regret for All Payoff-Bounded Tasks Authors: L. Hu, Y. Wu | |
| Minor Containment and Disjoint Paths in almost-linear time Authors: T. Korhonen, M. Pilipczuk, G. Stamoulis | Sampling, counting, and large deviations for triangle-free graphs near the critical density Authors: M. Jenssen, W. Perkins, A. Potukuchi, M. Simkin | A Lossless Deamortization for Dynamic Greedy Set Cover Authors: S. Solomon, A. Uzrad, T. Zhang | |
| Computing the 3-edge-connected components of directed graphs in linear time Authors: E. Kosinas, L. Georgiadis, G. Italiano | Computational Dynamical Systems Authors: J. Cotler, S. Rezchikov | The Online Submodular Assignment Problem Authors: S. Sarkar, D. Hathcock, M. Zlatin, B. Jin, K. Patton | |
| Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem Authors: Y. Inoue, K. Kawarabayashi, A. Miyashita, B. Mohar, T. Sonobe | Locally Stationary Distributions Authors: K. Liu, S. Mohanty, P. Raghavendra, A. Rajaraman, D. Wu | Fully Dynamic Matching and Ordered Ruzsa-Szemer’edi Graphs Authors: S. Behnezhad, A. Ghafari | |
| 10:30 – 10:50am | Break | ||
|---|---|---|---|
| 10:50 – 12:00 | Plenary 1Roger Myerson, University of Chicago | ||
| 12:00 – 1:30pm | Conference Lunch | ||
1:30pm – 2:30pm | Session 2A | Session 2B | Session 2C |
| Fast list decoding of univariate multiplicity and folded Reed-Solomon codes Authors: R. Goyal, P. Harsha, M. Kumar, A. Shankar | Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier Authors: S. Ron, C. Thomas, S. Weinberg, Q. Zhang | Efficient approximate unitary designs from random Pauli rotations Authors: J. Haah, Y. Liu, X. Tan | |
| Decoding Quasi-Cyclic Quantum LDPC Codes Authors: L. Golowich, V. Guruswami | On Pigeonhole Principles and Ramsey in TFNP Authors: S. Jain, J. Li, R. Robere, Z. Xun | Efficient Unitary Designs from Random Sums and Permutations Authors: C. Chen, J. Docter, M. Xu, A. Bouland, F. Brandao, P. Hayden | |
| Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications Authors: S. Hirahara, Z. Lu, M. Nanashima | An XOR Lemma for Deterministic Communication Complexity Authors: S. Iyer, A. Rao | Simple constructions of linear-depth t-designs and pseudorandom unitaries Authors: T. Metger, A. Poremba, M. Sinha, H. Yuen | |
| Expansion of high-dimensional cubical complexes with application to quantum locally testable codes Authors: I. Dinur, T. Lin, T. Vidick | The Communication Complexity of Approximating Matrix Rank Authors: A. Sherstov, A. Storozhenko | Gapped Clique Homology is QMA1-hard and contained in QMA Authors: R. King, T. Kohler | |
| 2:40 – 3:50pm | Plenary 2Irit Dinur, Weizmann Institute | ||
| 3:55 – 4:15 | Break | ||
| 4:15 – 5:30PM | Session 3A | Session 3B | Session 3C |
| Reverse Mathematics of Complexity Lower Bounds Authors: L. Chen, J. Li, I. Oliveira | Optimal Bounds for Open Addressing Without Reordering Authors: M. Farach-Colton, A. Krapivin, W. Kuszmaul | Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint Authors: N. Buchbinder, M. Feldman | |
| Interactive Proofs for General Distribution Properties Authors: T. Herman, G. Rothblum | Tight Analyses of Ordered and Unordered Linear Probing Authors: M. Braverman, W. Kuszmaul | On Approximating Cutwidth and Pathwidth Authors: N. Bansal, D. Katzelnick, R. Schwartz | |
| Trading Determinism for Noncommutativity in Edmonds’ Problem Authors: V. Arvind, A. Chatterjee, P. Mukhopadhyay | Tight Bounds for Classical Open Addressing Authors: M. Bender, W. Kuszmaul, R. Zhou | The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2. Authors: J. Byrka, F. Grandoni, V. Traub | |
| \Pi_2^p vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem Authors: D. Zhuk | Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation Authors: S. Narayanan, V. Rozhoň, J. Tětek, M. Thorup | Efficient Approximation of Hypertree Width Authors: V. Surianarayanan, D. Lokshtanov, S. Saurabh, J. Xue, V. Korchemna | |
| Jump operators, Interactive Proofs and Proof Complexity Generators Authors: E. Khaniki | An Optimal Algorithm for Sorting Pattern-Avoiding Sequences Authors: M. Opler | Faster isomorphism testing of p-groups of Frattini class-2 Authors: G. Ivanyos, E. Mendoza, Y. Qiao, X. Sun, C. Zhang | |
| 6pm | Business Meeting | ||
9:00 – 10:30am | Session 4A | Session 4B | Session 4C | ||
| Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable Authors: S. Mouli | Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the Dimension Threshold Authors: V. Guruswami, J. Hsieh, P. Raghavendra | High-Temperature Gibbs States are Unentangled and Efficiently Preparable Authors: A. Bakshi, A. Liu, A. Moitra, E. Tang | |||
| A Dense Model Theorem for the Boolean Slice Authors: G. Kalai, N. Lifshitz, T. Ziegler, D. Minzer | Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis Authors: I. Diakonikolas, S. Karmalkar, S. Pang, A. Potechin | Structure learning of Hamiltonians from real-time evolution Authors: A. Bakshi, A. Liu, A. Moitra, E. Tang | |||
| Dot-Product Proofs and Their Applications Authors: N. Bitansky, P. Harsha, Y. Ishai, R. Rothblum, D. Wu | Semirandom Planted Clique and the Restricted Isometry Property Authors: J. Błasiok, R. Buhai, P. Kothari, D. Steurer | Quantum eigenvalue processing Authors: G. Low, Y. Su | |||
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs Authors: Y. Dikstein, I. Dinur, A. Lubotzky and and Constant Degree Direct Product Testers with Small Soundness Authors: M. Bafna, N. Lifshitz, D. Minzer | Efficient Certificates of Anti-Concentration Beyond Gaussians Authors: A. Bakshi, P. Kothari, G. Rajendran, M. Tulsiani, A. Vijayaraghavan | Quantum computational advantage with constant-temperature Gibbs sampling Authors: T. Bergamaschi, C. Chen, Y. Liu | |||
| Chernoff-Hoeffding and Reverse Hypercontractivity on High Dimensional Expanders Authors: Y. Dikstein, M. Hopkins | Tensor cumulants for statistical inference on invariant distributions Authors: D. Kunisky, C. Moore, A. Wein | Optimal tradeoffs for estimating Pauli observables Authors: S. Chen, W. Gong, Q. Ye | |||
| New investigations into noncommutative CSPs Authors: E. Culf, H. Mousavi, T. Spirig | Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians Authors: J. Lee, A. Mehrotra, M. Zampetakis | A computational test of quantum contextuality, and even simpler proofs of quantumness Authors: A. Arora, A. Coladangelo, A. Cojocaru, K. Bharti | |||
10:30 – 10:50am | Break | ||||
|---|---|---|---|---|---|
10:50 – 12:00 | Plenary 3Christos Papadimitriou, Columbia University | ||||
12pm – 1:30pm | Conference Lunch | ||||
1:30pm – 2:20pm | Session 5: Best Student Papers (Machtey Prize) | ||||
Capacity Threshold for the Ising Perceptron | |||||
Optimal quantile estimation: beyond the comparison model | |||||
2:40 – 3:50pm | Knuth Prize LectureRajeev Alur, University of Pennsylvania | ||||
3:55 – 4:15 | Break | ||||
4:15 – 5:30pm | Session 6A | Session 6B | Session 6C | ||
| Proofs of Space with Maximal Hardness Authors: L. Reyzin | Online Combinatorial Allocations and Auctions with Few Samples Authors: P. Duetting, T. Kesselheim, B. Lucier, R. Reiffenhauser, S. Singla | The Tractability Border of Reachability in Simple Vector Addition Systems with States Authors: D. Chistikov, W. Czerwiński, Ł. Orlikowski, F. Mazowiecki, H. Sinclair-Banks, K. Węgrzycki | |||
| Commitments are equivalent to one-way state generators Authors: R. Batra, J. Rahul | Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer Authors: Y. Jin, P. Lu | Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares Authors: M. Abrahamsen, J. Stade | |||
| Succinct arguments for QMA from standard assumptions via compiled nonlocal games Authors: T. Metger, A. Natarajan, T. Zhang | Semi-Bandit Learning for Monotone Stochastic Optimization Authors: A. Agarwal, R. Ghuge, V. Nagarajan | The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds Authors: R. Williams | |||
| Certifying almost all quantum states with few single-qubit measurements Authors: H. Huang, J. Preskill, M. Soleimanifar | On Robustness to k-wise Independence of Optimal Bayesian Mechanisms Authors: N. Gravin, Z. Wang | Strong vs. Weak Range Avoidance and the Linear Ordering Principle Authors: O. Korten, T. Pitassi | |||
| How to Simulate Random Oracles with Auxiliary Input Authors: Y. Dodis, A. Jain, R. Lin, J. Luo, D. Wichs | Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting Authors: R. Gao, M. Roghani, A. Rubinstein, A. Saberi | Canonical forms for matrix tuples in polynomial time Authors: Y. Qiao, X. Sun | |||
9:00 – 10:30am | Session 7A | Session 7B | Session 7C |
| Boosting uniformity in quasirandom groups: faster and simpler Authors: E. Viola, H. Derksern, C. Lee | Improved Distance (Sensitivity) Oracles with Subquadratic Space Authors: D. Bilò, S. Chechik, K. Choudhary, S. Cohen, T. Friedrich, M. Schirneck | Replicability in High Dimensional Statistics Authors: M. Hopkins, R. Impagliazzo, D. Kane, S. Liu, C. Ye | |
| The sample complexity of smooth boosting and the tightness of the hardcore theorem Authors: G. Blanc, A. Hayderi, C. Koch, L. Tan | Sparse graph counting and Kelley–Meka bounds for binary systems Authors: Y. Filmus, H. Hatami, K. Hosseini, E. Kelman | Computing Approximate Centerpoints in Polynomial Time Authors: Y. Cherapanamjeri | |
| On the Existence of Seedless Condensers: Exploring the Terrain Authors: E. Chattopadhyay, M. Gurumukhani, N. Ringach | Towards Instance-Optimal Euclidean Spanners Authors: H. Le, S. Solomon, C. Than, C. T\’oth, T. Zhang | Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers Authors: S. Khanna, A. Putterman, M. Sudan | |
| Tight Bounds for the Zig-Zag Product Authors: G. Cohen, G. Maor, I. Cohen | Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems Authors: F. Eisenbrand, L. Rohwedder, K. Wegrzycki | Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds Authors: N. Bansal, V. Cohen-Addad, M. Prabhu, D. Saulpic, C. Schwiegelshohn | |
| Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness Authors: J. Li, E. Pyne, R. Tell | Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs Authors: X. Yu, D. Kunisky | Novel properties of hierarchical probabilistic partitions and their algorithmic applications Authors: S. Banerjee, Y. Bartal, L. Gottlieb, A. Hovav | |
| Improved Condensers for Chor-Goldreich Sources Authors: J. Goodman, X. Li, D. Zuckerman | New Structures and Algorithms for Length-Constrained Expander Decompositions Authors: B. Haeupler, D Hershkowitz, Z. Tan | Spectral Guarantees for Adversarial Streaming PCA Authors: Z. Xun, E. Price | |
10:30 – 10:50am | Break | ||
|---|---|---|---|
10:50 – 12:05pm | Session 8A | Session 8B | Session 8C |
A stronger bound for linear 3-LCC and Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs | Gaussian Approximation of Convex Sets by Intersections of Halfspaces Authors: A. De, S. Nadimpalli, R. Servedio | Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality Authors: J. van den Brand, L. Chen, R. Kyng, Y. Liu, S. Meierhans, M. Gutenberg, S. Sachdeva | |
| Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric Authors: Z. Guo, C. Xing, C. Yuan, Z. Zhang | Agnostically Learning Multi-index Models with Queries Authors: I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, N. Zarifis | Dynamic Deterministic Constant-Approximate Distance Oracles with Worst-Case Update Time Authors: B. Haeupler, Y. Long, T. Saranurak | |
| Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles Authors: O. Alrabiah, V. Guruswami | Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning Authors: N. Golowich, A. Moitra, D. Rohatgi | Lempel-Ziv (LZ77) Factorization in Sublinear Time Authors: D. Kempa, T. Kociumaka | |
| An Improved Line-Point Low-Degree Test Authors: P. Harsha, M. Kumar, R. Saptharishi, M. Sudan | Revisiting Agnostic PAC Learning Authors: S. Hanneke, K. Larsen, N. Zhivotovskiy | Maximum Flow by Augmenting Paths in Time Authors: A. Bernstein, J. Blikstad, T. Saranurak, T. Tu | |
| Fast decision tree learning solves hard coding-theoretic problems Authors: C. Koch, C. Strassle, L. Tan | Ramsey Theorems for Trees and a General ‘Private Learning Implies Online Learning’ Theorem Authors: S. Fioravanti, S. Hanneke, S. Moran, H. Schefler, I. Tsubari | Near-Optimal (1+ϵ)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs Authors: A. Filtser, G. Goranci, N. Patel, M. Gutenberg | |
12:05 – 1:30pm | Conference Lunch | ||
1:30pm – 2:20pm | Session 9: Best Papers | ||
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps | |||
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS | |||
2:20 – 2:45 | Break | ||
2:45 – 4:15pm | Session 10A | Session 10B | Session 10C |
| Verifying Groups in Linear Time Authors: O. Klein, I. Komargodski, S. Evra, S. Gadot | Nearly Optimal List Labeling Authors: M. Bender, A. Conway, M. Farach-Colton, H. Komlos, M. Koucky, W. Kuszmaul, M. Saks | The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution Authors: Z. Ding, E. Epperly, L. Lin, R. Zhang | |
| Power Series Composition in Near-Linear Time Authors: Y. Kinoshita, B. Li | Stochastic Online Correlated Selection Authors: Z. Chen, Z. Huang, E. Sun | Constant-Depth Arithmetic Circuits for Linear Algebra Problems Authors: R. Andrews, A. Wigderson | |
| Faster (Δ+1)-Edge Coloring: Breaking the Time Barrier Authors: S. Bhattacharya, D. Carmon, M. Costa, S. Solomon, T. Zhang | Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach Authors: R. Pinto Jr. | Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems Authors: H. Hirai, K. Sakabe | |
| An Improved Pseudopolynomial Time Algorithm for Subset Sum Authors: L. Chen, J. Lian, Y. Mao, G. Zhang | Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy Authors: K. Dvijotham, H. McMahan, K. Pillutla, T. Steinke, A. Thakurta | On the Complexity of Avoiding Heavy Elements Authors: Z. Lu, I. Oliveira, H. Ren, R. Santhanam | |
| Naively Sorting Evolving Data is Optimal and Robust Authors: G. Giakkoupis, M. Kiwi, D. Los | A Strong Separation for Adversarially Robust Estimation for Linear Sketches Authors: E. Gribelyuk, H. Lin, D. Woodruff, H. Yu, S. Zhou | Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems Authors: M. Blanchard | |
| Tight Bounds for Sorting Under Partial Information Authors: I. van der Hoog, D. Rutschmann | |||