| STOC 2024 Program | ||||||||||||
| Monday June 24 |
Grand Ballroom
Workshop A
|
9:00-11:00 |
|
Grand Ballroom
Session 1A: Best Papers (single session)
Chair: Ryan O'Donnell
|
11:15 | Single-Source Shortest Paths with Negative Real Weights in Õ(mn8/9) Time
Jeremy T. Fineman (Georgetown University) |
11:33 | Near Optimal Alphabet-Soundness Tradeoff PCPs
Dor Minzer, Kai Zhe Zheng (MIT) |
11:51 | Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Venkatesan Guruswami (University of California, Berkeley); Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Kewen Wu (University of California, Berkeley) |
|
12:15 |
Junior Ballroom Foyer
Lunch (boxed lunch provided)
|
|
12:30-14:00 |
Grand Ballroom
|
|
Grand Ballroom
Session 2A
Chair: Fabrizio Grandoni
|
Junior Ballroom AB
Session 2B
Chair: Benjamin Rossman
|
Junior Ballroom C
Session 2C
Chair: Frederic Koehler
|
Junior Ballroom D
Session 2D
Chair: Jan Vondrak
|
14:15 | Online Edge Coloring is (Nearly) as Easy as Offline
Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); Ola Svensson, Radu Vintan (EPFL); David Wajc (Technion — Israel Institute of Technology) |
Strong Algebras and Radical Sylvester-Gallai Configurations
Rafael Oliveira, Akash Kumar Sengupta (University of Waterloo) |
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane (University of California, San Diego); Vasilis Kontonis (University of Texas, Austin); Sihan Liu (University of California, San Diego); Nikos Zarifis (University of Wisconsin-Madison) |
The Power of Two-sided Recruitment in Two-sided Markets
Yang Cai (Yale University); Christopher Liaw, Aranyak Mehta (Google); Mingfei Zhao (Google Research) |
14:33 | Approximate Earth Mover's Distance in Truly-Subquadratic Time
Lorenzo Beretta (BARC, University of Copenhagen); Aviad Rubinstein (Stanford University) |
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai Mathematical Institute, India); Abhranil Chatterjee (Indian Statistical Institute, Kolkata, India); Partha Mukhopadhyay (Chennai Mathematical Institute, India) |
Calibrated Language Models Must Hallucinate
Adam Tauman Kalai (Microsoft Research); Santosh Vempala (Georgia Tech) |
Strategic Budget Selection in a Competitive Autobidding World
Yiding Feng (University of Chicago); Brendan Lucier, Aleksandrs Slivkins (Microsoft Research) |
14:51 | Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss (University of Warwick); Aaron Sidford (Stanford University); David Wajc (Technion) |
The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups
Bireswar Das, Dhara Thakkar (IIT Gandhinagar) |
Private graphon estimation via sum-of-squares
Hongjie Chen, Jingqiu Ding (ETH Zürich); Tommaso D'Orsi (Bocconi University); Yiding Hua (ETH Zürich); Chih-Hung Liu (National Taiwan University); David Steurer (ETH Zürich) |
The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
Nicolo Cesa-Bianchi (University of Milan); Tommaso Cesari (University of Ottawa); Roberto Colomboni (Italian Institute of Technology & University of Milan); Federico Fusco (Sapienza); Stefano Leonardi (University of Rome La Sapienza) |
15:09 | Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler (ETH Zurich); D Ellis Hershkowitz (Brown University); Jason Li (UC Berkeley); Antti Röyskö (ETH Zurich); Thatchaphol Saranurak (University of Michigan) |
Learning the coefficients: A presentable version of border complexity and applications to circuit factoring
C. S. Bhargav, Prateek Dwivedi, Nitin Saxena (Department of Computer Science & Engg., Indian Institute of Technology Kanpur) |
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi (MIT) |
Bilateral Trade with Correlated Values
Shahar Dobzinski (Weizmann); Ariel Shaulker (Weizmann Institute) |
15:27 | Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial Algorithm
Julia Chuzhoy (Toyota Technological Institute at Chicago); Sanjeev Khanna (University of Pennsylvania) |
On the Power of Homogeneous Algebraic Formulas
Hervé Fournier (IMJ-PRG, Université Paris Cité); Nutan Limaye (IT University of Copenhagen); Srikanth Srinivasan (University of Copenhagen); Sébastien Tavenas (Université Savoie Mont Blanc, CNRS, LAMA) |
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Spencer Compton, Gregory Valiant (Stanford University) |
No-Regret Learning in Bilateral Trade via Global Budget Balance
Martino Bernasconi (Bocconi University); Matteo Castiglioni (Politecnico di Milano); Andrea Celli (Bocconi University); Federico Fusco (Sapienza University of Rome) |
|
15:45 |
Junior Ballroom Foyer
Coffee Break
|
|
16:15-17:45 |
Grand Ballroom
TCS4All Workshop (continued)
|
|
18:00-19:00 |
Pavilion Ballroom ABC
Reception
|
|
|
| Tuesday June 25 |
Grand Ballroom
Workshop A
|
Junior Ballroom D
Workshop B
|
9:00-11:00 |
|
Grand Ballroom
Plenary talk
|
11:15 |
Tim Roughgarden (Columbia University and a16z crypto): The Computer in the Sky
|
|
12:15 |
Lunch (on your own)
|
|
Grand Ballroom
Session 3A
Chair: Tomasz Kociumaka
|
Junior Ballroom AB
Session 3B
Chair: Frederic Koehler
|
Junior Ballroom C
Session 3C
Chair: Fermi Ma
|
Junior Ballroom D
Session 3D
Chair: Sahil Singla
|
14:15 | Knapsack with Small Items in Near-Quadratic Time
Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics) Joint talk with 0-1 Knapsack in Nearly Quadratic Time
Ce Jin (MIT) |
Testing Closeness of Multivariate Distributions via Ramsey Theory
Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane, Sihan Liu (University of California, San Diego) |
Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Brent Waters (University of Texas at Austin and NTT Research); David J. Wu (University of Texas at Austin) |
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University) |
14:33 | A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University) Joint talk with (1 − ε)-Approximation of Knapsack in Nearly Quadratic Time
Xiao Mao (Stanford University) |
Semidefinite programs simulate approximate message passing robustly
Misha Ivkov, Tselil Schramm (Stanford) |
A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
Brent Waters (University of Texas at Austin and NTT Research) |
Structural Complexities of Matching Mechanisms
Yannai A. Gonczarowski (Harvard University); Clayton Thomas (Microsoft Research) |
14:51 | Approximating Partition in Near-Linear Time
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University) |
Planted Clique Conjectures Are Equivalent
Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Tokyo Institute of Technology) |
Optimal Load-Balanced Scalable Distributed Agreement
Yuval Gelles (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research) |
A constant-factor approximation for Nash social welfare with subadditive valuations
Shahar Dobzinski (Weizmann Institute); Wenzheng Li, Aviad Rubinstein, Jan Vondrak (Stanford University) |
15:09 | Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee (University of Michigan); Jason Li (UC Berkeley); Thatchaphol Saranurak (University of Michigan) |
Robust recovery for stochastic block models, simplified and generalized
Sidhanth Mohanty (MIT); Prasad Raghavendra, David Wu (U.C. Berkeley) |
Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs
Thomas Debris-Alazard (Inria); Pouria Fallahpour (ENS de Lyon, France); Damien Stehlé (CryptoLab Inc, Lyon, France) |
Limitations of Stochastic Selection Problems with Pairwise Independent Priors
Shaddin Dughmi, Yusuf Kalayci, Neel Patel (University of Southern California) |
15:27 | Better coloring of 3-colorable graphs
Ken-ichi Kawarabayashi (National Institute of Informatics, The university of Tokyo); Mikkel Thorup (University of Copenhagen); Hirotaka Yoneda (The university of Tokyo) |
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Aditya Bhaskara (University of Utah); Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan (Northwestern University) |
Batch Proofs are Statistically Hiding
Nir Bitansky (Tel Aviv University); Chethan Kamath (IIT Bombay); Omer Paneth (Tel Aviv University); Ron D. Rothblum (Technion); Prashant Nalini Vasudevan (NUS) |
Prophet Inequalities Require Only a Constant Number of Samples
Andres Cristi (Universidad de Chile); Bruno Ziliotto (CNRS) |
|
15:45 |
Junior Ballroom Foyer
Coffee Break
|
|
Grand Ballroom
Session 4A
Chair: Stanislav Živný
|
Junior Ballroom AB
Session 4B
Chair: Daochen Wang
|
Junior Ballroom C
Session 4C
Chair: Siyao Guo
|
Junior Ballroom D
Session 4D
Chair: Bundit Laekhanukit
|
16:15 | A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
Jason Gaitonde (Massachusetts Institute of Technology); Elchanan Mossel (MIT) |
Classical simulation of peaked shallow quantum circuits
Sergey Bravyi (IBM Quantum, T. J. Watson Research Center); David Gosset, Yinchen Liu (University of Waterloo) |
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
Yilei Chen (Tsinghua University and Shanghai Qi Zhi Institute); Jiatu Li (Massachusetts Institute of Technology) |
Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma (Freie Universität Berlin); Michal Opler (Czech Technical University in Prague) |
16:33 | Nonlinear dynamics for the Ising model
Pietro Caputo (Univ Rome III); Alistair Sinclair (U.C. Berkeley) |
Quantum Time-Space Tradeoffs for Matrix Problems
Paul Beame (University of Washington); Niels Kornerup (University of Texas at Austin); Michael Whitmeyer (University of Washington) |
Communication Lower Bounds for Collision Problems via Density Increment Arguments
Guangxu Yang, Jiapeng Zhang (University of Southern California) |
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland (University of California at Santa Barbara); Daniel Lokshtanov (University of California Santa Barbara, USA); Tomáš Masarík, Marcin Pilipczuk, Michal Pilipczuk (University of Warsaw); Pawel Rzazewski (Warsaw University of Technology) |
16:51 | Influences in Mixing Measures
Frederic Koehler (Stanford University); Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer, Elchanan Mossel (MIT) |
Circuit-to-Hamiltonian from tensor networks and fault tolerance
Anurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Quynh T Nguyen (Harvard University) |
Lower bounds for regular resolution over parities
Klim Efremenko (Ben-Gurion University of the Negev); Michal Garlik (Imperial College London); Dmitry Itsykson (Ben-Gurion University of the Negev) |
Packing even directed circuits quarter-integrally
Maximilian Gorsky (Technische Universität Berlin); Sebastian Wiederrecht (Institute for Basic Science, South Korea); Stephan Kreutzer (Technische Universität Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) |
17:09 | Parallel Sampling via Counting
Nima Anari, Ruiquan Gao, Aviad Rubinstein (Stanford University) |
Quantum and classical query complexities of functions of matrices
Ashley Montanaro (University of Bristol); Changpeng Shao (Academy of Mathematics and Systems Science, Chinese Academy of Sciences) |
XOR Lemmas for Communication via Marginal Information
Siddharth Iyer (University of Washington); Anup Rao (School of Computer Science, University of Washington) |
Edge-Disjoint Paths in Eulerian Digraphs
Dario Giuliano Cavallaro (TU Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Stephan Kreutzer (TU Berlin) |
17:27 | On The Fourier Coefficients of High-Dimensional Random Geometric Graphs
Kiril Bangachev, Guy Bresler (MIT) |
Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
Saeed Mehraban (Tufts University); Mehrdad Tahmasbi (UIUC) |
Beating Brute Force for Compression Problems
Shuichi Hirahara (National Institute of Informatics, Tokyo, Japan); Rahul Ilango, Ryan Williams (MIT) |
A Flat Wall Theorem for Matching Minors in Bipartite Graphs
Archontia C. Giannopoulou (Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece); Sebastian Wiederrecht (Discrete Mathematics Group, IBS, Daejeon, South Korea) |
|
18:00 |
Pavilion Ballroom ABC
Estimathon
|
|
|
| Wednesday June 26 |
Grand Ballroom
Workshop A
|
Junior Ballroom D
Workshop B
|
Junior Ballroom C
Workshop C
|
9:00-11:00 |
|
Grand Ballroom
Plenary talk
|
11:15 |
Jakub Pachocki (OpenAI): Scaling Up Deep Learning
|
|
12:15 |
Lunch (on your own)
|
|
Grand Ballroom
Session 5A
Chair: Amey Bhangale
|
Junior Ballroom D
Session 5B
Chair: Soheil Behnezhad
|
Junior Ballroom C
Session 5C
Chair: Stanislav Živný
|
14:15 | Generalized GM-MDS: Polynomial Codes are Higher Order MDS
Joshua Brakensiek (Stanford University); Manik Dhar (MIT); Sivakanth Gopi (Microsoft Research) Joint talk with AG codes achieve list decoding capacity over constant-sized fields
Joshua Brakensiek (Stanford University); Manik Dhar (MIT); Sivakanth Gopi (Microsoft Research); Zihan Zhang (The Ohio State University) |
Data-Dependent LSH for the Earth Mover’s Distance
Rajesh Jayaram (Google Research); Erik Waingarten, Tian Zhang (University of Pennsylvania) |
The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True
Andreas Björklund (IT University of Copenhagen); Petteri Kaski (Aalto University) Joint talk with A stronger connection between the asymptotic rank conjecture and the set cover conjecture
Kevin Pratt (New York University) |
14:33 | Constant Query Local Decoding Against Deletions is Impossible
Meghal Gupta (UC Berkeley) |
Polylog-Competitive Deterministic Local Routing and Scheduling
Bernhard Haeupler (ETH Zurich & CMU); Shyamal Patel (Columbia University); Antti Roeyskoe (ETH Zurich); Cliff Stein (Columbia University); Goran Zuzic (Google Research) |
Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
Swee Hong Chan (Rutgers University); Igor Pak (UCLA) |
14:51 | Local Correction of Linear Functions over the Boolean Cube
Prashanth Amireddy (Harvard University); Amik Raj Behera (Aarhus University); Manaswi Paraashar, Srikanth Srinivasan (University of Copenhagen); Madhu Sudan (Harvard University) |
Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka (Weizmann Institute of Science); Seth Pettie (University of Michigan) |
Semigroup algorithmic problems in metabelian groups
Ruiwen Dong (University of Oxford) |
15:09 | An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University) |
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams
Sepehr Assadi (University of Waterloo and Rutgers University); Gillat Kol, Zhijun Zhang (Princeton University) |
The Complexity of Computing KKT Solutions of Quadratic Programs
John Fearnley (University of Liverpool); Paul W. Goldberg, Alexandros Hollender (University of Oxford); Rahul Savani (University of Liverpool) |
15:27 | Explicit two-sided unique-neighbor expanders
Jun-Ting Hsieh (Carnegie Mellon University); Theo McKenzie (Stanford University); Sidhanth Mohanty (MIT); Pedro Paredes (Princeton University) |
O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set
Sepehr Assadi (Rutgers University and University of Waterloo); Christian Konrad, Kheeran K. Naidu (University of Bristol); Janani Sundaresan (University of Waterloo) |
Minimum Star Partitions of Simple Polygons in Polynomial Time
Mikkel Abrahamsen (University of Copenhagen); Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); André Nusser, Hanwen Zhang (University of Copenhagen) |
|
15:45 |
Junior Ballroom Foyer
Coffee Break
|
|
Grand Ballroom
Session 6A
Chair: Ohad Trabelsi
|
Junior Ballroom AB
Session 6B
Chair: Fang Song
|
Junior Ballroom C
Session 6C
Chair: Avishay Tal
|
Junior Ballroom D
Session 6D
Chair: Ainesh Bakshi
|
16:15 | Revisiting Local Computation of PageRank: Simple and Optimal
Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang (Renmin University of China) |
Commitments from Quantum One-Wayness
Dakshita Khurana (University of Illinois at Urbana-Champaign); Kabir Tomer (University of Illinois Urbana-Champaign) |
Detecting Low-Degree Truncation
Anindya De, Huan Li (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University) |
Local geometry of NAE-SAT solutions in the condensation regime
Allan Sly (Princeton University); Youngtak Sohn (MIT) |
16:33 | Towards Optimal Output-Sensitive Clique Listing
Mina Dalirrooyfard, Surya Mathialagan, Yinzhan Xu, Virginia Vassilevska Williams (MIT) |
A one-query lower bound for unitary synthesis and breaking quantum cryptography
Alex Lombardi (Princeton); Fermi Ma (Simons Institute and UC Berkeley); John Wright (UC Berkeley) |
Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli, Shyamal Patel (Columbia University) |
Trickle-Down in Localization Schemes and Applications
Nima Anari, Frederic Koehler, Thuy-Duong Vuong (Stanford University) |
16:51 | New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer (Weizmann Institute of Science); Zander Kelley (University of Illinois at Urbana-Champaign); Shachar Lovett (UCSD); Raghu Meka (UCLA) |
Two prover perfect zero knowledge for MIP*
Kieran Mastel, William Slofstra (University of Waterloo) |
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Xi Chen (Columbia University); Yumou Fei (Peking University); Shyamal Patel (Columbia University) |
Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, Mark Rudelson (University of Michigan) |
17:09 | Nearly Optimal Fault Tolerant Distance Oracle
Dipan Dey, Manoj Gupta (IIT Gandhinagar) |
How to Use Quantum Indistinguishability Obfuscation
Andrea Coladangelo (University of Washington); Sam Gunn (UC Berkeley) Joint talk with Quantum State Obfuscation from Classical Oracles
James Bartusek (UC Berkeley); Zvika Brakerski (Weizmann); Vinod Vaikuntanathan (MIT CSAIL) |
On the Power of Interactive Proofs for Learning
Tom Gur (University of Cambridge); Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh (Simon Fraser University); Ninad Rajgopal (University of Cambridge); Bahar Salamatian, Igor Shinkar (Simon Fraser University) |
Solving Dense Linear Systems Faster than via Preconditioning
Michal Derezinski, Jiaming Yang (University of Michigan) |
17:27 | Almost Linear Size Edit Distance Sketch
Michal Koucký (Charles University/Rutgers University); Michael Saks (Rutgers University) |
Nonlocality under Computational Assumptions
Grzegorz Gluch, Khashayar Barooti (EPFL); Alexandru Gheorghiu (Chalmers University of Technology); Marc-Olivier Renou (Inria, Universitée Paris-Saclay, CPHT, Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau) |
Complexity-Theoretic Implications of Multicalibration
Sílvia Casacuberta (University of Oxford); Cynthia Dwork, Salil Vadhan (Harvard University) |
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri (MIT); Yin Tat Lee (University Washington and Microsoft Research); Swati Padmanabhan (MIT); William Swartworth, David P. Woodruff (Carnegie Mellon University); Guanghao Ye (MIT) |
|
18:00 |
Grand Ballroom
Business Meeting
|
|
|
| Thursday June 27 |
Grand Ballroom
Workshop D
|
Junior Ballroom D
Workshop B
|
Junior Ballroom C
Workshop C
|
8:30-11:00 |
|
|
9:00-11:00 |
|
|
Grand Ballroom D
Plenary talk
|
11:15 |
Michal Feldman (Tel Aviv University): Algorithmic Contract Design
|
|
12:15 |
Lunch (on your own)
|
|
Grand Ballroom
Session 7A
Chair: Fabrizio Grandoni
|
Junior Ballroom AB
Session 7B
Chair: Sahil Singla
|
Junior Ballroom C
Session 7C
Chair: Amey Bhangale
|
Junior Ballroom D
Session 7D
Chair: Ainesh Bakshi
|
14:15 | Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
Xiao Mao (Stanford University) |
Settling the Communication Complexity of VCG-based Mechanisms for All Approximation Guarantees
Frederick Qiu, S. Matthew Weinberg (Princeton University) |
Explicit orthogonal arrays and universal hashing with arbitrary parameters
Nicholas Harvey, Arvin Sahami (UBC) |
An area law for the maximally-mixed ground state in arbitrarily degenerate systems with good AGSP
Itai Arad (Centre for Quantum Technologies); Raz Firanko (Technion); Rahul Jain (National University of Singapore) |
14:33 | Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval
William Kuszmaul (Harvard University); Stefan Walzer (Karlsruhe Institute of Technology) |
PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas (University of Edinburgh); Kristoffer Arnsfelt Hansen, Kasper Høgh (Aarhus University); Alexandros Hollender (University of Oxford) |
Tree Evaluation is in Space O(log n · log log n)
James Cook; Ian Mertz (University of Warwick) |
Local minima in quantum systems
Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou (California Institute of Technology) |
14:51 | Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
Li Chen (Carnegie Mellon University); Rasmus Kyng (ETH Zurich); Yang P. Liu (Institute for Advanced Study); Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich) |
From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
Yuval Dagan (UC Berkeley); Constantinos Daskalakis (EECS, MIT); Maxwell Fishelson (Massachusetts Institute of Technology); Noah Golowich (MIT) Joint talk with Fast swap regret minimization and applications to approximate correlated equilibria
Binghui Peng (Columbia University); Aviad Rubinstein (Stanford University) |
Locality Bounds for Sampling Hamming Slices
Daniel M. Kane, Anthony Ostuni (UC San Diego); Kewen Wu (UC Berkeley) |
An optimal tradeoff between entanglement and copy complexity for state tomography
Sitan Chen (Harvard University); Jerry Li (Microsoft Research); Allen Liu (MIT) |
15:09 | A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich) |
Fair Division via Quantile Shares
Yakov Babichenko (Technion - Israel Institute of Technology); Michal Feldman (Tel Aviv University); Ron Holzman (Technion - Israel Institute of Technology); Vishnu V. Narayan (Tel Aviv University) |
No Complete Problem for Constant-Cost Randomized Communication
Yuting Fang (The Ohio State University); Lianna Hambardzumyan (The Hebrew University of Jerusalem); Nathaniel Harms (EPFL); Pooya Hatami (The Ohio State University) |
Learning shallow quantum circuits
Hsin-Yuan Huang (Caltech); Yunchao Liu (UC Berkeley); Michael Broughton (Google Quantum AI); Isaac Kim (UC Davis); Anurag Anshu (Harvard University); Zeph Landau (UC Berkeley); Jarrod R. McClean (Google Quantum AI) |
15:27 | Dynamic O(arboricity) coloring in polylogarithmic worst-case time
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich) |
Prophet Inequalities with Recourse
Farbod Ekbatani, Rad Niazadeh (University of Chicago Booth School of Business); Pranav Nuti, Jan Vondrak (Stanford) |
Explicit separations between randomized and deterministic Number-on-Forehead communication
Zander Kelley (University of Illinois at Urbana-Champaign); Shachar Lovett (UCSD); Raghu Meka (UCLA) |
Improved Stabilizer Estimation via Bell Difference Sampling
Sabee Grewal, Vishnu Iyer (University of Texas at Austin); William Kretschmer (Simons Institute); Daniel Liang (Rice University) |
|
15:45 |
Junior Ballroom Foyer
Coffee Break
|
|
Grand Ballroom
Session 8A
Chair: Rafael Mendes de Oliveira
|
Junior Ballroom AB
Session 8B
Chair: Pravesh Kothari
|
Junior Ballroom C
Session 8C
Chair: Saeed Mehraban
|
Junior Ballroom D
Session 8D
Chair: Tomasz Kociumaka
|
16:15 | Computing a Fixed Point of Contraction Maps in Polynomial Queries
Xi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University) |
Product Mixing in Compact Lie Groups
David Ellis (University of Bristol); Guy Kindler, Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer (MIT) |
Learning quantum Hamiltonians at any temperature in polynomial time
Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley) |
Counting Small Induced Subgraphs with Edge-monotone Properties
Simon Döring (Max Planck Institute for Informatics; Saarbrücken Graduate School of Computer Science; Saarland Informatics Campus); Dániel Marx (CISPA Helmholtz Center for Information Security); Philip Wellnitz (Max Planck Institute for Informatics; Saarland Informatics Campus) |
16:33 | Self-Improvement for Circuit-Analysis Problems
Ryan Williams (MIT) |
On Approximability of Satisfiable k-CSPs: IV
Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT) |
An efficient quantum parallel repetition theorem and applications
John Bostanci (Columbia University); Luowen Qian (Boston University); Nick Spooner (University of Warwick & NYU); Henry Yuen (Columbia University) |
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin (TTIC) |
16:51 | Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
Benjamin Rossman (Duke University) |
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
Shuichi Hirahara (National Institute of Informatics); Naoto Ohsaka (CyberAgent, Inc.) |
The Power of Adaptivity in Quantum Query Algorithms
Uma Girish (Princeton University); Makrand Sinha (University of Illinois at Urbana-Champaign); Avishay Tal, Kewen Wu (University of California at Berkeley) |
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
Tuukka Korhonen (University of Bergen); Marek Sokolowski (University of Warsaw) |
17:09 | Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London) |
Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
Uriya A. First (University of Haifa); Tali Kaufman (Bar Ilan University) |
On the Pauli Spectrum of QAC0
Shivam Nadimpalli, Natalie Parham (Columbia University); Francisca Vasconcelos (University of California, Berkeley); Henry Yuen (Columbia University) |
Combinatorial Characterizations of Monadically NIP Graph Classes
Jan Dreier (TU Wien); Nikolas Mählmann (University of Bremen); Szymon Torunczyk (University of Warsaw) |
17:27 | Black-Box PPP is Not Turing-Closed
Noah Fleming (Memorial University of Newfoundland); Stefan Grosser (McGill); Toniann Pitassi (Columbia); Robert Robere (McGill) |
Randomly punctured Reed–Solomon codes achieve list-decoding capacity over linear-sized fields
Omar Alrabiah, Venkatesan Guruswami (UC Berkeley); Ray Li (Santa Clara University) |
Approaching the Quantum Singleton Bound with Approximate Error Correction
Thiago Bergamaschi, Louis Golowich, Sam Gunn (UC Berkeley) |
A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column
Daniel Dadush, Zhuan Khye Koh (CWI Amsterdam); Bento Natura (Georgia Institute of Technology); Neil Olver, László A. Végh (London School of Economics) |
|
18:00 |
Grand Ballroom
Turing Award Lecture: Avi Wigderson
|
|
|
19:30 |
Banquet
|
|
|
| Friday June 28 |
Grand Ballroom
Workshop D
|
Junior Ballroom C
Workshop C
|
8:30-11:00 |
|
9:00-11:00 |
|
|
Grand Ballroom
Session 9A: Best Student Papers
Chair: Ryan O'Donnell
|
11:15 | Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin, Yinzhan Xu (MIT) |
11:33 | Relaxed Local Correctability from Local Testing
Vinayak M. Kumar, Geoffrey Mon (University of Texas at Austin) |
|
12:15 |
Lunch (on your own)
|
|
Grand Ballroom
Session 10A
Chair: Ohad Trabelsi
|
Junior Ballroom AB
Session 10B
Chair: Lap Chi Lau
|
Junior Ballroom C
Session 10C
Chair: Siyao Guo
|
Junior Ballroom D
Session 10D
Chair: Artur Czumaj
|
14:15 | On Optimal Coreset Construction for Euclidean (k,z)-clustering
Lingxiao Huang (Nanjing University); Jian Li, Xuan Wu (Tsinghua University) |
Reconfiguration of Basis Pairs in Regular Matroids
Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz (Eötvös Loránd University) |
Memory Checking Requires Logarithmic Overhead
Elette Boyle (Reichman University and NTT Research); Ilan Komargodski (Hebrew University and NTT Research); Neekon Vafa (MIT) |
On the Communication Complexity of Approximate Pattern Matching
Tomasz Kociumaka (Max Planck Institute for Informatics, SIC); Jakob Nogler (ETH Zurich); Philip Wellnitz (Max Planck Institute for Informatics, SIC) |
14:33 | Understanding the Cluster Linear Program for Correlation Clustering
Nairen Cao (Boston College); Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (Nanjing University); Alantha Newman (CNRS-Université Grenoble Alpes); Lukas Vogl (Ecole Polytechnique Federale de Lausanne) |
Sparsifying generalized linear models
Arun Jambulapati (Simons Institute); James R Lee (University of Washington); Yang P. Liu (Institute for Advanced Study); Aaron Sidford (Stanford University) |
Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor (University of Cambridge); Nicholas Spooner (University of Warwick/NYU) |
Local Borsuk-Ulam, Stability, and Replicability
Zachary Chase, Bogdan Chornomaz, Shay Moran (Technion); Amir Yehudayoff (Technion-IIT) |
14:51 | Combinatorial Correlation Clustering
Vincent Cohen-Addad (Google Research, France); Marcin Pilipczuk (University of Warsaw); David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan, Hanwen Zhang (University of Copenhagen) |
Sampling Balanced Forests of Grids in Polynomial Time
Sarah Cannon (Claremont McKenna College); Wesley Pegden (Carnegie Mellon University); Jamie Tucker-Foltz (Harvard University) |
One-Way Functions and Zero Knowledge
Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology) |
A New Information Complexity Measure for Multi-Pass Streaming with Applications
Mark Braverman (Princeton University); Sumegha Garg (Rutgers University); Qian Li (Shenzhen Research Institute of Big Data); Shuo Wang (Shanghai Jiao Tong University); David P. Woodruff (CMU); Jiapeng Zhang (University of Southern California) |
15:09 | Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
Calum MacRury, Will Ma (Columbia University) |
Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors
Yulin Wang, Chihao Zhang (Shanghai Jiao Tong University); Zihan Zhang (Graduate Institute for Advanced Studies, SOKENDAI) |
Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie (NYU Shanghai); Yuping Ye (East China Normal University and NYU Shanghai) |
New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Eric Blais, Cameron Seth (University of Waterloo) |
15:27 | Prize-Collecting Steiner Tree: A 1.79 Approximation
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi (University of Maryland) |
Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen (Duke University); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University) |
SNARGs Under LWE via Propositional Proofs
Zhengzhong Jin (MIT CSAIL); Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Princeton); Vinod Vaikuntanathan (MIT CSAIL) |
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
John Kallaugher, Ojas Parekh (Sandia National Laboratories); Nadezhda Voronova (Boston University) |
|
15:45 |
Junior Ballroom Foyer
Coffee Break
|
|
Grand Ballroom
Session 11A
Chair: Bundit Laekhanukit
|
Junior Ballroom AB
Session 11B
Chair: Mahsa Derakhshan
|
Junior Ballroom C
Session 11C
Chair: Lap Chi Lau
|
Junior Ballroom D
Session 11D
Chair: Avishay Tal
|
16:15 | Proof of the density threshold conjecture for pinwheel scheduling
Akitoshi Kawamura (Kyoto University) |
Breaking the VLB Barrier for Oblivious Reconfigurable Networks
Tegan Wilson, Daniel Amir, Nitika Saran, Robert Kleinberg (Cornell University); Vishal Shrivastav (Purdue University); Hakim Weatherspoon (Cornell University) |
Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs
Pravesh Kothari (CMU); Aaron Potechin (University of Chicago); Jeff Xu (CMU) |
Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen (University of California at Berkeley); Shuichi Hirahara (National Institute of Informatics); Hanlin Ren (University of Oxford) Joint talk with Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
Zeyong Li (National University of Singapore) |
16:33 | Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa) |
Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability
Mohsen Ghaffari, Brandon Wang (MIT) |
Semidefinite programming and linear equations vs. homomorphism problems
Lorenzo Ciardo, Stanislav Živný (University of Oxford) |
Random (log n)-CNF are Hard for Cutting Planes (Again)
Dmitry Sokolov (EPFL) |
16:51 | Optimal Online Discrepancy Minimization
Janardhan Kulkarni (Microsoft Research); Victor Reis (Institute for Advanced Study); Thomas Rothvoss (University of Washington) |
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich) |
How Random CSPs Fool Hierarchies
Siu On Chan, Hiu Tsun Ng (The Chinese University of Hong Kong); Sijin Peng (Tsinghua University) |
Hardness Condensation by Restriction
Mika Göös (EPFL); Ilan Newman (University of Haifa); Artur Riazanov, Dmitry Sokolov (EPFL) |
17:09 | Supermodular Approximation of Norms and Applications
Thomas Kesselheim (University of Bonn); Marco Molinaro (PUC-Rio); Sahil Singla (Georgia Tech) |
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy (School of Computation, Information and Technology, Technical University of Munich, Munich Center for Quantum Science and Technology); Francesco d'Amore (Aalto University and Bocconi University and BIDSA); Rishikesh Gajjala (Indian Institute of Science and Aalto University); Fabian Kuhn (University of Freiburg); François Le Gall (Nagoya University); Henrik Lievonen, Augusto Modanese (Aalto University); Marc-Olivier Renou (Inria, Universitée Paris-Saclay, CPHT, Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau); Gustav Schmid (University of Freiburg); Jukka Suomela (Aalto University) |
Swap cosystolic expansion
Yotam Dikstein (Institute for Advanced Study); Irit Dinur (Weizmann Institute of Science) Joint talk with Agreement theorems for high dimensional expanders in the low acceptance regime: the role of covers
Yotam Dikstein (Institute for Advanced Study); Irit Dinur (Weizmann Institute of Science) |
Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions
Ronen Shaltiel (University of Haifa); Jad Silbak (Northeastern University) |
17:27 | Ghost Value Augmentation for k-ECSS and k-ECSM
D Ellis Hershkowitz (Brown University); Nathan Klein (Institute for Advanced Study); Rico Zenklusen (ETH Zurich) |
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond
Hossein Esfandiari (Google); Praneeth Kacham (Carnegie Mellon University); Vahab Mirrokni (Google Research); David P. Woodruff (Carnegie Mellon University); Peilin Zhong (Google Research) |
Characterizing Direct Product Testing via Coboundary Expansion
Mitali Bafna, Dor Minzer (MIT) |
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L that Uses Properties of BPL
Dean Doron (Ben Gurion University); Edward Pyne (MIT); Roei Tell (University of Toronto) |
|
| The times listed in this table are in Pacific Daylight Time. | ||||||||||||