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. 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.
Proceedings: The proceedings can be accessed here (the username and password have been sent to conference attendees over email). The abstracts of all the accepted papers can be found here.
The main conference location is Floor 14. The session rooms are in Floors 14 and 15.
Session Rooms: Session A will be in Sauganash East (Floor 14), Session B is in Western Stage House (Floor 14), and Session C is in Lasalle (Floor 15). All plenaries and singlesession activities will be in Sauganash East. Lunch can be picked up in the Sauganash West room (Floor 14).
Room Assignments: Session A will be in Sauganash East (14th floor), Session B is in Western Stage House (14th floor), and Session C is in Lasalle (Floor 15).
The planned events on Day 1 include Workshops, Graduating Bits and an Industry Workshop. The schedule of the workshops is as follows. You can access the detailed schedules for the workshops using the following links: Distortion in Social Choice, Recent Advances in Quantum Learning, ShangHua Teng Fest, Workshop on Calibration, Industry Workshop.
Workshop Session A  Workshop Session B  Workshop Session C  
9:00am – 10:30am  ShangHua 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  ShangHua 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  ShangHua 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  ShangHua 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 Session 
9:00 – 10:30am 
Session 1A
(Session chair: Xiaorui Sun) 
Session 1B(Session chair: Kalen Patton) 
Session 1C(Session chair: Dionysios Arvanitakis) 
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 ChicagoDual Reduction and Elementary Games with Senders and Receivers 

12:00 – 1:30pm 
TCSForAll Best Research Practices Talk by Ankur Moitra


1:30pm – 2:30pm 
Session 2A(Session chair: Ioannis Panageas) 
Session 2B(Session chair: Anxin (Bob) Guo) 
Session 2C(Session chair: Sean Hallgren) 
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 InstituteExpanders and PCPs: Emergence from Local to Global 

3:55 – 4:15 
Break 

4:15 – 5:30PM 
Session 3A(Chair: Meena Mahajan) 
Session 3B(Chair: Yang Liu) 
Session 3C(Chair: Santosh Vempala) 
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 
Canonical forms for matrix tuples in polynomial time Authors: Y. Qiao, X. Sun 

6pm 
Business Meeting 
Room Assignments: Session A will be in Sauganash East (14th floor), Session B is in Western Stage House (14th floor), and Session C is in Lasalle (Floor 15). Lunch can picked up from the Sauganash West room (14th floor).
9:00 – 10:30am  Session 4A(Session chair: Maryam Aliakbarpour)  Session 4B(Session chair: Santosh Vempala)  Session 4C(Session chair: Sean Hallgren)  
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  Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians Authors: J. Lee, A. Mehrotra, M. Zampetakis  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  Tensor cumulants for statistical inference on invariant distributions Authors: D. Kunisky, C. Moore, A. Wein  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 UniversityComputing with Dynamical Systems  
12pm – 1:30pm  Conference Lunch  
1:30pm – 2:20pm  Session 5: Best Student Papers (Machtey Prize)(Session chair: Santosh Vempala)  
Capacity Threshold for the Ising Perceptron  
Optimal quantile estimation: beyond the comparison model  
2:40 – 3:50pm  Knuth Prize LectureRajeev Alur, University of PennsylvaniaSpecificationguided Reinforcement Learning  
3:55 – 4:15  Break  
4:15 – 5:30pm  Session 6A(Session chair: He Jia)  Session 6B(Session chair: Chang Wang)  Session 6C(Session chair: Emanuele Viola)  
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  Faster isomorphism testing of pgroups of Frattini class2 Authors: G. Ivanyos, E. Mendoza, Y. Qiao, X. Sun, C. Zhang 
Room Assignments: Session A will be in Sauganash East (14th floor), Session B is in Western Stage House (14th floor), and Session C is in Lasalle (Floor 15). All plenaries and singlesession activities will be Sauganash East. Lunch can picked up from the Sauganash West room (14th floor).
9:00 – 10:30am  Session 7A(Session chair: Santosh Vempala)  Session 7B(Session chair: Yang Liu)  Session 7C(Session chair: Dionysios Arvanitakis) 
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 chair: Xiaorui Sun)  Session 8B(Session chair: Idan Attias)  Session 8C(Session chair: Santosh Vempala) 
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 $n^{2+o(1)}$ 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  Conference Lunch  
1:30pm – 2:20pm  Session 9: Best Papers(Session chair: Aravindan Vijayaraghavan)  
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 chair: He Jia)  Session 10B(Session chair: Vaidehi Srinivas)  Session 10C(Session chair: Santosh Vempala) 
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 