STOC 2024

His NYU page

Anupam Gupta just asked us to help announce the next 56th ACM Symposium on Theory of Computing (STOC 2024). His own news is a recent move from CMU to NYU.

This comes together with TheoryFest 2024 in an expanded 5-day format. The fun is at the Sheraton Vancouver Wall Centre in Vancouver, British Columbia, Canada from Monday, June 24 through Friday, June 28. The registration link is http://acm-stoc.org/stoc2024/registration.html

In addition to the STOC 2024 paper talks, the program features keynote talks by Michal Feldman, Jakub Pachocki, and Tim Roughgarden, and workshops on Algorithmic Problems in Modern LLMs, Extremal Combinatorics, Length-Constrained Expanders, Online Resource Allocation, and a special workshop on TCS Mentoring, Diversity, and Outreach.

Accepted Papers

• “Swap Cosystolic Expansion,” Yotam Dikstein (Institute for Advanced Study); Irit Dinur (Weizmann Institute of Science)
• “On the Pauli Spectrum of QAC0,” Shivam Nadimpalli, Natalie Parham (Columbia University); Francisca Vasconcelos (University of California, Berkeley); Henry Yuen (Columbia University)

• “Influences in Mixing Measures,” Frederic Koehler (Stanford University); Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer, Elchanan Mossel (MIT)

• “Parallel Sampling via Counting,” Nima Anari, Ruiquan Gao, Aviad Rubinstein (Stanford University)

• “Local minima in quantum systems,” Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou (California Institute of Technology)

• “Approximating Small Sparse Cuts,” Aditya Anand, Euiwoong Lee (University of Michigan); Jason Li (UC Berkeley); Thatchaphol Saranurak (University of Michigan)

• “Detecting Low-Degree Truncation,” Anindya De, Huan Li (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University)

• “How Random CSPs Fool Hierarchies,” Siu On Chan, Hiu Tsun Ng (The Chinese University of Hong Kong); Sijin Peng (Tsinghua University)

• “Fair Division via Quantile Shares,” Yakov Babichenko (Technion – Israel Institute of Technology); Michal Feldman (Tel Aviv University); Ron Holzman (Technion – Israel Institute of Technology); Vishnu V. Narayan (Tel Aviv University)

• “Learning shallow quantum circuits,” Hsin-Yuan Huang (Caltech); Yunchao Liu (UC Berkeley); Michael Broughton (Google Quantum AI); Isaac Kim (UC Davis); Anurag Anshu (Harvard University); Zeph Landau (UC Berkeley); Jarrod R. McClean (Google Quantum AI)

• “Prophet Inequalities with Recourse,” Farbod Ekbatani, Rad Niazadeh (University of Chicago Booth School of Business); Pranav Nuti, Jan Vondrak (Stanford)

• “Perfect Zero-Knowledge PCPs for \#P,” Tom Gur, Jack O’Connor (University of Cambridge); Nicholas Spooner (University of Warwick/NYU)

• “Black-Box PPP is not Turing-Closed,” Noah Fleming (Memorial University of Newfoundland); Stefan Grosser (McGill); Toniann Pitassi (Columbia); Robert Robere (McGill)

• “Commitments from Quantum One-Wayness,” Dakshita Khurana (University of Illinois at Urbana-Champaign); Kabir Tomer (University of Illinois Urbana-Champaign)

• “Hardness Condensation by Restriction,” Mika Goos (EPFL); Ilan Newman (University of Haifa); Artur Riazanov, Dmitry Sokolov (EPFL)

• “Product Mixing in Compact Lie Groups,” David Ellis (University of Bristol); Guy Kindler, Noam Lifshitz (Hebrew University of Jerusalem); Dor Minzer (MIT)

• “One-Way Functions and Zero Knowledge,” Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology)

• “Combinatorial Correlation Clustering,” Vincent Cohen-Addad (Google Research, France); Marcin Pilipczuk (University of Warsaw); David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan, Hanwen Zhang (University of Copenhagen)

• “Batch Proofs are Statistically Hiding,” Nir Bitansky (Tel Aviv University); Chethan Kamath (IIT Bombay); Omer Paneth (Tel Aviv University); Ron D. Rothblum (Technion); Prashant Nalini Vasudevan (NUS)

• “0-1 Knapsack in Nearly Quadratic Time,” Ce Jin (MIT)

• “Better coloring of 3-colorable graphs,” Ken-ichi Kawarabayashi (National Institute of Informatics, The University of Tokyo); Mikkel Thorup (University of Copenhagen); Hirotaka Yoneda (The University of Tokyo)

• “Sparsifying generalized linear models,” Arun Jambulapati (Simons Institute); James R Lee (University of Washington); Yang P. Liu (Institute for Advanced Study); Aaron Sidford (Stanford University)

• “Bilateral Trade with Correlated Values,” Shahar Dobzinski (Weizmann); Ariel Shaulker (Weizmann Institute)

• “Nonlinear dynamics for the Ising model,” Pietro Caputo (Univ Rome III); Alistair Sinclair (U.C. Berkeley)

• “Optimal Online Discrepancy Minimization,” Janardhan Kulkarni (Microsoft Research); Victor Reis (Institute for Advanced Study); Thomas Rothvoss (University of Washington)

• “Low-Step Multi-Commodity Flow Emulators,” Bernhard Haeupler (ETH Zurich); D Ellis Hershkowitz (Brown University); Jason Li (UC Berkeley); Antti Roysko (ETH Zurich); Thatchaphol Saranurak (University of Michigan)

• “Almost Linear Size Edit Distance Sketch,” Michal Kouck? (Charles University/Rutgers University); Michael Saks (Rutgers University)

• “Edge-Disjoint Paths in Eulerian Digraphs,” Dario Giuliano Cavallaro (TU Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Stephan Kreutzer (TU Berlin)

• “Optimization with pattern-avoiding input,” Benjamin Aram Berendsohn, Laszlo Kozma (Freie Universitat Berlin); Michal Opler (Czech Technical University in Prague)

• “SNARGs Under LWE via Propositional Proofs,” Zhengzhong Jin (MIT CSAIL); Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Princeton); Vinod Vaikuntanathan (MIT CSAIL)

• “Planted Clique Conjectures Are Equivalent,” Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Tokyo Institute of Technology)

• “A Nearly Quadratic-Time FPTAS for Knapsack,” Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)

• “Two prover perfect zero knowledge for MIP*,” Kieran Mastel, William Slofstra (University of Waterloo)

• “Locality Bounds for Sampling Hamming Slices,” Daniel M. Kane, Anthony Ostuni (UC San Diego); Kewen Wu (UC Berkeley)

• “Calibrated Language Models Must Hallucinate,” Adam Tauman Kalai (Microsoft Research); Santosh Vempala (Georgia Tech)

• “Nonlocality under Computational Assumptions,” Grzegorz Gluch, Khashayar Barooti (EPFL); Alexandru Gheorghiu (Chalmers University of Technology); Marc-Olivier Renou (Inria, Universitee Paris-Saclay, CPHT, Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau)

• “Approximating Partition in Near-Linear Time,” Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)

• “On Approximability of Satisfiable k-CSPs,”: IV Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT)

• “Explicit two-sided unique-neighbor expanders,” Jun-Ting Hsieh (Carnegie Mellon University); Theo McKenzie (Stanford University); Sidhanth Mohanty (MIT); Pedro Paredes (Princeton University)

• “Beating Brute Force for Compression Problems,” Shuichi Hirahara (National Institute of Informatics, Tokyo, Japan); Rahul Ilango, Ryan Williams (MIT)

• “Nearly Optimal Fault Tolerant Distance Oracle,” Dipan Dey, Manoj Gupta (IIT Gandhinagar)

• “Private graphon estimation via sum-of-squares,” Hongjie Chen, Jingqiu Ding (ETH Zurich); Tommaso D’Orsi (Bocconi University); Yiding Hua (ETH Zurich); Chih-Hung Liu (National Taiwan University); David Steurer (ETH Zurich)

• “Near Optimal Alphabet-Soundness Tradeoff PCPs,” Dor Minzer, Kai Zhe Zheng (MIT)

• “Memory Checking Requires Logarithmic Overhead,” Elette Boyle (Reichman University and NTT Research); Ilan Komargodski (Hebrew University and NTT Research); Neekon Vafa (MIT)

• “Self-Improvement for Circuit-Analysis Problems,” Ryan Williams (MIT)

• “Structural Complexities of Matching Mechanisms,” Yannai A. Gonczarowski (Harvard University); Clayton Thomas (Microsoft Research)

• “On the Power of Homogeneous Algebraic Formulas,” Herve Fournier (IMJ-PRG, Universite Paris Cite); Nutan Limaye (IT University of Copenhagen); Srikanth Srinivasan (University of Copenhagen); Sebastien Tavenas (Universite Savoie Mont Blanc, CNRS, LAMA)

• “Ghost Value Augmentation for k-ECSS and k-ECSM,” D Ellis Hershkowitz (Brown University); Nathan Klein (Institute for Advanced Study); Rico Zenklusen (ETH Zurich)

• “Relaxed Local Correctability from Local Testing,” Vinayak M. Kumar, Geoffrey Mon (University of Texas at Austin)

• “On the Power of Interactive Proofs for Learning,” Tom Gur (University of Cambridge); Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh (Simon Fraser University); Ninad Rajgopal (University of Cambridge); Bahar Salamatian, Igor Shinkar (Simon Fraser University)

• “Local Borsuk-Ulam, Stability, and Replicability,” Zachary Chase, Bogdan Chornomaz, Shay Moran (Technion); Amir Yehudayoff (Technion-IIT)

• “Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques,” Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu (MIT)

• “Tree Evaluation is in Space ,” James Cook; Ian Mertz (University of Warwick)

• “Quantum State Obfuscation from Classical Oracles,” James Bartusek (UC Berkeley); Zvika Brakerski (Weizmann); Vinod Vaikuntanathan (MIT CSAIL)

• “Quantum Time-Space Tradeoffs for Matrix Problems,” Paul Beame (University of Washington); Niels Kornerup (University of Texas at Austin); Michael Whitmeyer (University of Washington)

• “Knapsack with Small Items in Near-Quadratic Time,” Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics)

• “Lower bounds for regular resolution over parities,” Klim Efremenko (Ben-Gurion University of the Negev); Michal Garlik (Imperial College London); Dmitry Itsykson (Ben-Gurion University of the Negev)

• “Data-Dependent LSH for the Earth Mover’s Distance,” Rajesh Jayaram (Google Research); Erik Waingarten, Tian Zhang (University of Pennsylvania)

• “Packing even directed circuits quarter-integrally,” Maximilian Gorsky (Technische Universitat Berlin); Ken-ichi Kawarabayashi (National Institute of Informatics, Japan); Stephan Kreutzer (Technische Universitat Berlin); Sebastian Wiederrecht (Institute for Basic Science, South Korea)

• “Hypergraph Unreliability in Quasi-Polynomial Time,” Ruoxu Cen (Duke University); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University)

• “Reconfiguration of Basis Pairs in Regular Matroids,” Kristof Berczi, Bence Matravolgyi, Tamas Schwarcz (Eotvos Lorand University)

• “The Power of Adaptivity in Quantum Query Algorithms,” Uma Girish (Princeton University); Makrand Sinha (University of Illinois at Urbana-Champaign); Avishay Tal, Kewen Wu (University of California at Berkeley)

• “Online Edge-Coloring is (Nearly) as Easy as Offline,” Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); Ola Svensson, Radu Vintan (EPFL); David Wajc (Technion — Israel Institute of Technology)

• “How to Use Quantum Indistinguishability Obfuscation,” Andrea Coladangelo (University of Washington); Sam Gunn (UC Berkeley)

• “Semigroup algorithmic problems in metabelian groups,” Ruiwen Dong (University of Oxford)

• “Prize-Collecting Steiner Tree: A 1.79 Approximation,” Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi (University of Maryland)

• “Supermodular Approximation of Norms and Applications,” Thomas Kesselheim (University of Bonn); Marco Molinaro (PUC-Rio); Sahil Singla (Georgia Tech)

• “Optimal Load-Balanced Scalable Distributed Agreement,” Yuval Gelles (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research)

• “Trickle-Down in Localization Schemes and Applications,” Nima Anari, Frederic Koehler, Thuy-Duong Vuong (Stanford University)

• “Sampling Balanced Forests of Grids in Polynomial Time,” Sarah Cannon (Claremont McKenna College); Wesley Pegden (Carnegie Mellon University); Jamie Tucker-Foltz (Harvard University)

• “XOR Lemmas for Communication via Marginal Information,” Siddharth Iyer (University of Washington); Anup Rao (School of Computer Science, University of Washington)

• “Complexity-Theoretic Implications of Multicalibration,” Silvia Casacuberta (University of Oxford); Cynthia Dwork, Salil Vadhan (Harvard University)

• “Random (log n)-CNF are Hard for Cutting Planes (Again),” Dmitry Sokolov (EPFL)

• “Classical simulation of peaked shallow quantum circuits,” Sergey Bravyi (IBM Quantum, T. J. Watson Research Center); David Gosset, Yinchen Liu (University of Waterloo)

• “The Power of Two-sided Recruitment in Two-sided Markets,” Yang Cai (Yale University); Christopher Liaw, Aranyak Mehta (Google); Mingfei Zhao (Google Research)

• “Generalized GM-MDS: Polynomial Codes are Higher Order MDS,” Joshua Brakensiek (Stanford University); Manik Dhar (MIT); Sivakanth Gopi (Microsoft Research)

• “Optimal Embedding Dimension for Sparse Subspace Embeddings,” Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, Mark Rudelson (University of Michigan)

• “-Approximation of Knapsack in Nearly Quadratic Time,” Xiao Mao (Stanford University)

• “Local Correction of Linear Functions over the Boolean Cube,” Prashanth Amireddy (Harvard University); Amik Raj Behera (Aarhus University); Manaswi Paraashar, Srikanth Srinivasan (University of Copenhagen); Madhu Sudan (Harvard University)

• “Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams,” Sepehr Assadi (University of Waterloo and Rutgers University); Gillat Kol, Zhijun Zhang (Princeton University)

• “Improved Stabilizer Estimation via Bell Difference Sampling,” Sabee Grewal, Vishnu Iyer (University of Texas at Austin); William Kretschmer (Simons Institute); Daniel Liang (Rice University)

• “A Flat Wall Theorem for Matching Minors in Bipartite Graphs,” Archontia C. Giannopoulou (Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece); Sebastian Wiederrecht (Discrete Mathematics Group, IBS, Daejeon, South Korea)

• “Strong Algebras and Radical Sylvester-Gallai Configurations,” Rafael Oliveira, Akash Kumar Sengupta (University of Waterloo)

• “Revisiting Local Computation of PageRank: Simple and Optimal,” Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang (Renmin University of China)

• “Solving Dense Linear Systems Faster than via Preconditioning,” Michal Derezinski, Jiaming Yang (University of Michigan)

• “Symmetric Exponential Time Requires Near-Maximum Circuit Size,” Lijie Chen (University of California at Berkeley); Shuichi Hirahara (National Institute of Informatics); Hanlin Ren (University of Oxford)

• “Approximate Earth Mover’s Distance in Truly-Subquadratic Time,” Lorenzo Beretta (BARC, University of Copenhagen); Aviad Rubinstein (Stanford University)

• “Approximating Maximum Matching Requires Almost Quadratic Time,” Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University)

• “Strategic Budget Selection in a Competitive Autobidding World,” Yiding Feng (University of Chicago); Brendan Lucier, Aleksandrs Slivkins (Microsoft Research)

• “Constant Query Local Decoding Against Deletions is Impossible,” Meghal Gupta (UC Berkeley)

• “Minimum Star Partitions of Simple Polygons in Polynomial Time,” Mikkel Abrahamsen (University of Copenhagen); Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); Andre Nusser, Hanwen Zhang (University of Copenhagen)

• “No Complete Problem for Constant-Cost Randomized Communication,” Yuting Fang (The Ohio State University); Lianna Hambardzumyan (The Hebrew University of Jerusalem); Nathaniel Harms (EPFL); Pooya Hatami (The Ohio State University)

• “Polylog-Competitive Deterministic Local Routing and Scheduling,” Bernhard Haeupler (ETH Zurich & CMU); Shyamal Patel (Columbia University); Antti Roeyskoe (ETH Zurich); Cliff Stein (Columbia University); Goran Zuzic (Google Research)

• “Local geometry of NAE-SAT solutions in the condensation regime,” Allan Sly (Princeton University); Youngtak Sohn (MIT)

• “Characterizing Direct Product Testing via Coboundary Expansion,” Mitali Bafna, Dor Minzer (MIT)

• “Counting Small Induced Subgraphs with Edge-monotone Properties,” Simon Doring (Max Planck Institute for Informatics; Saarbrucken Graduate School of Computer Science; Saarland Informatics Campus); Daniel Marx (CISPA Helmholtz Center for Information Security); Philip Wellnitz (Max Planck Institute for Informatics; Saarland Informatics Campus)

• “Breaking the VLB Barrier for Oblivious Reconfigurable Networks,” Tegan Wilson, Daniel Amir, Nitika Saran, Robert Kleinberg (Cornell University); Vishal Shrivastav (Purdue University); Hakim Weatherspoon (Cornell University)

• “Prophet Inequalities Require Only a Constant Number of Samples,” Andres Cristi (Universidad de Chile); Bruno Ziliotto (CNRS)

• “On Optimal Coreset Construction for Euclidean (k,z)-clustering,” Lingxiao Huang (Nanjing University); Jian Li, Xuan Wu (Tsinghua University)

• “No distributed quantum advantage for approximate graph coloring,” Xavier Coiteux-Roy (School of Computation, Information and Technology, Technical University of Munich, Munich Center for Quantum Science and Technology); Francesco d’Amore (Aalto University and Bocconi University); Rishikesh Gajjala (Indian Institute of Science and Aalto University); Fabian Kuhn (University of Freiburg); Francois Le Gall (Nagoya University); Henrik Lievonen, Augusto Modanese (Aalto University); Marc-Olivier Renou (Inria, Universitee Paris-Saclay, CPHT, Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau); Gustav Schmid (University of Freiburg); Jukka Suomela (Aalto University)

• “Circuit-to-Hamiltonian from tensor networks and fault tolerance,” Anurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Quynh T Nguyen (Harvard University)

• “On the Communication Complexity of Approximate Pattern Matching,” Tomasz Kociumaka (Max Planck Institute for Informatics, SIC); Jakob Nogler (ETH Zurich); Philip Wellnitz (Max Planck Institute for Informatics, SIC)

• “The Complexity of Computing KKT Solutions of Quadratic Programs,” John Fearnley (University of Liverpool); Paul W. Goldberg, Alexandros Hollender (University of Oxford); Rahul Savani (University of Liverpool)

• “Sampling Proper Colorings on Line Graphs Using (1+o(1))? Colors,” Yulin Wang, Chihao Zhang (Shanghai Jiao Tong University); Zihan Zhang (Graduate Institute for Advanced Studies, SOKENDAI)

• “Connectivity Labeling and Routing with Multiple Vertex Failures,” Merav Parter, Asaf Petruschka (Weizmann Institute of Science); Seth Pettie (University of Michigan)

• “No-Regret Learning in Bilateral Trade via Global Budget Balance,” Martino Bernasconi (Bocconi University); Matteo Castiglioni (Politecnico di Milano); Andrea Celli (Bocconi University); Federico Fusco (Sapienza University of Rome)

• “Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators,” Shivam Nadimpalli, Shyamal Patel (Columbia University)

• “Combinatorial Characterizations of Monadically NIP Graph Classes,” Jan Dreier (TU Wien); Nikolas Mahlmann (University of Bremen); Szymon Torunczyk (University of Warsaw)

• “An efficient quantum parallel repetition theorem and applications,” John Bostanci (Columbia University); Luowen Qian (Boston University); Nick Spooner (University of Warwick & NYU); Henry Yuen (Columbia University)

• “Dynamic O(arboricity) coloring in polylogarithmic worst-case time,” Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)

• “Testing Closeness of Multivariate Distributions via Ramsey Theory,” Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane, Sihan Liu (University of California, San Diego)

• “Computing a Fixed Point of Contraction Maps in Polynomial Queries,” Xi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University)

• “Orthogonal arrays and universal hashing with arbitrary parameters,” Nicholas Harvey, Arvin Sahami (UBC)

• “Quantum and classical query complexities of functions of matrices,” Ashley Montanaro (University of Bristol); Changpeng Shao (Academy of Mathematics and Systems Science, Chinese Academy of Sciences)

• “Proof of the density threshold conjecture for pinwheel scheduling,” Akitoshi Kawamura (Kyoto University)

• “AG codes achieve list decoding capacity over constant-sized fields,” Joshua Brakensiek (Stanford University); Manik Dhar (MIT); Sivakanth Gopi (Microsoft Research); Zihan Zhang (The Ohio State University)

• “Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval,” William Kuszmaul (Harvard University); Stefan Walzer (Karlsruhe Institute of Technology)

• “Learning quantum Hamiltonians at any temperature in polynomial time,” Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley)

• “Semidefinite programs simulate approximate message passing robustly,” Misha Ivkov, Tselil Schramm (Stanford)

• “Understanding the Cluster Linear Program for Correlation Clustering,” Nairen Cao (Boston College); Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (Nanjing University); Alantha Newman (CNRS-Universite Grenoble Alpes); Lukas Vogl (Ecole Polytechnique Federale de Lausanne)

• “Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances,” Spencer Compton, Gregory Valiant (Stanford University)

• “Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem,” Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie (NYU Shanghai); Yuping Ye (East China Normal University and NYU Shanghai)

• “An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes,” Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University)

• “Robust recovery for stochastic block models, simplified and generalized,” Sidhanth Mohanty (MIT); Prasad Raghavendra, David Wu (U.C. Berkeley)

• “Semidefinite programming and linear equations vs. homomorphism problems,” Lorenzo Ciardo, Stanislav Zivny (University of Oxford)

• “On The Fourier Coefficients of High-Dimensional Random Geometric Graphs,” Kiril Bangachev, Guy Bresler (MIT)

• “Single-Source Shortest Paths with Negative Real Weights in O(mn8/9) Time,” Jeremy T. Fineman (Georgetown University)

• “Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes,” Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin (TTIC)

• “Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs,” Sayan Bhattacharya, Peter Kiss (University of Warwick); Aaron Sidford (Stanford University); David Wajc (Technion)

• “Approaching the Quantum Singleton Bound with Approximate Error Correction,” Thiago Bergamaschi, Louis Golowich, Sam Gunn (UC Berkeley)

• “ Passes is Optimal for Semi-Streaming Maximal Independent Set,” Sepehr Assadi (Rutgers University and University of Waterloo); Christian Konrad, Kheeran K. Naidu (University of Bristol); Janani Sundaresan (University of Waterloo)

• “A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors,” Brent Waters (University of Texas at Austin and NTT Research)

• “Maximum Bipartite Matching in Time via a Combinatorial Algorithm,” Julia Chuzhoy (Toyota Technological Institute at Chicago); Sanjeev Khanna (University of Pennsylvania)

• “Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers,” Tuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London)

• “Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis,” Venkatesan Guruswami (University of California, Berkeley); Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Kewen Wu (University of California, Berkeley)

• “Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time,” Xiao Mao (Stanford University)

• “Limitations of Stochastic Selection Problems with Pairwise Independent Priors,” Shaddin Dughmi, Yusuf Kalayci, Neel Patel (University of Southern California)

• “The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True,” Andreas Bjorklund (IT University of Copenhagen); Petteri Kaski (Aalto University)

• “Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs,” Pravesh Kothari (CMU); Aaron Potechin (University of Chicago); Jeff Xu (CMU)

• “Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth,” Tuukka Korhonen (University of Bergen); Marek Sokolowski (University of Warsaw)

• “Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries,” Xi Chen (Columbia University); Yumou Fei (Peking University); Shyamal Patel (Columbia University)

• “Constrained Submodular Maximization via New Bounds for DR-Submodular Functions,” Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa)

• “New Graph and Hypergraph Container Lemmas with Applications in Property Testing,” Eric Blais, Cameron Seth (University of Waterloo)

• “A one-query lower bound for unitary synthesis and breaking quantum cryptography,” Alex Lombardi (Princeton); Fermi Ma (Simons Institute and UC Berkeley); John Wright (UC Berkeley)

• “A New Information Complexity Measure for Multi-Pass Streaming with Applications,” Mark Braverman (Princeton University); Sumegha Garg (Rutgers University); Qian Li (Shenzhen Research Institute of Big Data); Shuo Wang (Shanghai Jiao Tong University); David P. Woodruff (CMU); Jiapeng Zhang (University of Southern California)

• “Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication,” Benjamin Rossman (Duke University)

• “Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation,” Brent Waters (University of Texas at Austin and NTT Research); David J. Wu (University of Texas at Austin)

• “From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces,” Yuval Dagan (UC Berkeley); Constantinos Daskalakis (EECS, MIT); Maxwell Fishelson (Massachusetts Institute of Technology); Noah Golowich (MIT)

• “Communication Lower Bounds for Collision Problems via Density Increment Arguments,” Guangxu Yang, Jiapeng Zhang (University of Southern California)

• “An optimal tradeoff between entanglement and copy complexity for state tomography,” Sitan Chen (Harvard University); Jerry Li (Microsoft Research); Allen Liu (MIT)

• “Improving the Bit Complexity of Communication for Distributed Convex Optimization,” Mehrdad Ghadiri (MIT); Yin Tat Lee (University Washington and Microsoft Research); Swati Padmanabhan (MIT); William Swartworth, David P. Woodruff (Carnegie Mellon University); Guanghao Ye (MIT)

• “The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations,” Nicolo Cesa-Bianchi (University of Milan); Tommaso Cesari (University of Ottawa); Roberto Colomboni (Italian Institute of Technology & University of Milan); Federico Fusco (Sapienza); Stefano Leonardi (University of Rome La Sapienza)

• “The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups,” Bireswar Das, Dhara Thakkar (IIT Gandhinagar)

• “A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width,” Jason Gaitonde (Massachusetts Institute of Technology); Elchanan Mossel (MIT)

• “A constant-factor approximation for Nash social welfare with subadditive valuations,” Shahar Dobzinski (Weizmann Institute); Wenzheng Li, Aviad Rubinstein, Jan Vondrak (Stanford University)

• “Fast swap regret minimization and applications to approximate correlated equilibria,” Binghui Peng (Columbia University); Aviad Rubinstein (Stanford University)

• “New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms,” Amir Abboud, Nick Fischer (Weizmann Institute of Science); Zander Kelley (University of Illinois at Urbana-Champaign); Shachar Lovett (UCSD); Raghu Meka (UCLA)

• “Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach,” Saeed Mehraban (Tufts University); Mehrdad Tahmasbi (UIUC)

• “Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs,” Thomas Debris-Alazard (Inria); Pouria Fallahpour (ENS de Lyon, France); Damien Stehle (CryptoLab Inc, Lyon, France)

• “Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping,” Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)

• “Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time,” Peter Gartland (University of California at Santa Barbara); Daniel Lokshtanov (University of California Santa Barbara, USA); Tomas Masarik, Marcin Pilipczuk, Michal Pilipczuk (University of Warsaw); Pawel Rzazewski (Warsaw University of Technology)

• “Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography,” Yilei Chen (Tsinghua University and Shanghai Qi Zhi Institute); Jiatu Li (Massachusetts Institute of Technology)

• “Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond,” Hossein Esfandiari (Google); Praneeth Kacham (Carnegie Mellon University); Vahab Mirrokni (Google Research); David P. Woodruff (Carnegie Mellon University); Peilin Zhong (Google Research)

• “Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy,” Swee Hong Chan (Rutgers University); Igor Pak (UCLA)

• “Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles,” Noah Golowich, Ankur Moitra, Dhruv Rohatgi (MIT)

• “Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform,” Zeyong Li (National University of Singapore)

• “A stronger connection between the asymptotic rank conjecture and the set cover conjecture,” Kevin Pratt (New York University)

• “Explicit separations between randomized and deterministic Number-on-Forehead communication,” Zander Kelley (University of Illinois at Urbana-Champaign); Shachar Lovett (UCSD); Raghu Meka (UCLA)

• “A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications,” Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich)

• “Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More,” Ce Jin, Yinzhan Xu (MIT)

• “Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields,” Omar Alrabiah, Venkatesan Guruswami (UC Berkeley); Ray Li (Santa Clara University)

• “Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time Routability,” Mohsen Ghaffari, Brandon Wang (MIT)

• “Settling the Communication Complexity of VCG-based Mechanisms for All Approximation Guarantees,” Frederick Qiu, S. Matthew Weinberg (Princeton University)

• “Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model,” John Kallaugher, Ojas Parekh (Sandia National Laboratories); Nadezhda Voronova (Boston University)

• “An area law for the maximally-mixed ground state in arbitrarily degenerate systems with good AGSP,” Itai Arad (Centre for Quantum Technologies); Raz Firanko (Technion); Rahul Jain (National University of Singapore)

• “Agreement theorems for high dimensional expanders in the low acceptance regime: the role of covers,” Yotam Dikstein (Institute for Advanced Study); Irit Dinur (Weizmann Institute of Science)

• “Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time,” V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai Mathematical Institute, India); Abhranil Chatterjee (Indian Statistical Institute, Kolkata, India); Partha Mukhopadhyay (Chennai Mathematical Institute, India)

• “Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems,” Shuichi Hirahara (National Institute of Informatics); Naoto Ohsaka (CyberAgent, Inc.)

• “Cosystolic Expansion of Sheaves over Posets with Applications to Good 2-Queries LTCs and Lifted Codes,” Uriya A. First (University of Haifa); Tali Kaufman (Bar Ilan University)

• “Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L that Uses Properties of BPL,” Dean Doron (Ben Gurion University); Edward Pyne (MIT); Roei Tell (University of Toronto)

• “PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization,” Aris Filos-Ratsikas (University of Edinburgh); Kristoffer Arnsfelt Hansen, Kasper Hogh (Aarhus University); Alexandros Hollender (University of Oxford)

• “A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column,” Daniel Dadush, Zhuan Khye Koh (CWI Amsterdam); Bento Natura (Georgia Institute of Technology); Neil Olver, Laszlo A. Vegh (London School of Economics)

• “New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries,” Aditya Bhaskara (University of Utah); Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan (Northwestern University)

• “Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions,” Ronen Shaltiel (University of Haifa); Jad Silbak (Northeastern University)

• “Learning the coefficients: A presentable version of border complexity and applications to circuit factoring,” C. S. Bhargav, Prateek Dwivedi, Nitin Saxena (Department of Computer Science & Engg., Indian Institute of Technology Kanpur)

• “Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs,” Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane (University of California, San Diego); Vasilis Kontonis (University of Texas, Austin); Sihan Liu (University of California, San Diego); Nikos Zarifis (University of Wisconsin-Madison)
• “Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals,” Calum MacRury, Will Ma (Columbia University)
• “Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow,” Li Chen (Carnegie Mellon University); Rasmus Kyng (ETH Zurich); Yang P. Liu (Institute for Advanced Study); Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich)

Our prize for the shortest entries is shared by “0-1 Knapsack in Nearly Quadratic Time” by Ce Jin and “Self-Improvement for Circuit-Analysis Problems” by Ryan Williams, both of MIT. Maybe MIT and CMU and NYU etc. have unfair advantages for this prize. We have linked the paper “Calibrated Language Models Must Hallucinate” at a pertinent point in our previous post.

Open Problems

Here is an open problem: Will we ever get tired of looking at knapsack problems? Besides the paper by Ce Jin, there are “Knapsack with Small Items in Near-Quadratic Time” by Karl Bringmann and “A Nearly Quadratic-Time FPTAS for Knapsack” by Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang.

Hope you all enjoy the new results. Best to all.