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 1## Roger Myerson, University of Chicago | ||

12:00 – 1:30pm | ## Conference Lunch | ||

| ## 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 2## Irit 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
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 3## Christos Papadimitriou, Columbia University | ||||

## 12pm – 1:30pm | ## Conference Lunch | ||||

## 1:30pm – 2:20pm | ## Session 5: Best Student Papers (Machtey Prize) | ||||

| |||||

| |||||

## 2:40 – 3:50pm | ## Knuth Prize Lecture## Rajeev 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
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 | ||

| |||

| |||

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