Time- and Communication-Efficient Overlay Network Construction via Gossip
Fabien Dufoulon (University of Houston), Michael Moorman (University of Houston), William K. Moses Jr. (Durham University) and Gopal Pandurangan (University of Houston)
Small sunflowers and the structure of slice rank decompositions
Thomas Karam (University of Oxford)
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Gramoz Goranci (University of Vienna), Monika Henzinger (IST Austria), Harald Räcke (Technical University Munich), Sushant Sachdeva (University of Toronto) and A. R. Sricharan (University of Vienna)
The Message Complexity of Distributed Graph Optimization
Fabien Dufoulon (University of Houston), Shreyas Pai (Aalto University), Gopal Pandurangan (University of Houston), Sriram V. Pemmaraju (University of Iowa) and Peter Robinson (Augusta University)
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
Josh Alman (Columbia), Ethan Turok (Columbia), Hantao Yu (Columbia) and Hengzhi Zhang (Columbia)
Towards Stronger Depth Lower Bounds
Gabriel Bathie (DI ENS, PSL Research University, and LaBRI, Université de Bordeaux) and Ryan Williams (MIT)
Advanced Composition Theorems for Differential Obliviousness
Mingxun Zhou (Carnegie Mellon University), Mengshi Zhao (The University of Hong Kong), T-H. Hubert Chan (The University of Hong Kong) and Elaine Shi (Carnegie Mellon University)
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
Iddo Tzameret (Imperial College London) and Lu-Ming Zhang (London School of Economics)
Total NP Search Problems with Abundant Solutions
Jiawei Li (University of Texas at Austin)
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes
Louis Golowich (UC Berkeley) and Tali Kaufman (Bar Ilan University)
Proving Unsatisfiability with Hitting Formulas
Yuval Filmus (Technion - Israel Institute of Technology, Haifa, Israel), Edward A. Hirsch (Ariel University, Ariel, Israel), Artur Riazanov (EPFL, Lausanne, Switzerland), Alexander Smal (Technion - Israel Institute of Technology, Haifa, Israel) and Marc Vinyals (University of Auckland, Auckland, New Zealand)
Testing Intersecting and Union-Closed Families
Xi Chen (Columbia University), Anindya De (University of Pennsylvania), Yuhao Li (Columbia University), Shivam Nadimpalli (Columbia University) and Rocco A. Servedio (Columbia University)
Tensor Reconstruction Beyond Constant Rank
Shir Peleg (Tel Aviv University), Amir Shpilka (Tel-Aviv University) and Ben Lee Volk (Reichman University)
Are there graphs whose shortest path structure requires large edge weights?
Aaron Bernstein (Rutgers University), Greg Bodwin (University of Michigan) and Nicole Wein (Simons Institute)
A Combinatorial Approach to Robust PCA
Weihao Kong (Google Research), Mingda Qiao (University of California, Berkeley) and Rajat Sen (Google Research)
Distribution Testing with a Confused Collector
Renato Ferreira Pinto Jr. (University of Waterloo) and Nathaniel Harms (EPFL)
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
Zhao Song (Adobe Research), Lichen Zhang (Massachusetts Institute of Technology) and Ruizhe Zhang (Simons Institute for the Theory of Computing)
Quantum Money from Abelian Group Actions
Mark Zhandry (NTT Research)
Collective Tree Exploration via Potential Function Method
Romain Cosson (Inria, Paris) and Laurent Massoulie (Inria, Paris)
Classical Verification of Quantum Learning
Matthias C. Caro (California Institute of Technology, Freie Universität Berlin), Marcel Hinsche (Freie Universität Berlin), Marios Ioannou (Freie Universität Berlin), Alexander Nietner (Freie Universität Berlin) and Ryan Sweke (IBM Quantum)
Pseudorandom Linear Codes are List-Decodable to Capacity
Aaron (Louie) Putterman (Harvard University) and Edward Pyne (MIT)
Discreteness of Asymptotic Tensor Ranks
Jop Briet (CWI), Matthias Christandl (University of Copenhagen), Itai Leigh (Tel-Aviv University), Amir Shpilka (Tel-Aviv University) and Jeroen Zuiddam (University of Amsterdam)
Dynamic Maximal Matching in Clique Networks
Minming Li (City University of Hong Kong), Peter Robinson (Augusta University) and Xianbin Zhu (City University of Hong Kong)
Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
Xingjian Li (Tsinghua University), Qipeng Liu (UCSD), Angelos Pelecanos (UC Berkeley) and Takashi Yamakawa (NTT Social Informatics Laboratories)
On the complexity of isomorphism problems for tensors, groups, and polynomials under the actions of classical groups
Zhili Chen (University of Technology Sydney), Joshua Grochow (Departments of Computer Science and Mathematics, University of Colorado—Boulder, Boulder, CO 80309-0430, United States), Youming Qiao (Center for Quantum Software and Information, University of Technology, Ultimo NSW 2007, Australia), Gang Tang (University of Technology Sydney) and Chuanqi Zhang (University of Technology Sydney)
Determinants vs. Algebraic Branching Programs
Abhranil Chatterjee (Indian Statistical Institute, Kolkata), Mrinal Kumar (TIFR Bombay) and Ben Lee Volk (Reichman University)
Spanning Adjacency Oracles in Sublinear Time
Henry Fleischmann (University of Cambridge) and Greg Bodwin (University of Michigan)
The Space-Time Cost of Purifying Quantum Computations
Mark Zhandry (NTT Research)
A Computational Separation Between Quantum No-cloning and No-telegraphing
Barak Nehoran (Princeton University) and Mark Zhandry (NTT Research & Princeton University)
Kernelization of Counting Problems
Daniel Lokshtanov (University of California Santa Barbara, USA), Pranabendu Misra (Chennai Mathematical Institute), Saket Saurabh (IMSc) and Meirav Zehavi (Ben-Gurion University of the Negev)
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
Euiwoong Lee (University of Michigan) and Pasin Manurangsi (Google Research)
Distributional PAC-Learning from Nisan's Natural Proofs
Ari Karchmer (Boston University)
Winning without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round
Melissa Dutz (Toyota Technological Institute at Chicago) and Avrim Blum (Toyota Technological Institute at Chicago)
On Parallel Repetition of PCPs
Alessandro Chiesa (EPFL), Ziyi Guan (EPFL) and Burcu Yildiz (EPFL)
The Chromatic Number of Kneser Hypergraphs via Consensus Division
Ishay Haviv (The Academic College of Tel Aviv-Yaffo)
Quantum Merlin-Arthur and proofs without relative phase
Roozbeh Bassirian (University of Chicago), Bill Fefferman (University of Chicago) and Kunal Marwaha (University of Chicago)
Differentially Private Approximate Pattern Matching
Teresa Anna Steiner (Technical University of Denmark)
Two-State Spin Systems with Negative Interactions
Yumou Fei (Peking University), Leslie Ann Goldberg (Department of Computer Science, University of Oxford) and Pinyan Lu (Shanghai University of Finance and Economics)
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
Rajarshi Bhattacharjee (University of Massachusetts Amherst), Gregory Dexter (Purdue University), Cameron Musco (University of Massachusetts Amherst), Archan Ray (University of Massachusetts Amherst), Sushant Sachdeva (University of Toronto) and David P. Woodruff (Carnegie Mellon University)
Graph Threading
Erik D. Demaine (MIT), Yael Kirkpatrick (MIT) and Rebecca Lin (MIT)
On the (in)approximability of Combinatorial Contracts
Tomer Ezra (SLMath), Michal Feldman (Tel Aviv University) and Maya Schlesinger (Tel Aviv University)
An Axiomatic Characterization of CFMMs and Equivalence to Prediction Markets
Rafael Frongillo (U. Colorado, Boulder), Maneesha Papireddygari (University of Colorado, Boulder) and Bo Waggoner (U. Colorado, Boulder)
Quantum and classical low-degree learning via a dimension-free Remez inequality
Ohad Klein (Hebrew University), Joseph Slote (California Institute of Technology), Alexander Volberg (Michigan State University) and Haonan Zhang (University of South Carolina)
On generalized corners and matrix multiplication
Kevin Pratt (Carnegie Mellon University)
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
Scott Aaronson (UT Austin/OpenAI), Harry Buhrman (QuSoft/CWI/University of Amsterdam) and William Kretschmer (Simons Institute/UC Berkeley)
FPT Approximation for Capacitated Sum of Radii
Ragesh Jaiswal (IIT Delhi), Amit Kumar (IIT Delhi) and Jatin Yadav (IIT Delhi)
Color Fault-Tolerant Spanners
Asaf Petruschka (Weizmann Institute), Shay Sapir (Weizmann Institute) and Elad Tzailk (Weizmann Institute)
Geometric Covering via Extraction Theorem
Sayan Bandyapadhyay (Portland State University), Anil Maheshwari (Carleton University), Sasanka Roy (Indian Statistical Institute), Michiel Smid (Carleton University) and Kasturi Varadarajan (University of Iowa)
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers
Jason Milionis (Columbia University), Ciamac C. Moallemi (Columbia University) and Tim Roughgarden (Columbia University / a16z crypto)
Loss Minimization Yields Multicalibration for Large Neural Networks
Jarosław Błasiok (Columbia University), Parikshit Gopalan (Apple), Lunjia Hu (Stanford University), Adam Tauman Kalai (Microsoft Research) and Preetum Nakkiran (Apple)
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications
Keller Blackwell (Stanford University) and Mary Wootters (Stanford University)
Deterministic 3SUM-Hardness
Nick Fischer (Weizmann Institute of Science), Piotr Kaliciak (Jagiellonian University) and Adam Polak (Max Planck Institute for Informatics)
Homomorphic Indistinguishability Obfuscation and its Applications
Kaartik Bhushan (Indian Institute of Technology, Mumbai), Venkata Koppula (Indian Institute of Technology, Delhi) and Manoj Prabhakaran (Indian Institute of Technology, Mumbai)
Intersection Classes in TFNP and Proof Complexity
Yuhao Li (Columbia), William Pires (Columbia) and Robert Robere (McGill)
Communicating with Anecdotes
Nika Haghtalab (UC Berkeley), Nicole Immorlica (Microsoft Research), Brendan Lucier (Microsoft Research), Markus Mobius (Microsoft Research) and Divyarthi Mohan (Tel Aviv University)
Simple and Optimal Online Contention Resolution Schemes for $k$-Uniform Matroids
Atanas Dinev (Massachusetts Institute of Technology) and S. Matthew Weinberg (Princeton University)
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations
Siddharth Barman (Indian Institute of Science), Anand Krishna (Indian Institute of Science), Pooja Kulkarni (University of Illinois Urbana-Champaign) and Shivika Narang (Indian Institute of Science)
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False
Noam Mazor (Cornell Tech) and Rafael Pass (Tel Aviv University & Cornell Tech)
Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine
Clément Canonne (University of Sydney) and Yucheng Sun (ETH Zurich)
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions
Huacheng Yu (Princeton University) and Wei Zhan (University of Chicago)
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
Ioannis Anagnostides (Carnegie Mellon University), Alkis Kalavasis (Yale University), Tuomas Sandholm (Carnegie Mellon University) and Manolis Zampetakis (Yale University)
On the Size Overhead of Pairwise Spanners
Idan Shabat (Ben-Gurion University) and Ofer Neiman (Ben-Gurion University)
Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints
Rian Neogi (University of Waterloo), Kanstantsin Pashkovich (University of Waterloo) and Chaitanya Swamy (University of Waterloo)
Rumors with Changing Credibility
Charlotte Out (University of Cambridge), Nicolas Rivera (Universidad de Valparaíso), Thomas Sauerwald (University of Cambridge) and John Sylvester (University of Liverpool)
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis
Gregory Valiant (Stanford)
Differentially Private Medians and Interior Points for Non-Pathological Data
Rose Silver (Northeastern University), Maryam Aliakbarpour (Rice University), Thomas Steinke (Google Research) and Jonathan Ullman (Northeastern University)
Making Progress Based on False Discoveries
Roi Livni (Tel Aviv University)
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics), Allan Grønlund (Aarhus University), Marvin Künnemann (RPTU Kaiserslautern-Landau) and Kasper Green Larsen (Aarhus University)
Recursive Error Reduction for Regular Branching Programs
Eshan Chattopadhyay (Cornell University) and Jyun-Jie Liao (Cornell University)
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees
Yi-Jun Chang (National University of Singapore)
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
Prantar Ghosh (Georgetown University) and Vihan Shah (University of Waterloo)
Homogeneous algebraic complexity theory and algebraic formulas
Pranjal Dutta (School of Computing, National University of Singapore (NUS)), Fulvio Gesmundo (Saarland University), Christian Ikenmeyer (University of Warwick), Gorav Jindal (Max Planck Institute for Software Systems, Saarbrücken) and Vladimir Lysikov (Ruhr University Bochum)
Parity vs. AC0 with quantum preprocessing
Joseph Slote (California Institute of Technology)
Maximizing Miner Revenue in Transaction Fee Mechanism Design
Ke Wu (CMU), Elaine Shi (CMU) and Hao Chung (Carnegie Mellon University)
Learning Arithmetic Circuits in the Presence of Noise: A General Framework and Applications to Unsupervised Learning
Pritam Chandra (Microsoft Research), Ankit Garg (Microsoft Research India), Tanmay Sinha (Microsoft Research), Neeraj Kayal (Microsoft Research) and Kunal Mittal (Princeton University)
Quantum Event Learning and Gentle Random Measurements
John Bostanci (Columbia University) and Adam Bene Watts (University of Waterloo)
Influence Maximization in Ising Models
Zongchen Chen (University at Buffalo) and Elchanan Mossel (MIT)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions
Arvind V. Mahankali (Stanford University), David P. Woodruff (Carnegie Mellon University) and Ziyu Zhang (Massachusetts Institute of Technology)
An improved protocol for ExactlyN with more than 3 players
Lianna Hambardzumyan (Hebrew University of Jerusalem), Toniann Pitassi (Columbia University), Suhail Sherif (University of Lisbon), Morgan Shirley (University of Toronto) and Adi Shraibman (The Academic College of Tel Aviv-Yaffo)
Modularity and graph expansion
Baptiste Louf (CNRS Bordeaux), Colin McDiarmid (University of Oxford) and Fiona Skerman (Uppsala University)
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Monika Henzinger (IST Austria), Barna Saha (University of California, San Diego), Martin P. Seybold (University of Vienna) and Christopher Ye (University of California, San Diego)
Noisy decoding by shallow circuits with parities: classical and quantum
Jop Briet (CWI), Harry Buhrman (CWI, University of Amsterdam), Davi Castro-Silva (CWI) and Niels M. P. Neumann (CWI, TNO)
Testing and Learning Convex Sets in the Ternary Hypercube
Hadley Black (UCLA), Eric Blais (University of Waterloo) and Nathaniel Harms (EPFL)
One-Way Functions vs. TFNP: Simpler and Improved
Lukáš Folwarczný (Czech Academy of Sciences and Charles University), Mika Göös (EPFL), Pavel Hubáček (Czech Academy of Sciences and Charles University), Gilbert Maystre (EPFL) and Weiqiang Yuan (EPFL)
Quantum Pseudoentanglement
Scott Aaronson (University of Texas, Austin), Adam Bouland (Stanford University), Bill Fefferman (University of Chicago), Soumik Ghosh (University of Chicago), Umesh Vazirani (University of California, Berkeley), Chenyi Zhang (Stanford University) and Zixin Zhou (Stanford University)
Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election
Rex Fernando (CMU), Yuval Gelles (Hebrew University) and Ilan Komargodski (Hebrew University and NTT Research)
Pseudorandom Strings from Pseudorandom Quantum States
Prabhanjan Ananth (UC Santa Barbara), Yao-Ting Lin (UC Santa Barbara) and Henry Yuen (Columbia University)
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions
Justin Y. Chen (MIT), Piotr Indyk (MIT) and David P. Woodruff (Carnegie Mellon University)
Extractors for polynomial sources over $F_2$
Eshan Chattopadhyay (Cornell University), Jesse Goodman (Cornell University) and Mohit Gurumukhani (Cornell University)
Lower Bounds for Planar Arithmetic Circuits
Ramya C (Institute of Mathematical Sciences) and Pratik Shastri (Institute of Mathematical Sciences)
TFNP Intersections through the Lens of Feasible Disjunction
Pavel Hubáček (Czech Academy of Sciences and Charles University), Erfan Khaniki (Czech Academy of Sciences and Charles University) and Neil Thapen (Czech Academy of Sciences)
A VLSI Circuit Model Accounting for Wire Delay
Nathaniel Young (Unaffiliated), Ce Jin (MIT) and Ryan Williams (MIT)
General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation
Aleksandar Nikolov (University of Toronto) and Haohua Tang (University of Toronto)
Rethinking Fairness for Human-AI Collaboration
Haosen Ge (Wharton School, University of Pennsylvania), Hamsa Bastani (Wharton School, University of Pennsylvania) and Osbert Bastani (University of Pennsylvania)
Sampling, Flowers and Communication
Huacheng Yu (Princeton University) and Wei Zhan (University of Chicago)
Quickly Determining Who Won an Election
Lisa Hellerstein (New York University), Naifeng Liu (University of Mannheim) and Kevin Schewior (University of Southern Denmark)
Fraud Detection for Random Walks
Varsha Dani (Rochester Institute of Technology), Thomas P. Hayes (University at Buffalo), Seth Pettie (University of Michigan) and Jared Saia (University of New Mexico)
On The Black-Box Complexity of Correlation Intractability
Nico Dottling (Helmholtz Center for Information Security (CISPA)) and Tamer Mour (Weizmann Institute for Science)
Exponential-time Approximation Schemes via Compression
Tanmay Inamdar (University of Bergen), Madhumita Kundu (University of Bergen), Pekka Parviainen (University of Bergen), M. S. Ramanujan (University of Warwick) and Saket Saurabh (Institute of Mathematical Sciences)
Property Testing with Online Adversaries
Omri Ben-Eliezer (Massachusetts Institute of Technology), Esty Kelman (Boston University and Massachusetts Institute of Technology), Uri Meir (Tel Aviv University) and Sofya Raskhodnikova (Boston University)
Equivocal Blends: Prior Independent Lower Bounds
Aleck Johnsen (Northwestern University) and Jason Hartline (Northwestern University)
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio
Mayank Goswami (Queens College, CUNY, New York) and Riko Jacob (IT University of Copenhagen)