Chasing Convex Bodies with Linear Competitive Ratio (Invited Paper)
C. J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang
(Carnegie Mellon University, USA; Google Research, USA)

Publisher's Version

Neural Tangent Kernel: Convergence and Generalization in Neural Networks (Invited Paper)
Arthur Jacot, Franck Gabriel, and Clément Hongler
(EPFL, Switzerland)

Publisher's Version

Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability (Invited Paper)
Jon Kleinberg and Sendhil Mullainathan
(Cornell University, USA; University of Chicago, USA)

Publisher's Version

The Ghost in the Radiation: Robust Encodings of the Black Hole Interior (Invited Paper)
Isaac H. Kim, Eugene Tang, and John Preskill
(University of Sydney, Australia; California Institute of Technology, USA)

Publisher's Version

A New Analysis of Differential Privacy’s Generalization Guarantees (Invited Paper)
Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld
(University of Pennsylvania, USA; Hebrew University of Jerusalem, Israel)

Publisher's Version

Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times (Invited Paper)
Isaac Grosof, Ziv Scully, and Mor Harchol-Balter
(Carnegie Mellon University, USA)

Publisher's Version

Learnability Can Be Independent of Set Theory (Invited Paper)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff
(University of Waterloo, Canada; Czech Academy of Sciences, Czechia; Technion, Israel; Tel Aviv University, Israel)

Publisher's Version

Tutorials

Log-Concave Polynomials in Theory and Applications (Tutorial)
Nima Anari and Cynthia Vinzant
(Stanford University, USA; North Carolina State University, USA; University of Washington, USA)

Publisher's Version

Statistical Physics of Random CSPs (Tutorial)
Nike Sun
(Massachusetts Institute of Technology, USA)

Publisher's Version

Papers

Best Student Papers

Discrepancy Minimization via a Self-Balancing Walk
Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney
(Princeton University, USA; Stanford University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Video

Separating Words and Trace Reconstruction
Zachary Chase
(University of Oxford, UK)

Publisher's Version

Best Papers

A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)

Publisher's Version

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani
(University of Liverpool, UK; University of Oxford, UK)

Publisher's Version

Indistinguishability Obfuscation from Well-Founded Assumptions
Aayush Jain, Huijia Lin, and Amit Sahai
(University of California at Los Angeles, USA; University of Washington, USA)

Publisher's Version

Session 1A

Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
Yufei Ruan, Jiaqi Yang, and Yuan Zhou
(University of Illinois at Urbana-Champaign, USA; Tsinghua University, China)

Publisher's Version

Efficiently Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)

Publisher's Version

Robust Linear Regression: Optimal Rates in Polynomial Time
Ainesh Bakshi and Adarsh Prasad
(Carnegie Mellon University, USA)

Publisher's Version

Statistical Query Complexity of Manifold Estimation
Eddie Aamari and Alexander Knop
(LPSM, France; Sorbonne University, France; University of Paris, France; CNRS, France; University of California at San Diego, USA)

Publisher's Version

When Is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar
(Boston University, USA; Apple, USA)

Publisher's Version

Session 2A

Sample-Optimal and Efficient Learning of Tree Ising Models
Constantinos Daskalakis and Qinxuan Pan
(Massachusetts Institute of Technology, USA)

Publisher's Version

Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and N. V. Vinodchandran
(National University of Singapore, Singapore; University of Texas at Austin, USA; University of Nebraska-Lincoln, USA)

Publisher's Version

Info

Learning Ising Models from One or Multiple Samples
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros
(Massachusetts Institute of Technology, USA; Google, USA)

Publisher's Version

A New Coreset Framework for Clustering
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn
(Google, Switzerland; Sorbonne University, France; CNRS, France; LIP6, France; Aarhus University, Denmark)

Publisher's Version

Info

Sample-Efficient Proper PAC Learning with Approximate Differential Privacy
Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi
(Google Research, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 1B

Log-Rank and Lifting for AND-Functions
Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan
(University of California at San Diego, USA; Tsinghua University, China)

Publisher's Version

Automating Algebraic Proof Systems Is NP-Hard
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, and Dmitry Sokolov
(Czech Academy of Sciences, Czechia; EPFL, Switzerland; University of Copenhagen, Denmark; Lund University, Sweden; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA; McGill University, Canada; St. Petersburg State University, Russia; Russian Academy of Sciences, Russia)

Publisher's Version

Strong Co-nondeterministic Lower Bounds for NP Cannot Be Proved Feasibly
Ján Pich and Rahul Santhanam
(Czech Academy of Sciences, Czechia; University of Oxford, UK)

Publisher's Version

Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
Rahul Santhanam and Iddo Tzameret
(University of Oxford, UK; Imperial College London, UK)

Publisher's Version

New Separations Results for External Information
Mark Braverman and Dor Minzer
(Princeton University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 2B

Polynomial Time Deterministic Identity Testing Algorithm for Σ^[3]ΠΣΠ^[2] Circuits via Edelstein–Kelly Type Theorem for Quadratic Polynomials
Shir Peleg and Amir Shpilka
(Tel Aviv University, Israel)

Publisher's Version

Info

An Improved Derandomization of the Switching Lemma
Zander Kelley
(University of Illinois at Urbana-Champaign, USA)

Publisher's Version

Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost
Lijie Chen and Roei Tell
(Massachusetts Institute of Technology, USA)

Publisher's Version

Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions
Shuichi Hirahara
(National Institute of Informatics, Japan)

Publisher's Version

Pseudodeterministic Algorithms and the Structure of Probabilistic Time
Zhenjian Lu, Igor C. Oliveira, and Rahul Santhanam
(University of Warwick, UK; University of Oxford, UK)

Publisher's Version

Session 1C

Vertex Connectivity in Poly-logarithmic Max-Flows
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(Carnegie Mellon University, USA; University of Copenhagen, Denmark; KTH, Sweden; Duke University, USA; University of Michigan, USA; Aalto University, Finland)

Publisher's Version

Finding Large Induced Sparse Subgraphs in C_>t -Free Graphs in Quasipolynomial Time
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski
(University of California at Santa Barbara, USA; University of Warsaw, Poland; Warsaw University of Technology, Poland)

Publisher's Version

Clan Embeddings into Trees, and Low Treewidth Graphs
Arnold Filtser and Hung Le
(Columbia University, USA; University of Massachusetts, USA)

Publisher's Version

Tree Embeddings for Hop-Constrained Network Design
Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic
(Carnegie Mellon University, USA; ETH Zurich, Switzerland)

Publisher's Version

Bridging the Gap between Tree and Connectivity Augmentation: Unified and Stronger Approaches
Federica Cecchetto, Vera Traub, and Rico Zenklusen
(ETH Zurich, Switzerland)

Publisher's Version

Session 2C

Deterministic Mincut in Almost-Linear Time
Jason Li
(Carnegie Mellon University, USA)

Publisher's Version

Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs
Theo McKenzie, Peter Michael Reichstein Rasmussen, and Nikhil Srivastava
(University of California at Berkeley, USA; University of Copenhagen, Denmark)

Publisher's Version

Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong
(Stanford University, USA; University of Washington, USA; North Carolina State University, USA)

Publisher's Version

Info

Breaking the Quadratic Barrier for Matroid Intersection
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai
(KTH, Sweden; University of Copenhagen, Denmark)

Publisher's Version

Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More
Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong
(Stanford University, USA)

Publisher's Version

Info

Session 3A

Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev
(Princeton University, USA; Tel Aviv University, Israel; Harvard University, USA; Massachusetts Institute of Technology, USA; Technion, Israel; Google Research, Israel; Weizmann Institute of Science, Israel; Boston University, USA)

Publisher's Version

Stronger Calibration Lower Bounds via Sidestepping
Mingda Qiao and Gregory Valiant
(Stanford University, USA)

Publisher's Version

Hardness of Learning DNFs using Halfspaces
Suprovat Ghoshal and Rishi Saket
(University of Michigan, USA; IBM Research, India)

Publisher's Version

Boosting Simple Learners
Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; OrCam, Israel; Google AI, USA; Technion, Israel; Google Research, Israel)

Publisher's Version

Algorithmic Foundations for the Diffraction Limit
Sitan Chen and Ankur Moitra
(Massachusetts Institute of Technology, USA)

Publisher's Version

Session 4A

VC Dimension and Distribution-Free Sample-Based Testing
Eric Blais, Renato Ferreira Pinto Jr., and Nathaniel Harms
(University of Waterloo, Canada; Google, Canada)

Publisher's Version

Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu and Ankur Moitra
(Massachusetts Institute of Technology, USA)

Publisher's Version

A Theory of Universal Learning
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff
(Google, Switzerland; Toyota Technological Institute at Chicago, USA; Technion, Israel; Google Research, Israel; Princeton University, USA)

Publisher's Version

Optimal Testing of Discrete Distributions with High Probability
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, and Eric Price
(University of Wisconsin-Madison, USA; MPI-INF, Germany; University of California at San Diego, USA; Princeton University, USA; University of Texas at Austin, USA)

Publisher's Version

Session 3B

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
Seth Pettie and Dingyu Wang
(University of Michigan, USA)

Publisher's Version

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu
(Massachusetts Institute of Technology, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version

Robust Testing of Low Dimensional Functions
Anindya De, Elchanan Mossel, and Joe Neeman
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; University of Texas at Austin, USA)

Publisher's Version

Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida
(EPFL, Switzerland; Weizmann Institute of Science, Israel; National Institute of Informatics, Japan)

Publisher's Version

Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
Sepehr Assadi and Vishvajeet N
(Rutgers University, USA)

Publisher's Version

Session 4B

Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time
Julia Chuzhoy
(Toyota Technological Institute at Chicago, USA)

Publisher's Version

Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka and Saeed Seddighin
(University of California at Berkeley, USA; Toyota Technological Institute at Chicago, USA)

Publisher's Version

Fully Dynamic Approximation of LIS in Polylogarithmic Time
Paweł Gawrychowski and Wojciech Janczewski
(University of Wrocław, Poland)

Publisher's Version

A Framework for Dynamic Matching in Weighted Graphs
Aaron Bernstein, Aditi Dudeja, and Zachary Langley
(Rutgers University, USA)

Publisher's Version

Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
Zhiyi Huang and Xinkai Shu
(University of Hong Kong, China)

Publisher's Version

Session 3C

Continuous LWE
Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang
(New York University, USA; University of Michigan, USA)

Publisher's Version

SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE
Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang
(University of Illinois at Urbana-Champaign, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
Yanyi Liu and Rafael Pass
(Cornell University, USA)

Publisher's Version

Indistinguishability Obfuscation from Circular Security
Romain Gay and Rafael Pass
(IBM Research, Switzerland; Cornell Tech, USA)

Publisher's Version

Fiat–Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW Is Not Zero-Knowledge)
Justin Holmgren, Alex Lombardi, and Ron D. Rothblum
(NTT Research, USA; Massachusetts Institute of Technology, USA; Technion, Israel)

Publisher's Version

Session 4C

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma
Lijie Chen and Xin Lyu
(Massachusetts Institute of Technology, USA; Tsinghua University, China)

Publisher's Version

Info

Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
Josh Alman
(Harvard University, USA)

Publisher's Version

Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity
Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay
(Tata Institute of Fundamental Research, India; Chennai Mathematical Institute, India)

Publisher's Version

Structure vs. Randomness for Bilinear Maps
Alex Cohen and Guy Moshkovitz
(Yale University, USA; City University of New York, USA)

Publisher's Version

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich
(Rutgers University, USA; Boston College, USA)

Publisher's Version

Session 5A

A Faster Algorithm for Solving General LPs
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang
(Columbia University, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version

Info

Combinatorial Bernoulli Factories: Matchings, Flows, and Other Polytopes
Rad Niazadeh, Renato Paes Leme, and Jon Schneider
(University of Chicago, USA; Google Research, USA)

Publisher's Version

Capacity Lower Bounds via Productization
Leonid Gurvits and Jonathan Leake
(City College of New York, USA; TU Berlin, Germany)

Publisher's Version

Minimum Cost Flows, MDPs, and ℓ₁-Regression in Nearly Linear Time for Dense Instances
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; University of Michigan, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA; Google Research, USA)

Publisher's Version

A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations
Vijay Bhattiprolu, Euiwoong Lee, and Assaf Naor
(Institute for Advanced Study at Princeton, USA; Princeton University, USA; University of Michigan, USA)

Publisher's Version

Session 5B

The Randomized Communication Complexity of Randomized Auctions
Aviad Rubinstein and Junyao Zhao
(Stanford University, USA)

Publisher's Version

Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization
Oren Mangoubi and Nisheeth K. Vishnoi
(Worcester Polytechnic Institute, USA; Yale University, USA)

Publisher's Version

Contextual Search in the Presence of Irrational Agents
Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert Schapire
(Microsoft Research, USA; Harvard University, USA)

Publisher's Version

How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik
(Carnegie Mellon University, USA; University of Texas at El Paso, USA; University of Pennsylvania, USA)

Publisher's Version

The Communication Complexity of Payment Computation
Shahar Dobzinski and Shiri Ron
(Weizmann Institute of Science, Israel)

Publisher's Version

Exponential Communication Separations between Notions of Selfishness
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, and Junyao Zhao
(Stanford University, USA; Princeton University, USA)

Publisher's Version

Session 5C

Reducing Isotropy and Volume to KLS: An O*(n³ψ²) Volume Algorithm
He Jia, Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA)

Publisher's Version

A New Algorithm for Euclidean Shortest Paths in the Plane
Haitao Wang
(Utah State University, USA)

Publisher's Version

Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions
Natan Rubin
(Ben-Gurion University of the Negev, Israel)

Publisher's Version

Info

Dynamic Planar Point Location in Optimal Time
Yakov Nekrich
(Michigan Technological University, USA)

Publisher's Version

Session 6A

When Is Approximate Counting for Conjunctive Queries Tractable?
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros
(PUC, Chile; IMFD, Chile; Carnegie Mellon University, USA)

Publisher's Version

Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces
Yair Bartal and Lee-Ad Gottlieb
(Hebrew University of Jerusalem, Israel; Ariel University, Israel)

Publisher's Version

A (2 + ε)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine
Lars Rohwedder and Andreas Wiese
(EPFL, Switzerland; University of Chile, Chile)

Publisher's Version

A Quasipolynomial (2 + ε)-Approximation for Planar Sparsest Cut
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, and Jason Li
(Google, Switzerland; Carnegie Mellon University, USA; Brown University, USA)

Publisher's Version

Flow Time Scheduling with Uncertain Processing Time
Yossi Azar, Stefano Leonardi, and Noam Touitou
(Tel Aviv University, Israel; Sapienza University of Rome, Italy)

Publisher's Version

Session 7A

The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation
Albert Cheu and Jonathan Ullman
(Northeastern University, USA)

Publisher's Version

Outcome Indistinguishability
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona
(Harvard University, USA; University of California at Berkeley, USA; Stanford University, USA; Weizmann Institute of Science, Israel)

Publisher's Version

Optimal Labelling Schemes for Adjacency, Comparability, and Reachability
Marthe Bonamy, Louis Esperet, Carla Groenland, and Alex Scott
(CNRS, France; Labri, France; University of Bordeaux, France; G-SCOP, France; Grenoble Alps University, France; University of Oxford, UK)

Publisher's Version

Bipartite Perfect Matching as a Real Polynomial
Gal Beniamini and Noam Nisan
(Hebrew University of Jerusalem, Israel)

Publisher's Version

Efficient and Near-Optimal Algorithms for Sampling Connected Subgraphs
Marco Bressan
(University of Milan, Italy)

Publisher's Version

Session 6B

Distributed Weighted Min-Cut in Nearly-Optimal Time
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai
(ETH Zurich, Switzerland; University of Toronto, Canada; KTH, Sweden; University of Copenhagen, Denmark)

Publisher's Version

A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
Krzysztof Nowicki
(University of Copenhagen, Denmark; University of Wrocław, Poland)

Publisher's Version

Universally-Optimal Distributed Algorithms for Known Topologies
Bernhard Haeupler, David Wajc, and Goran Zuzic
(Carnegie Mellon University, USA; ETH Zurich, Switzerland; Stanford University, USA)

Publisher's Version

Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan
(Reykjavik University, Iceland; University of Freiburg, Germany; Technion, Israel)

Publisher's Version

The Communication Complexity of Multiparty Set Disjointness under Product Distributions
Nachum Dershowitz, Rotem Oshman, and Tal Roth
(Tel Aviv University, Israel)

Publisher's Version

Session 7B

Hop-Constrained Oblivious Routing
Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)

Publisher's Version

Efficient Randomized DCAS
George Giakkoupis, Mehrdad Jafari Giv, and Philipp Woelfel
(Inria, France; University of Rennes, France; CNRS, France; IRISA, France; University of Calgary, Canada)

Publisher's Version

Optimal Error Resilience of Adaptive Message Exchange
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)

Publisher's Version

How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games
William Kuszmaul
(Massachusetts Institute of Technology, USA)

Publisher's Version

Load Balancing with Dynamic Set of Balls and Bins
Anders Aamand, Jakob Bæk Tejs Knudsen, and Mikkel Thorup
(University of Copenhagen, Denmark)

Publisher's Version

Session 6C

Fiber Bundle Codes: Breaking the N^1/2 polylog(N) Barrier for Quantum LDPC Codes
Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell
(Station Q, USA; Microsoft Quantum, USA; Carnegie Mellon University, USA)

Publisher's Version

An Optimal Separation of Randomized and Quantum Query Complexity
Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu
(University of California at Los Angeles, USA)

Publisher's Version

k-Forrelation Optimally Separates Quantum and Classical Query Complexity
Nikhil Bansal and Makrand Sinha
(CWI, Netherlands; Eindhoven University of Technology, Netherlands)

Publisher's Version

New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(√n log^k n) Distance
Tali Kaufman and Ran J. Tessler
(Bar-Ilan University, Israel; Weizmann Institute of Science, Israel)

Publisher's Version

Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal
(University of Texas at Austin, USA; University of Waterloo, Canada; Microsoft Quantum, USA; Microsoft Research, USA; Northwestern University, USA; University of California at Berkeley, USA)

Publisher's Version

Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
Bill Fefferman and Zachary Remscrim
(University of Chicago, USA)

Publisher's Version

Session 7C

(Sub)Exponential Advantage of Adiabatic Quantum Computation with No Sign Problem
András Gilyén, Matthew B. Hastings, and Umesh Vazirani
(California Institute of Technology, USA; Microsoft Quantum, USA; Microsoft Research, USA; University of California at Berkeley, USA)

Publisher's Version

Succinct Blind Quantum Computation using a Random Oracle
Jiayu Zhang
(Boston University, USA)

Publisher's Version

Sampling Matrices from Harish-Chandra–Itzykson–Zuber Densities with Applications to Quantum Inference and Differential Privacy
Jonathan Leake, Colin McSwiggen, and Nisheeth K. Vishnoi
(TU Berlin, Germany; University of Tokyo, Japan; Yale University, USA)

Publisher's Version

Improved Quantum Data Analysis
Costin Bădescu and Ryan O'Donnell
(Carnegie Mellon University, USA)

Publisher's Version

Session 8A

Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, and László A. Végh
(University of Illinois at Urbana-Champaign, USA; London School of Economics and Political Science, UK)

Publisher's Version

Settling the Complexity of Nash Equilibrium in Congestion Games
Yakov Babichenko and Aviad Rubinstein
(Technion, Israel; Stanford University, USA)

Publisher's Version

Revelation Gap for Pricing from Samples
Yiding Feng, Jason D. Hartline, and Yingkai Li
(Northwestern University, USA)

Publisher's Version

Efficient Two-Sided Markets with Limited Information
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser
(Google Research, Switzerland; Sapienza University of Rome, Italy)

Publisher's Version

The Complexity of Constrained Min-Max Optimization
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis
(Massachusetts Institute of Technology, USA; Singapore University of Technology and Design, Singapore; University of California at Berkeley, USA)

Publisher's Version

Session 9A

On Codes Decoding a Constant Fraction of Errors on the BSC
Jan Hązła, Alex Samorodnitsky, and Ori Sberlo
(EPFL, Switzerland; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)

Publisher's Version

Decoding Multivariate Multiplicity Codes on Product Sets
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan
(Tata Institute of Fundamental Research, India; IIT Bombay, India; Harvard University, USA)

Publisher's Version

Efficient List-Decoding with Constant Alphabet and List Sizes
Zeyu Guo and Noga Ron-Zewi
(University of Haifa, Israel)

Publisher's Version

Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity
Ronen Shaltiel and Jad Silbak
(University of Haifa, Israel; Tel Aviv University, Israel)

Publisher's Version

Near-Linear Time Decoding of Ta-Shma’s Codes via Splittable Regularity
Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani
(University of Chicago, USA; Toyota Technological Institute at Chicago, USA)

Publisher's Version

Session 8B

Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
Zongchen Chen, Kuikui Liu, and Eric Vigoda
(Georgia Institute of Technology, USA; University of Washington, USA)

Publisher's Version

Entropy Decay in the Swendsen–Wang Dynamics on ℤ^d
Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, and Eric Vigoda
(Pennsylvania State University, USA; Roma Tre University, Italy; University of California at Berkeley, USA; Georgia Institute of Technology, USA)

Publisher's Version

Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
Weiming Feng, Kun He, and Yitong Yin
(Nanjing University, China; Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China)

Publisher's Version

Frozen 1-RSB Structure of the Symmetric Ising Perceptron
Will Perkins and Changji Xu
(University of Illinois at Chicago, USA; Harvard University, USA)

Publisher's Version

Perfectly Sampling k ≥ (8/3 + o(1))Δ-Colorings in Graphs
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney
(Simons Institute for the Theory of Computing Berkeley, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Session 9B

The Metric Relaxation for 0-Extension Admits an Ω(log^2/3k) Gap
Roy Schwartz and Nitzan Tur
(Technion, Israel)

Publisher's Version

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups
Amey Bhangale and Subhash Khot
(University of California at Riverside, USA; New York University, USA)

Publisher's Version

Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, and David Steurer
(Harvard University, USA; Carnegie Mellon University, USA; Stanford University, USA; ETH Zurich, Switzerland)

Publisher's Version

Expander Random Walks: A Fourier-Analytic Approach
Gil Cohen, Noam Peri, and Amnon Ta-Shma
(Tel Aviv University, Israel)

Publisher's Version

Info

Local Concentration Inequalities and Tomaszewski’s Conjecture
Nathan Keller and Ohad Klein
(Bar-Ilan University, Israel)

Publisher's Version

Session 8C

Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors
Jesper Nederlof and Karol Węgrzycki
(Utrecht University, Netherlands; Saarland University, Germany; MPI-INF, Germany)

Publisher's Version

Video

Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)
Ray Li
(Stanford University, USA)

Publisher's Version

Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard and Nicole Wein
(Massachusetts Institute of Technology, USA)

Publisher's Version

Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Karl Bringmann, Nick Fischer, and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany)

Publisher's Version

Subcubic Algorithms for Gomory–Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
(Weizmann Institute of Science, Israel)

Publisher's Version

Approximate Gomory–Hu Tree Is Faster Than n – 1 Max-Flows
Jason Li and Debmalya Panigrahi
(Carnegie Mellon University, USA; Duke University, USA)

Publisher's Version

Session 9C

Constant Approximating k-Clique Is W[1]-Hard
Bingkai Lin
(Nanjing University, China)

Publisher's Version

Vertex Deletion Parameterized by Elimination Distance and Even Less
Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk
(Eindhoven University of Technology, Netherlands)

Publisher's Version

A Full Complexity Dichotomy for Immanant Families
Radu Curticapean
(IT University of Copenhagen, Denmark)

Publisher's Version

A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
Sally Dong, Yin Tat Lee, and Guanghao Ye
(University of Washington, USA; Microsoft Research, USA)

Publisher's Version

proc time: 29.18