October 27-30, 2024

Chicago, IL, USA

Program Schedule

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.

Day 1: Sunday, October 27, 2024

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:30amShang-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:00pmShang-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
Conference Lunch

 2:00pm – 3:30pmShang-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:00pmShang-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

 

Day 2: Monday, October 28, 2024

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. SimkinA 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

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

Day 3: Tuesday, October 29, 2024

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 3

Christos Papadimitriou, Columbia University

  

12pm – 1:30pm

Conference Lunch

1:30pm – 2:20pm

Session 5: Best Student Papers (Machtey Prize)

 
Capacity Threshold for the Ising Perceptron
Authors: B. Huang
 
Optimal quantile estimation: beyond the comparison model
Authors: M. Singhal, M. Gupta, H. Wu

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

Day 4: Wednesday, October 30, 2024

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
Authors: T. Yankovitz

and

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Authors: P. Kothari, P. Manohar

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

 
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Authors: B. Haeupler, R. Hladík, V. Rozhon, R. Tarjan, J. Tětek
 
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
Authors: M. Ghaffari, C. Grunau

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