All times are local.
|
Workshop: Machine Learning for Algorithms
Room: Grand Ballroom A
Chair: Nina Balcan, Avrim Blum, Piotr Indyk, Ali Vakilian
|
Workshop: (Hyper)graph Problems via Global Queries
Room: Grand Ballroom B
Chair: Deeparnab Chakrabarty and Sagnik Mukhopadhyay
|
Workshop: Random Purification Channel
Room: Alpine Ballroom A
Chair: Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright
|
Room: Alpine Ballroom B
Chair: Noah Golowich, Allen Liu, Abhishek Shetty
|
|---|
| Time |
Session 1: Best Papers and Best Student Papers
Room: Grand Ballroom
Chair: Chair TBD
|
|---|---|
| 11:00 |
Lower Estimates for L_1-Distortion of Transportation Cost Spaces
|
| 11:18 |
Separating QMA from QCMA with a classical oracle
|
| 11:36 |
Boolean function monotonicity testing requires (almost) n^1/2 queries
|
| 11:54 |
NP-membership for the boundary-boundary art-gallery problem
|
| 12:12 |
MIPco=coRE
|
| Time |
Session 2A: Negative-Weight Shortest Paths
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 2B: Market Equilibrium, Trade, and Welfare
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 2C: Concentration and Derandomization
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 2D: CSP and Proof Complexity
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 14:15 |
Deterministic Padded Decompositions and Negative-Weight Shortest Paths
|
Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium
|
Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
|
Near Optimal Hardness of Approximating k-CSP
|
| 14:33 |
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
|
Tâtonnement Dynamics for Fisher Markets with Chores
|
Derandomizing Matrix Concentration Inequalities from Free Probability
|
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
|
| 14:51 |
Shortcutting for Negative-Weight Shortest Paths
|
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
|
Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
|
Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
|
| 15:09 |
From Hop Reduction to Sparsification for Negative Length Shortest Paths
|
Approximating Gains-from-Trade in Matching Markets
|
Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysis
|
Lower Bounds against the Ideal Proof System in Finite Fields
|
| 15:27 |
Reviving Thorup's Shortcut Conjecture
|
Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
|
Monte Carlo to Las Vegas for Recursively Composed Functions
|
The Weak Rank Principle: Lower Bounds and Applications
|
| 15:45 |
Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
|
Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
|
On the Informativeness of Moments in Optimal Stopping
|
Lower Bounds for Near-Quadratic-Depth Resolution over Parities
|
| Time |
Session 3A: Reed-Solomon Structure and List Decoding
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 3B: Packing, Scheduling, and Stochastic Covering
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 3C: SNARGs, SNARKs, and PCPs
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 3D: Streaming and Dynamic Algorithms
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 16:30 |
Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities
|
Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
|
SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to use the simplicity of cryptographic reasoning)
|
A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
|
| 16:48 |
On proximity gaps of Reed-Solomon codes
|
Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center
|
SNARGs for NP and Non-Signaling PCPs, Revisited
|
Semi-Streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints
|
| 17:06 |
Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
|
An Optimal Algorithm for Stochastic Vertex Cover
|
SNARKs from LWE via Non-black-box Reductions
|
Half-Approximating Maximum Dicut in the Streaming Setting
|
| 17:24 |
Deterministic list decoding of Reed-Solomon codes
|
Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
|
Ideals, Macaulay Bases, and PCPs
|
A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
|
| 17:42 |
High Rate Efficient Local List Decoding from HDX
|
Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
|
Secret-Key PIR from Random Linear Codes
|
Adversarial Robustness on Insertion-Deletion Streams
|
|
Workshop: Machine Learning for Algorithms
Room: Grand Ballroom A
Chair: Nina Balcan, Avrim Blum, Piotr Indyk, Ali Vakilian
|
Workshop: (Hyper)graph Problems via Global Queries
Room: Grand Ballroom B
Chair: Deeparnab Chakrabarty and Sagnik Mukhopadhyay
|
Workshop: Random Purification Channel
Room: Alpine Ballroom A
Chair: Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright
|
Room: Alpine Ballroom B
Chair: Noah Golowich, Allen Liu, Abhishek Shetty
|
|---|
| Time |
Session 4A: Connectivity and Routing
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 4B: Randomness, Extractors, and Randomized Encodings
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 4C: Lattice Hardness and Communication
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 4D: Online Privacy and Adversarial Data Access
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 11:00 |
Steiner Forest: A Simplified Better-Than-2 Approximation
|
Fast and Compact Random Mappings with Uniform Guarantees and Applications
|
Deterministic Hardness of Approximation of Unique-SVP and GapSVP in Lp norms for p>2
|
Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
|
| 11:18 |
Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
|
Extractors for Samplable Distributions from the Two-Source Extractor Recipe
|
SVP_p is NP-Hard for all p > 2, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
|
The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms
|
| 11:36 |
Randomized Rounding over Dynamic Programs
|
Improved Bounds for Coin Flipping, Leader Election, and Random Selection
|
Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
|
Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
|
| 11:54 |
A Constant-Factor Approximation for Directed Latency
|
Improved Pseudorandom Codes from Permuted Puzzles
|
Sub-Linear Secure Broadcast and Applications
|
Efficient Calibration for Decision Making
|
| 12:12 |
Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier
|
Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions
|
Optimal Contest beyond Convexity
|
Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
|
| Time |
Session 5A: Network Design
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 5B: Fine-Grained and String Algorithms
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 5C: Distributed Algorithms and Coordination
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 5D: Algebraic Complexity and Arithmetic Reconstruction
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 14:15 |
Perfect Network Resilience in Polynomial Time
|
Approximation schemes for Edit Distance and LCS in quasi-strongly subquadratic time
|
Breaking Barriers for Distributed MIS by Faster Degree Reduction
|
Closure under factorization from a result of Furstenberg
|
| 14:33 |
A Strong Linear Programming Relaxation for Weighted Tree Augmentation
|
Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
|
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
|
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
|
| 14:51 |
A Polylogarithmic Approximation for Buy-at-Bulk Network Design with Protection
|
Approximate Orthogonal Vectors and Diameter via Regularity Lemma
|
What Can Be Computed Locally Revisited - First-Order Logic on Sparse Graphs in Distributed Computing -
|
Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system
|
| 15:09 |
Nonuniform graph partitioning with just a little flex
|
Beating Meet-in-the-Middle for Subset Balancing Problems
|
Contention Resolution, With and Without a Global Clock
|
Learning Read-Once Determinants and the Principal Minor Assignment Problem
|
| 15:27 |
Lower Bounds on Flow Sparsifiers with Steiner Nodes
|
Space-Efficient Dictionary Matching with Mismatches Using Function Inversion
|
Can Like Attract Like? A Study of Homonymous Gathering in Networks
|
Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-in
|
| 15:45 |
DAG Projections: Reducing Distance and Flow Problems to DAGs
|
A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
|
The Complexity of Min-Max Optimization with Product Constraints
|
Strong ETH Holds for Bounded-Depth Resolution over Parities
|
| Time |
Session 6A: Quantum Algorithms
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 6B: Directed Cuts and Flows
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 6C: High-Dimensional Inference and Low-Degree Limits
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 6D: Circuit Lower Bounds and Small-Depth Power
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 16:30 |
Efficient Quantum Hermite Transform
|
Almost-Optimal Approximation Algorithm for Global Minimum Cut in Directed Graphs
|
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
|
Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits
|
| 16:48 |
Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
|
Approximating Directed Connectivity in Almost-Linear Time
|
High-Accuracy List-Decodable Mean Estimation
|
Monotone Circuit Complexity of Matching
|
| 17:06 |
Fast Mixing of Quantum Spin Chains at All Temperatures
|
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
|
Rigorous Implications of the Low-Degree Heuristic
|
Negations are powerful even in small depth
|
| 17:24 |
A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
|
An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
|
Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
|
Improved Lower Bounds for QAC0
|
| 17:42 |
Approximation does not help in quantum unitary time-reversal
|
On the Learning Curves of Revenue Maximization
|
Sparse Linear Regression is Easy on Random Supports
|
The natural proofs barrier against data-structure lower-bounds
|
|
Workshop: Machine Learning for Algorithms
Room: Grand Ballroom A
Chair: Nina Balcan, Avrim Blum, Piotr Indyk, Ali Vakilian
|
Workshop: (Hyper)graph Problems via Global Queries
Room: Grand Ballroom B
Chair: Deeparnab Chakrabarty and Sagnik Mukhopadhyay
|
Workshop: Random Purification Channel
Room: Alpine Ballroom A
Chair: Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright
|
Room: Alpine Ballroom B
Chair: Noah Golowich, Allen Liu, Abhishek Shetty
|
|---|
| Time |
Session 7A: Quantum Complexity, Lower Bounds, and Advantage
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 7B: Halfspaces, Replicability, and Private Learning
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 7C: Geometry and Euclidean Approximation
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 7D: Optimization and Sampling
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 14:15 |
No exponential quantum speedup for SIS∞ anymore
|
Borsuk-Ulam and replicable learning of large-margin halfspaces
|
Fine-Grained Complexity of Continuous Euclidean k-Center
|
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
|
| 14:33 |
Quantum circuit lower bounds in the magic hierarchy
|
A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
|
Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
|
Trust Region Interior Point Methods: Optimal L2- and Faster Wide-Neighborhood Path Following
|
| 14:51 |
On the Need for (Quantum) Memory with Short Outputs
|
The Sample Complexity of Replicable Realizable PAC Learning
|
Near-Optimal Directed Euclidean Spanners in High Dimensions
|
Hesse’s Redemption: Efficient Convex Polynomial Programming
|
| 15:09 |
On the Cryptographic Foundations of Interactive Quantum Advantage
|
Private Learning of Littlestone Classes, Revisited
|
A (4+ϵ)-Approximation for Euclidean k-Means via Non-Monotone Dual-Fitting
|
Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
|
| 15:27 |
Few Single-Qubit Measurements Suffice to Certify Any Quantum State
|
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
|
Locally Computable High Independence Hashing
|
Parallel Sampling via Autospeculation
|
| Time |
Session 8A: Structural Reconstruction and Hypergraph Optimization
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 8B: Computability, Diophantine Problems, and Algebraic Identities
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 8C: Dynamic, Streaming, Kernelization
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 8D: Stabilizers, Cliffords, and Quantum State Structure
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 16:15 |
Optimal Phylogenetic Reconstruction from Sampled Quartets
|
Determination of the fifth Busy Beaver value
|
Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
|
Learning stabilizer structure of quantum states
|
| 16:33 |
A Poisson Process for Submodular Maximization
|
S-unit equations in modules and linear-exponential Diophantine equations
|
Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
|
Clifford testing: algorithms and lower bounds
|
| 16:51 |
Optimal and Efficient Partite Decompositions of Hypergraphs
|
The Skolem Problem in rings of positive characteristic
|
Settling the Pass Complexity of Streaming Set Cover
|
Average-Case Complexity of Quantum Stabilizer Decoding
|
| 17:09 |
Combinatorial Markov Search
|
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
|
A Dichotomy Theorem for Multi-Pass Streaming CSPs
|
Magic and communication complexity
|
| 17:27 |
Combinatorial Optimization using Comparison Oracles
|
Dynamic Meta-Kernelization
|
Instance-Optimal Quantum State Certification with Entangled Measurements
|
|
Workshop: Understanding LLMs via TCS
Room: Grand Ballroom A
Chair: Anay Mehrotra, Amin Saberi, Grigoris Velegkas
|
Workshop: New Algorithm Foundations for Crypto
Room: Grand Ballroom B
Chair: Aayush Jain, Amit Sahai
|
Workshop: Testing in the Modern World
Room: Alpine Ballroom A
Chair: Anindya De and Shivam Nadimpalli
|
Workshop: Graduating Bits
Room: Alpine Ballroom B
Chair: Organizers TBD
|
|---|
| Time |
Session 9A: Parameterized Graph Algorithms
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 9B: Search, Unambiguity, and Feasible Reasoning
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 9C: Modern Learning Theory and Sequence Models
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 9D: Statistical Physics and Markov Chains
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 14:15 |
Forbidden Subgraphs of Graphs with Low Bandwidth
|
A Theory for Probabilistic Polynomial-Time Reasoning
|
Smoothed Analysis of Learning from Positive Samples
|
On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses
|
| 14:33 |
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
|
Range avoidance, Arthur-Merlin, and TFNP
|
Better neural network expressivity: subdividing the simplex
|
Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime
|
| 14:51 |
Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs
|
Reach Unambiguous Logspace is almost in Logspace
|
On the Computational Hardness of Transformers
|
Mixing of general biased adjacent transposition chains
|
| 15:09 |
Fine-Grained Bounds for Courcelle's Theorem
|
Pseudodeterministic Communication Complexity
|
Provable Long-Range Benefits of Next-Token Prediction
|
Markov Chains Approximate Message Passing
|
| 15:27 |
Oracle Subset Problems: A Meta-Algorithm for FPT Approximation via Random Walks
|
Hardness Amplification Beyond Boolean Functions
|
Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
|
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
|
| 15:45 |
Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations
|
|
Workshop: Understanding LLMs via TCS
Room: Grand Ballroom A
Chair: Anay Mehrotra, Amin Saberi, Grigoris Velegkas
|
Workshop: New Algorithm Foundations for Crypto
Room: Grand Ballroom B
Chair: Aayush Jain, Amit Sahai
|
Workshop: Testing in the Modern World
Room: Alpine Ballroom A
Chair: Anindya De and Shivam Nadimpalli
|
Workshop: Rising Stars
Room: Alpine Ballroom B
Chair: TCS4All
|
|---|
| Time |
Session 10A: Sparse, Minor-Free, and Planar Structure
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 10B: Boolean Testing and Sparsity
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 10C: Quantum Cryptography
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 10D: Local Properties and Local Decodability of Codes
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 14:15 |
Separator Theorem for Minor-Free Graphs in Linear Time
|
A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
|
A Meta-Complexity Characterization of Minimal Quantum Cryptography
|
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
|
| 14:33 |
Efficient reversal of transductions of sparse graph classes
|
Restriction Trees for Sparsity and Applications
|
Average hardness of SIVP for module lattices of fixed rank
|
From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids
|
| 14:51 |
A Graph Minors Approach to Temporal Sequences
|
Testing noisy low-degree polynomials for sparsity
|
Compressed Permutation Oracles
|
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
|
| 15:09 |
Cutting Planarians: Planar Emulators for String Graphs
|
Learning Functions of Halfspaces
|
The power of two bases: nearly robust and copy-optimal certification of nearly all quantum states with single-qubit measurements
|
3-Query RLDCs are Strictly Stronger than 3-Query LDCs
|
| 15:27 |
Planar Length-Constrained Minimum Spanning Trees
|
Learning CNF formulas from uniform random solutions in the local lemma regime
|
The debiased Keyl's algorithm: a new unbiased estimator for full state tomography
|
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
|
| Time |
Session 11A: Data Structures, Hashing, and Lower Bounds
Room: Grand Ballroom A
Chair: Chair TBD
|
Session 11B: Online Learning, Games, and Matrix Optimization
Room: Grand Ballroom B
Chair: Chair TBD
|
Session 11C: Noise, Spectra, and Functional Inequalities
Room: Alpine Ballroom A
Chair: Chair TBD
|
Session 11D: Meta-Complexity, Kolmogorov, and Inductive Inference
Room: Alpine Ballroom B
Chair: Chair TBD
|
|---|---|---|---|---|
| 16:15 |
Sampling Permutations with Cell Probes is Hard
|
The Price of Competitive Information Disclosure
|
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
|
A Sharp Characterization of Pessiland
|
| 16:33 |
Greedy Open Addressing Revisited: Beyond Yao's Lower Bound
|
Online Combinatorial Optimization with Graphical Dependencies
|
Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
|
Complexity-Theoretic Universal Inductive Inference
|
| 16:51 |
Memory Reallocation with Polylogarithmic Overhead
|
Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
|
Sparsifying Suprema of Gaussian Processes
|
Optimal Random Self-Reductions for All Linear Problems
|
| 17:09 |
Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
|
First-order (coarse) correlated equilibria in non-concave games
|
Fourier Spectrum of Noisy Quantum Algorithms
|
Kolmogorov's Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity
|
| 17:27 |
Solving Matrix Games with Near-Optimal Matvec Complexity
|
Testing Distributions Against Bounded Distinguishers
|
Failure of Symmetry of Information for Randomized Computations
|
|
Workshop
Room: Grand Ballroom
|
|---|