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.
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 single-session 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, Shang-Hua Teng Fest, Workshop on Calibration, Industry Workshop.
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 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 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 ChicagoDual Reduction and Elementary Games with Senders and Receivers | ||
| 12:00 – 1:30pm | TCS-For-All 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 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 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. 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 | 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 | 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 | 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 University | ||||
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 Pennsylvania | ||||
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. 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 | Faster isomorphism testing of p-groups of Frattini class-2 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 single-session 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 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 chair: Xiaorui Sun) | Session 8B(Session chair: Idan Attias) | Session 8C(Session chair: Santosh Vempala) |
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 $n^{2+o(1)}$ 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(Session chair: Aravindan Vijayaraghavan) | ||
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 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. 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 | |||