All the times are in CDT (UTC05: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 WellLinked 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 dary Cuckoo Hashing up to the Load Threshold Authors: T. Bell, A. Frieze  On Approximate FullyDynamic Matching and Online MatrixVector Multiplication Authors: Y. Liu  
FirstOrder 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 kClustering with Fast Update Time and Small Recourse Authors: S. Bhattacharya, M. Costa, N. Garg, S. Lattanzi, N. Parotsidis  
Obstructions to ErdősPó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 PayoffBounded Tasks Authors: L. Hu, Y. Wu  
Minor Containment and Disjoint Paths in almostlinear time Authors: T. Korhonen, M. Pilipczuk, G. Stamoulis  Sampling, counting, and large deviations for trianglefree 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 3edgeconnected 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  
Threeedgecoloring 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 RuzsaSzemer’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 ReedSolomon codes Authors: R. Goyal, P. Harsha, M. Kumar, A. Shankar  Communication Separations for Truthful Auctions: Breaking the TwoPlayer 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 QuasiCyclic 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 lineardepth tdesigns and pseudorandom unitaries Authors: T. Metger, A. Poremba, M. Sinha, H. Yuen  
Expansion of highdimensional 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 QMA1hard 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. FarachColton, 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  InstanceOptimality in I/OEfficient 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 PatternAvoiding Sequences Authors: M. Opler  Faster isomorphism testing of pgroups of Frattini class2 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 
HighTemperature 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 
SumofSquares Lower Bounds for NonGaussian Component Analysis Authors: I. Diakonikolas, S. Karmalkar, S. Pang, A. Potechin 
Structure learning of Hamiltonians from realtime evolution Authors: A. Bakshi, A. Liu, A. Moitra, E. Tang 

DotProduct 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 BoundedDegree 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 AntiConcentration Beyond Gaussians Authors: A. Bakshi, P. Kothari, G. Rajendran, M. Tulsiani, A. Vijayaraghavan 
Quantum computational advantage with constanttemperature Gibbs sampling Authors: T. Bergamaschi, C. Chen, Y. Liu 

ChernoffHoeffding 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. SinclairBanks, K. Węgrzycki 

Commitments are equivalent to oneway state generators Authors: R. Batra, J. Rahul 
BenchmarkTight Approximation Ratio of Simple Mechanism for a UnitDemand 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 
SemiBandit Learning for Monotone Stochastic Optimization Authors: A. Agarwal, R. Ghuge, V. Nagarajan 
The Orthogonal Vectors Conjecture and NonUniform Circuit Lower Bounds Authors: R. Williams 

Certifying almost all quantum states with few singlequbit measurements Authors: H. Huang, J. Preskill, M. Soleimanifar 
On Robustness to kwise 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 EnvyFree 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 InstanceOptimal Euclidean Spanners Authors: H. Le, S. Solomon, C. Than, C. T\’oth, T. Zhang 
Nearoptimal Size Linear Sketches for Hypergraph Cut Sparsifiers Authors: S. Khanna, A. Putterman, M. Sudan 

Tight Bounds for the ZigZag 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 kMeans: Worst Case and Stability Optimal Coreset Bounds Authors: N. Bansal, V. CohenAddad, 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 liftmonotone 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 ChorGoldreich Sources Authors: J. Goodman, X. Li, D. Zuckerman 
New Structures and Algorithms for LengthConstrained 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 3LCC and Exponential Lower Bounds for Smooth 3LCCs and Sharp Bounds for Designs 
Gaussian Approximation of Convex Sets by Intersections of Halfspaces Authors: A. De, S. Nadimpalli, R. Servedio 
AlmostLinear Time Algorithms for Decremental Graphs: MinCost 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 Multiindex Models with Queries Authors: I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, N. Zarifis 
Dynamic Deterministic ConstantApproximate Distance Oracles with WorstCase Update Time Authors: B. Haeupler, Y. Long, T. Saranurak 

NearTight Bounds for 3Query 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 
LempelZiv (LZ77) Factorization in Sublinear Time Authors: D. Kempa, T. Kociumaka 

An Improved LinePoint LowDegree 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 codingtheoretic 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 
NearOptimal (1+ϵ)Approximate FullyDynamic AllPairs 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 BeyondWorstCase Heaps


NearOptimal 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. FarachColton, H. Komlos, M. Koucky, W. Kuszmaul, M. Saks 
The ESPRIT algorithm under high noise: Optimal error scaling and noisy superresolution Authors: Z. Ding, E. Epperly, L. Lin, R. Zhang 

Power Series Composition in NearLinear Time Authors: Y. Kinoshita, B. Li 
Stochastic Online Correlated Selection Authors: Z. Chen, Z. Huang, E. Sun 
ConstantDepth 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 NearOptimal 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 ParetoOptimal 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 