ITCS 2024 Accepted Papers

  • 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)

  • Smooth Nash Equilibria: Algorithms and Complexity
    Constantinos Daskalakis (EECS, MIT), Noah Golowich (EECS, MIT), Nika Haghtalab (UC Berkeley) and Abhishek Shetty (UC Berkeley)

  • 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)