Accepted Papers

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

Tsz Chiu Kwok (ITCS, Shanghai University of Finance and Economics), Zhewei Wei (Renmin University of China), Mingji Yang (Renmin University of China)

Multi-Quadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP

Benjamin Rossman (Duke University), Davidson Zhu (Duke University)

Range Longest Increasing Subsequence and its Relatives

Karthik C. S. (Rutgers University), Rahul Saladi (Department of Computer Science and Automation, Indian Institute of Science, India)

AC0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard

Jiaqi Lu (Imperial College London), Rahul Santhanam (University of Oxford), Iddo Tzameret (Imperial College London)

Lower Bounds on Tree Covers

Yu Chen (National University of Singapore), Zihan Tan (University of Minnesota), Hangyu Xu (University of Science and Technology of China)

Dudeney's Dissection is Optimal

Erik Demaine (MIT), Tonan Kamata (Japan Advanced Institute of Science and Technology), Ryuhei Uehara (JAIST)

Uniformity Testing under User-Level Local Privacy

Clément Canonne (The University of Sydney), Abigail Gentle (The University of Sydney), Vikrant Singhal (Harvard University)

Interactive Proofs For Distribution Testing With Conditional Oracles

Ari Biswas (University Of Warwick), Mark Bun (Boston University), Clément Canonne (The University of Sydney), Satchit Sivakumar (Boston University)

Lower Bounds for Noncommutative Circuits with Low Syntactic Degree

Pratik Shastri (Institute of Mathematical Sciences, Chennai)

Symmetric Algebraic Circuits and Homomorphism Polynomials

Anuj Dawar (University of Cambridge), Benedikt Pago (University of Cambridge), Tim Seppelt (IT-University of Copenhagen)

Identity check problem for shallow quantum circuits

Sergey Bravyi (IBM Quantum), nan Minh (IBM Quantum), Natalie Parham (Columbia University)

Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions

Will Ma (Columbia University), Calum MacRury (Columbia University), Jingwei Zhang (The Chinese University of Hong Kong (Shenzhen))

Identity Testing for Circuits with Exponentiation Gates

Jiatu Li (Massachusetts Institute of Technology), Mengdi Wu (Carnegie Mellon University)

Semi-Random Graphs, Robust Asymmetry, and Reconstruction

Julian Asilis (University of Southern California), Xi Chen (Columbia University), Dutch Hansen (University of Southern California), Shanghua Teng (University of Southern California)

Cloning Games, Black Holes and Cryptography

Alexander Poremba (Boston University), Seyoon Ragavan (MIT), Vinod Vaikuntanathan (MIT)

Forrelation Is Extremally Hard

Uma Girish (Columbia University), Rocco A. Servedio (Columbia University)

Lower Bounds Beyond DNF of Parities

Artur Riazanov (EPFL), Anastasia Sofronova (EPFL), Dmitry Sokolov (EPFL)

New Greedy Spanners and Applications

Elizaveta Popova (Weizmann Institute of Science), Elad Tzailk (Weizmann Institute)

Supercritical Tradeoff Between Size and Depth for Resolution over Parities

Dmitry Itsykson (Ben-Gurion University of the Negev), Alexander Knop (Google Research)

The Mixed Birth-death/death-Birth Moran Process

David A. Brewster (Harvard University), Yichen Huang (Harvard University), Michael Mitzenmacher (Harvard University), Martin A. Nowak (Harvard University)

On approximating the $f$-divergence between two Ising models

Weiming Feng (The University of Hong Kong), Yucheng Fu (The University of Hong Kong)

Linear time encodable binary code achieving GV bound with linear time encodable dual achieving GV bound

Martijn Brehm (University of Amsterdam), Nicolas Resch (University of Amsterdam)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Robert Andrews (University of Waterloo), Jules Armand (Université Savoie Mont Blanc, CNRS, LAMA), Prateek Dwivedi (IT University of Copenhagen, Denmark), Magnus Rahbek Dalgaard Hansen (IT University of Copenhagen, Denmark), Nutan Limaye (IT University of Copenhagen, Denmark), Srikanth Srinivasan (University of Copenhagen, Denmark), Sébastien Tavenas (Université Savoie Mont Blanc, CNRS, LAMA)

A Parameterized-Complexity Framework for Finding Local Optima

Robert Ganian (TU Wien), Hung Hoang (TU Wien), Christian Komusiewicz (University of Jena), Nils Morawietz (Friedrich-Schiller-Universität Jena)

Fixed-Parameter Tractable Submodular Maximization over a Matroid

Shamisa Nematollahi (CNRS, IRIF, Université Paris Cité), Adrian Vladu (CNRS, IRIF, Université Paris Cité), Junyao Zhao (CNRS, IRIF, Université Paris Cité)

Two bases suffice for QMA1 completneess

Henry Ma (MIT), Anand Natarajan (MIT)

Limitations to computing quadratic functions on Reed-Solomon encoded data

Keller Blackwell (Stanford University), Mary Wootters (Stanford)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

Bill Fefferman (U. of Chicago), Soumik Ghosh (University of Chicago), Wei Zhan (Purdue University)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

Shaddin Dughmi (University of Southern California), Yusuf Hakan Kalayci (University of Southern California), Xinyu Liu (University of Southern California)

Auditability and the Landscape of Distance to Multicalibration

Nathan Derhake (University of Southern California), Siddartha Devic (University of Southern California), Dutch Hansen (University of Southern California), Kuan Liu (University of Southern California), Vatsal Sharan (University of Southern California)

Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region

Shuai Shao (University of Sciences and Technology), Ke Shi (University of Sciences and Technology)

Bayesian Perspective on Memorization and Reconstruction

Haim Kaplan (Tel Aviv University), Yishay Mansour (Tel Aviv University), Uri Stemmer (Tel Aviv University), kobbi nissim (Georgetown)

The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class between QMA and QMA(2)

Jonas Kamminga (Paderborn University), Dorian Rudolph (Paderborn University)

Analyzing the Economic Impact of Decentralization on Users

Amit Levy (Better Bytes & Princeton), S. Matthew Weinberg (Princeton University), Chenghan Zhou (Stanford University)

Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Jin-Yi Cai (University of Wisconsin-Madison), Ben Young (University of Wisconsin-Madison)

Computing Equilibrium Points of Electrostatic Potentials

Abheek Ghosh (University of Oxford), Paul W. Goldberg (University of Oxford), Alexandros Hollender (University of Oxford)

Robust Resource Allocation via Competitive Subsidies

Siddhartha Banerjee (Cornell), Giannis Fikioris (Cornell University), David X. Lin (Cornell University), Eva Tardos (Cornell University)

Fourier Sparsity of Delta Functions and Matching Vector PIRs

Fatemeh Ghasemi (University of Toronto), Swastik Kopparty (University of Toronto)

Unconditional Pseudorandomness against Shallow Quantum Circuits

Soumik Ghosh (University of Chicago), Sathyawageeswar Subramanian (University of Cambridge), Wei Zhan (Purdue University)

Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election

Yi-Jun Chang (National University of Singapore), Lyuting Chen (National University of Singapore), Haoran Zhou (National University of Singapore)

Unitary Complexity and the Uhlmann Transformation Problem

John Bostanci (Columbia University), Yuval Efron (Columbia University), Tony Metger (ETH Zurich), Alexander Poremba (Boston University), Luowen Qian (Northeastern University), Henry Yuen (Columbia University)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

Marco Aldi (Virginia Commonwealth University), Sevag Gharibian (Paderborn University), Dorian Rudolph (Paderborn University)

Smoothed Analysis of Dynamic Graph Algorithms

Uri Meir (Tel-Aviv University), Ami Paz (LISN - CNRS & Paris Saclay University)

A Simple and Robust Protocol for Distributed Counting

Edith Cohen (Google Research and Tel Aviv University), Moshe Shechner (Tel Aviv University), Uri Stemmer (Tel Aviv University)

Lower Bounds and Separations for Torus Polynomials

Vaibhav Krishan (The Institute of Mathematical Sciences), Sundar Vishwanathan (Indian Institute of Technology)

One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Michal Feldman (Tel Aviv University), Yoav Gal-Tzur (Tel Aviv University), Tomasz Ponitka (Tel Aviv University), Maya Schlesinger (Tel Aviv University)

Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations

Bernhard Haeupler (INSAIT, Sofia University "St. Kliment Ohridski" & ETH Zurich), Marc Kaufmann (ETH Zürich), Raghu Raman Ravi (ETH Zürich), Ulysse Schaller (ETH Zürich)

Commuting Local Hamiltonians Beyond 2D

John Bostanci (Columbia University), Yeongwoo Hwang (Harvard University)

Time and Space Efficient Deterministic List Decoding

Joshua Cook (Amazon), Dana Moshkovitz (University of Texas at Austin)

Linear Matroid Intersection is in Catalytic Logspace

Aryan Agarwala (Max-Planck-Institut für Informatics), Yaroslav Alekseev (Technion), Antoine Vinciguerra (Technion Israel Institute of Technology)

Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds

Yaroslav Alekseev (Technion), Nikita Gaevoy (Technion)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy

Avantika Agarwal (University of Waterloo), Shalev Ben-David (University of Waterloo)

A Combinatorial Characterization of Constant Mixing Time

Lap Chi Lau (University of Waterloo), Raymond Liu (University of Waterloo)

Decentralized Data Archival: New Definitions and Constructions

Changrui Mu (Carnegie Mellon University), Elaine Shi (Carnegie Mellon University), Rose Silver (Carnegie Mellon University)

New Bounds for Circular Trace Reconstruction

Arnav Burudgunte (Purdue University), Paul Valiant (Purdue University), Hongao Wang (Purdue University)

Fully Quantum Computational Entropies

Rotem Arnon (Weizmann Institute of Science), Noam Avidan (Weizmann Institute of Science), Thomas Hahn (Weizmann Institute of Science), Joseph M. Renes (Institute for Theoretical Physics, ETH Zurich)

Dimension-Free Correlated Sampling for the Hypersimplex

Seffi Naor (Technion — Israel Institute of Technology), Nitya Raju (University of Maryland), Abhishek Shetty (Massachusetts Institute of Technology), Aravind Srinivasan (University of Maryland), Renata Valieva (University of Maryland), David Wajc (Technion — Israel Institute of Technology)

Debordering Closure Results in Determinantal and Pfaffian Ideals

Anakin Dey (The Ohio State University), Zeyu Guo (The Ohio State University)

Testing classical properties from quantum data

Matthias Caro (University of Warwick), Preksha Naik (California Institute of Technology), Joseph Slote (University of Washington)

Delaunay Triangulations with Predictions

Sergio Cabello (University of Ljubljana, Slovenia), Timothy M. Chan (University of Illinois at Urbana-Champaign), Panos Giannopoulos (City University of London)

FPT Approximations for Connected Maximum Coverage

Tanmay Inamdar (IIT Jodhpur), Satyabrata Jana (University of Warwick), Madhumita Kundu (University of Bergen), Daniel Lokshtanov (University of California Santa Barbara, USA), Saket Saurabh (Institute of Mathematical Sciences), Meirav Zehavi (Ben Gurion University)

On the PTAS Complexity of Multidimensional Knapsack

Ilan Doron-Arad (Technion), Ariel Kulik (Ben-Gurion University), Pasin Manurangsi (Google Research)

Discrepancy Beyond Additive Functions with Applications to Fair Division

Alexandros Hollender (University of Oxford), Pasin Manurangsi (Google Research), Raghu Meka (UCLA), Warut Suksompong (National University of Singapore)

Random Unitaries in Constant (Quantum) Time

Ben Foxman (Yale University), Natalie Parham (Columbia University), Francisca Vasconcelos (University of California, Berkeley), Henry Yuen (Columbia University)

Symmetric quantum computation

Davi Castro-Silva (University of Cambridge), Tom Gur (University of Cambridge), Sergii Strelchuk (University of Oxford)

Robust Streaming Against Low-Memory Adversaries

Omri Ben-Eliezer (Technion), Krzysztof Onak (Boston University), Sandeep Silwal (University of Wisconsin-Madison)

Samplability makes learning easier

Guy Blanc (Stanford University), Caleb Koch (Stanford University), Jane Lange (MIT), Carmen Strassle (Stanford University), Li-Yang Tan (Stanford University)

Local transformations of bipartite entanglement are rigid

John Bostanci (Columbia University), Tony Metger (ETH Zürich), Henry Yuen (Columbia University)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Yingxi Li (Stanford University), Ellen Vitercik (Stanford University), Mingwei Yang (Stanford University)

Testable algorithms for approximately counting edges and triangles

Talya Eden (Bar Ilan University, Israel), Ronitt Rubinfeld (MIT), Arsen Vasilyan (UT Austin)

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

Hanlin Ren (University of Oxford), Yichuan Wang (UC Berkeley), Yan Zhong (Johns Hopkins University)

Range Avoidance and Remote Point: New Algorithms and Hardness

Shengtang Huang (University of Science and Technology of China), Xin Li (Johns Hopkins University), Yan Zhong (Johns Hopkins University)

Limitations of Membership Queries in Testable Learning

Jane Lange (MIT), Mingda Qiao (University of Massachusetts Amherst)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Daniel Grier (UC San Diego), Daniel M. Kane (UC San Diego), Jackson Morris (UC San Diego), Anthony Ostuni (UC San Diego), Kewen Wu (Institute for Advanced Study)

Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length

Anna Gal (University of Texas at Austin), Gillat Kol (Princeton University), Raghuvansh Saxena (Tata Institute of Fundamental Research), Huacheng Yu (Princeton University)

Perfect Simulation of Las Vegas Algorithms via Local Computation

Xinyu Fu (Nanjing University), Yonggang Jiang (Max Planck Institute for Informatics and Saarland University), Yitong Yin (Nanjing University)

Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs

Klim Efremenko (Ben-Gurion University), Gillat Kol (Princeton University), Raghuvansh Saxena (Tata Institute of Fundamental Research), Zhijun Zhang (INSAIT)

A General Framework for Low Soundness Homomorphism Testing

Tushant Mittal (Stanford University), Sourya Roy (University of Iowa)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers

Shaofeng H.-C. Jiang (Peking University), Robert Krauthgamer (Weizmann Institute of Science), Shay Sapir (Weizmann Institute of Science), Sandeep Silwal (University of Wisconsin-Madison), Di Yue (Peking University)

Decoding Balanced Linear Codes With Preprocessing

Andrej Bogdanov (University of Ottawa), Rohit Chatterjee (National University of Singapore), Yunqi Li (National University of Singapore), Prashant Nalini Vasudevan (National University of Singapore)

Diffie--Hellman Key Exchange from Commutativity to Group Laws

Dung Hoang Duong (University of Wollongong), Youming Qiao (University of Technology Sydney), Chuanqi Zhang (University of Technology Sydney)

Differential privacy from axioms

Guy Blanc (Stanford University), William Pires (Columbia University), Toniann Pitassi (Columbia University)

Triangle Detection in H-free Graphs

Amir Abboud (Weizmann Institute of Science), Ron Safier (Weizmann Institute of Science), Nathan Wallheimer (Weizmann Institute of Science)

Ideal Private Simultaneous Messages Schemes and Their Applications

Reo Eriguchi (AIST), Keitaro Hiwatashi (AIST)

Average Sensitivity of Geometric Algorithms

Matthijs Ebbens (University of Cologne), Yuichi Yoshida (National Institute of Informatics)

Fairness in the k-Server Problem

Mohammadreza Daneshvaramoli (University of Massachusetts Amherst), Mohammad Hajiesmaili (University of Massachusetts Amherst), Shahin Kamali (York University), Helia Karisani (University of Massachusetts Amherst), Cameron Musco (University of Massachusetts Amherst)

On the power of Computationally Sound Interactive Proofs of Proximity

Hadar Strauss (Weizmann Institute of Science)

Efficient Algorithms for the Disjoint Shortest Paths Problem and its Extensions

Keerti Choudhary (Indian Institute of Technology Delhi, India), Amit Kumar (IIT Delhi), Lakshay Saggi (Indian Institute of Technology, Delhi)

Maximum-Flow and Minimum Cut Sensitivity Oracles for Directed Graphs

Mridul Ahi (Indian Institute of Technology, Delhi), Keerti Choudhary (Indian Institute of Technology Delhi, India), Shlok Pande (Indian Institute of Technology, Delhi), nan Pushpraj (Indian Institute of Technology, Delhi), Lakshay Saggi (Indian Institute of Technology, Delhi)

The Secretary Problem with Predictions and a Chosen Order

Hedyeh Beyhaghi (University of Massachusetts Amherst), Mohammadreza Daneshvaramoli (UMASS), Mohammad Hajiesmaili (UMass Amherst), Helia Karisani (University of Massachusetts Amherst), Cameron Musco (University of Massachusetts Amherst)

How to Use Nondeterminism in Cryptography

Marshall Ball (NYU), Peter Crawford-Kahrl (NYU)

Prior-Independent and Subgame Optimal Online Algorithms

Jason D. Hartline (Northwestern University), Anant Shah (Northwestern University), aleck johnsen (northwestern university)

Algorithmic Polynomial Freiman-Ruzsa Theorems

Srinivasan Arunachalam (IBM Quantum), Davi Castro-Silva (University of Cambridge), Arkopal Dutt (IBM Quantum), Tom Gur (University of Cambridge)

Pseudodeterministic Algorithms for Minimum Cut Algorithms

Aryan Agarwala (Max-Planck-Institut für Informatik), Nithin Varma (University of Cologne)

General Computation using Slidable Tiles with Deterministic Global Forces

Alberto Avila-Jimenez (University of Texas Rio Grande Valley), David Barreda (University of Texas Rio Grande Valley), Sarah-Laurie Evans (University of Texas Rio Grande Valley), Austin Luchsinger (University of Texas Rio Grande Valley), Aiden Massie (University of Texas Rio Grande Valley), Robert Schweller (University of Texas Rio Grande Valley), Evan Tomai (University of Texas Rio Grande Valley), Tim Wylie (University of Texas Rio Grande Valley)

Optimal Two-Round Communication Lower bound for Graph Connectivity via Pointer Chasing

Jaikumar Radhakrishnan (ICTS-TIFR), Chaitanya Reddy (IIT Hyderabad), Rakesh Venkat (IIT Hyderabad)

Unconditional Quantum Advantage for Sampling with Shallow Circuits

Adam Bene Watts (University of Waterloo), Natalie Parham (Columbia University)

Model-Generic Incrementally Verifiable Computation from Updatable BARGs

Rotem Oshman (Tel Aviv University, Israel), Eden Aldema Tshuva (Tel Aviv University)

Higher-order Delsarte Dual LPs: Lifting, Constructions and Completeness

Leonardo N. Coregliano (University of Chicago), Fernando Granha Jeronimo (UIUC), Chris Jones (Bocconi University), Nati Linial (The Hebrew University of Jerusalem), Elyassaf Loyfer (The Hebrew University of Jerusalem)

Markov Chain Robustness

David Zuckerman (University of Texas at Austin)

One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity

Yanyi Liu (Cornell Tech), Rafael Pass (Cornell Tech)

Topological dimension of extremal concept classes

Ari Blondal (McGill University), Hamed Hatami (McGill University), Pooya Hatami (Ohio State University), Chavdar Lalov (The Ohio State University), Sivan Tretiak (The Ohio State University)

Improved Rate for Non-Malleable Codes and Time-Lock Puzzles

Cody Freitag (Northeastern University and Hebrew University of Jerusalem), Ilan Komargodski (Hebrew University of Jerusalem), Manu Kondapaneni (Northeastern University), Jad Silbak (Northeastern University and MIT)

List Decoding Reed–Solomon Codes in the Lee, Euclidean, and Other Metrics

Chris Peikert (University of Michigan (Ann Arbor)), Alexandra Veliche (University of Michigan (Ann Arbor))

Efficient Catalytic Graph Algorithms

James Cook (None), Edward Pyne (MIT)

Hardness of Dynamic Tree Edit Distance and Friends

Bingbing Hu (University of California San Diego), Jakob Nogler (MIT), Barna Saha (University of California, San Diego)

The Learning Stabilizers with Noise problem

Alexander Poremba (Boston University), Yihui Quek (EPFL), Peter Shor (MIT)

The Hardness of Learning Quantum Circuits and its Cryptographic Applications

Bill Fefferman (U. of Chicago), Soumik Ghosh (University of Chicago), Makrand Sinha (UIUC), Henry Yuen (Columbia University)

Recovering Communities in Structured Random Graphs

Michael Kapralov (EPFL, Switzerland), Luca Trevisan (Bocconi University), Weronika Wrzos-Kaminska (EPFL)

The curious case of "XOR repetition" of monogamy-of-entanglement games

Andrea Coladangelo (University of Washington), Qipeng Liu (UC San Diego), Ziyi Xie (Tsinghua University)

Slice rank and partition rank of the determinant

Amichai Lampert (University of Michigan), Guy Moshkovitz (City University of New York)

Lower Bounds on FSS from Dynamic Data Structures

Niv Gilboa (Ben-Gurion University of the Negev), Daniel Weber (Ben-Gurion University of the Negev)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String

Lijie Chen (University of California at Berkeley), Yang Hu (Tsinghua University), Hanlin Ren (University of Oxford)

Characterizing Off-Chain Influence-Proof Transaction Fee Mechanisms

Aadityan Ganesh (Princeton University), Clayton Thomas (Yale University), S. Matthew Weinberg (Princeton University)

Total Search Problems in ZPP

Noah Fleming (Columbia University and Lund University), Stefan Grosser (McGill University), Siddhartha Jain (University of Texas at Austin), Jiawei Li (University of Texas at Austin), Hanlin Ren (University of Oxford), Morgan Shirley (University of Victoria), Weiqiang Yuan (EPFL)

On the complexity of unique quantum witnesses and quantum approximate counting

Anurag Anshu (Harvard University), Jonas Haferkamp (Saarland University), Yeongwoo Hwang (Harvard University), Quynh T Nguyen (Harvard University)

Weighted chairman assignment and flow-time scheduling

Siyue Liu (Carnegie Mellon University), Victor Reis (Microsoft Research)

Query Lower Bounds for Correlation Clustering under Memory Constraints

Sumegha Garg (Rutgers University), Songhua He (Rutgers University), Periklis A. Papakonstantinou (Rutgers University)