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.
The planned events on Day 1 include Workshops, Graduating Bits and an industry engagement activity. The schedule is TBD.
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 | 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 |
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 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 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 |
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 |
|||