| 2024 | 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 |
| 2024 | A Computational Test of Contextuality and, Even Simpler Proofs of Quantumness. Atul Singh Arora, Kishor Bharti, Alexandru Cojocaru, Andrea Coladangelo |
| 2024 | A Dense Model Theorem for the Boolean Slice. Gil Kalai, Noam Lifshitz, Dor Minzer, Tamar Ziegler |
| 2024 | A Lossless Deamortization for Dynamic Greedy Set Cover. Shay Solomon, Amitai Uzrad, Tianyi Zhang |
| 2024 | A Sampling Lovász Local Lemma for Large Domain Sizes. Chunyang Wang, Yitong Yin |
| 2024 | A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou |
| 2024 | A Stronger Bound for Linear 3-LCC. Tal Yankovitz |
| 2024 | Agnostically Learning Multi-Index Models with Queries. Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis |
| 2024 | Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality. Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva |
| 2024 | An Improved Line-Point Low-Degree Test. Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan |
| 2024 | An Improved Pseudopolynomial Time Algorithm for Subset Sum. Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang |
| 2024 | An Optimal Algorithm for Sorting Pattern-Avoiding Sequences. Michal Opler |
| 2024 | An XOR Lemma for Deterministic Communication Complexity. Siddharth Iyer, Anup Rao |
| 2024 | Approximation Algorithms for Noncommutative CSPs. Eric Culf, Hamoon Mousavi, Taro Spirig |
| 2024 | Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer. Yaonan Jin, Pinyan Lu |
| 2024 | Boosting Uniformity in Quasirandom Groups: Fast and Simple. Harm Derksen, Chin Ho Lee, Emanuele Viola |
| 2024 | Canonical Forms for Matrix Tuples in Polynomial Time. Youming Qiao, Xiaorui Sun |
| 2024 | Capacity Threshold for the Ising Perceptron. Brice Huang |
| 2024 | Certifying Almost All Quantum States with Few Single-Qubit Measurements. Hsin-Yuan Huang, John Preskill, Mehdi Soleimanifar |
| 2024 | Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra |
| 2024 | Chernoff Bounds and Reverse Hypercontractivity on HDX. Yotam Dikstein, Max Hopkins |
| 2024 | Commitments are Equivalent to Statistically-Verifiable One-Way State Generators. Rishabh Batra, Rahul Jain |
| 2024 | Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier. Shiri Ron, Clayton Thomas, S. Matthew Weinberg, Qianfan Zhang |
| 2024 | Computational Dynamical Systems. Jordan Cotler, Semon Rezchikov |
| 2024 | Computational Hardness of Detecting Graph Lifts and Certifying Lift-Monotone Properties of Random Regular Graphs. Dmitriy Kunisky, Xifan Yu |
| 2024 | Computing Approximate Centerpoints in Polynomial Time. Yeshwanth Cherapanamjeri |
| 2024 | Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time. Loukas Georgiadis, Giuseppe F. Italiano, Evangelos Kosinas |
| 2024 | Constant Degree Direct Product Testers with Small Soundness. Mitali Bafna, Noam Lifshitz, Dor Minzer |
| 2024 | Constant-Depth Arithmetic Circuits for Linear Algebra Problems. Robert Andrews, Avi Wigderson |
| 2024 | Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem. Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani, Irene Muzi |
| 2024 | Decoding Quasi-Cyclic Quantum LDPC Codes. Louis Golowich, Venkatesan Guruswami |
| 2024 | Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint. Niv Buchbinder, Moran Feldman |
| 2024 | Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach. Renato Ferreira Pinto Jr. |
| 2024 | Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. Jiatu Li, Edward Pyne, Roei Tell |
| 2024 | Dot-Product Proofs and Their Applications. Nir Bitansky, Prahladh Harsha, Yuval Ishai, Ron D. Rothblum, David J. Wu |
| 2024 | Dynamic Deterministic Constant-Approximate Distance Oracles with n Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak |
| 2024 | Efficient Approximate Unitary Designs from Random Pauli Rotations. Jeongwan Haah, Yunchao Liu, Xinyu Tan |
| 2024 | Efficient Approximation of Fractional Hypertree Width. Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan, Jie Xue |
| 2024 | Efficient Certificates of Anti-Concentration Beyond Gaussians. Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan |
| 2024 | Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians. Jane H. Lee, Anay Mehrotra, Manolis Zampetakis |
| 2024 | Efficient Unitary Designs from Random Sums and Permutations. Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Fernando G. S. L. Brandão, Patrick Hayden |
| 2024 | Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy. Krishnamurthy Dj Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, Abhradeep Thakurta |
| 2024 | Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes. Irit Dinur, Ting-Chun Lin, Thomas Vidick |
| 2024 | Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning. Noah Golowich, Ankur Moitra, Dhruv Rohatgi |
| 2024 | Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. Pravesh K. Kothari, Peter Manohar |
| 2024 | Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems. Caleb Koch, Carmen Strassle, Li-Yang Tan |
| 2024 | Fast List Decoding of Univariate Multiplicity and Folded Reed-Solomon Codes. Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar |
| 2024 | Fast Mixing in Sparse Random Ising Models. Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, David X. Wu |
| 2024 | Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier. Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang |
| 2024 | Faster Isomorphism Testing of p-Groups of Frattini Class 2. Gábor Ivanyos, Euan J. Mendoza, Youming Qiao, Xiaorui Sun, Chuanqi Zhang |
| 2024 | First-Order Model Checking on Monadically Stable Graph Classes. Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, Szymon Torunczyk |
| 2024 | Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs. Soheil Behnezhad, Alma Ghafari |
| 2024 | Fully Dynamic k-Clustering with Fast Update Time and Small Recourse. Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis |
| 2024 | Gapped Clique Homology on Weighted Graphs is QMA1-Hard and Contained in QMA. Robbie King, Tamara Kohler |
| 2024 | Gaussian Approximation of Convex Sets by Intersections of Halfspaces. Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2024 | Gradient Descent for Unbounded Convex Functions on Hadamard Manifolds and its Applications to Scaling Problems. Hiroshi Hirai, Keiya Sakabe |
| 2024 | Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems. Moïse Blanchard |
| 2024 | Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi |
| 2024 | Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares. Mikkel Abrahamsen, Jack Stade |
| 2024 | High-Temperature Gibbs States are Unentangled and Efficiently Preparable. Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang |
| 2024 | How to Simulate Random Oracles with Auxiliary Input. Yevgeniy Dodis, Aayush Jain, Huijia Lin, Ji Luo, Daniel Wichs |
| 2024 | Improved Condensers for Chor-Goldreich Sources. Jesse Goodman, Xin Li, David Zuckerman |
| 2024 | Improved Distance (Sensitivity) Oracles with Subquadratic Space. Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck |
| 2024 | Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation. Shyam Narayanan, Václav Rozhon, Jakub Tetek, Mikkel Thorup |
| 2024 | Interactive Proofs for General Distribution Properties. Tal Herman, Guy N. Rothblum |
| 2024 | Jump Operators, Interactive Proofs and Proof Complexity Generators. Erfan Khaniki |
| 2024 | Lempel-Ziv (LZ77) Factorization in Sublinear Time. Dominik Kempa, Tomasz Kociumaka |
| 2024 | Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains. Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, David X. Wu |
| 2024 | Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. Yotam Dikstein, Irit Dinur, Alexander Lubotzky |
| 2024 | Maximum Flow by Augmenting Paths in n Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu |
| 2024 | Minor Containment and Disjoint Paths in Almost-Linear Time. Tuukka Korhonen, Michal Pilipczuk, Giannos Stamoulis |
| 2024 | Naively Sorting Evolving Data is Optimal and Robust. George Giakkoupis, Marcos Kiwi, Dimitrios Los |
| 2024 | Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs. Arnold Filtser, Gramoz Goranci, Neel Patel, Maximilian Probst Gutenberg |
| 2024 | Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS. Mohsen Ghaffari, Christoph Grunau |
| 2024 | Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. Sanjeev Khanna, Aaron Putterman, Madhu Sudan |
| 2024 | Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. Omar Alrabiah, Venkatesan Guruswami |
| 2024 | Nearly Optimal List Labeling. Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks |
| 2024 | New Structures and Algorithms for Length-Constrained Expander Decompositions. Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan |
| 2024 | Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications. Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav |
| 2024 | O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold. Tolson Bell, Alan M. Frieze |
| 2024 | Obstructions to Erdös-Pósa Dualities for Minors. Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht |
| 2024 | On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication. Yang P. Liu |
| 2024 | On Approximating Cutwidth and Pathwidth. Nikhil Bansal, Dor Katzelnick, Roy Schwartz |
| 2024 | On Pigeonhole Principles and Ramsey in TFNP. Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun |
| 2024 | On Robustness to k-Wise Independence of Optimal Bayesian Mechanisms. Nick Gravin, Zhiqi Wang |
| 2024 | On the Complexity of Avoiding Heavy Elements. Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam |
| 2024 | On the Existence of Seedless Condensers: Exploring the Terrain. Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach |
| 2024 | Online Combinatorial Allocations and Auctions with Few Samples. Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla |
| 2024 | Optimal Bounds for Open Addressing Without Reordering. Martín Farach-Colton, Andrew Krapivin, William Kuszmaul |
| 2024 | Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima |
| 2024 | Optimal Quantile Estimation: Beyond the Comparison Model. Meghal Gupta, Mihir Singhal, Hongxun Wu |
| 2024 | Optimal Tradeoffs for Estimating Pauli Observables. Sitan Chen, Weiyuan Gong, Qi Ye |
| 2024 | Polynomial Calculus Sizes Over the Boolean and Fourier Bases are Incomparable. Sasank Mouli |
| 2024 | Power Series Composition in Near-Linear Time. Yasunori Kinoshita, Baitian Li |
| 2024 | Predict to Minimize Swap Regret for All Payoff-Bounded Tasks. Lunjia Hu, Yifan Wu |
| 2024 | Proofs of Space with Maximal Hardness. Leonid Reyzin |
| 2024 | Quantum Computational Advantage with Constant-Temperature Gibbs Sampling. Thiago Bergamaschi, Chi-Fang Chen, Yunchao Liu |
| 2024 | Quantum Eigenvalue Processing. Guang Hao Low, Yuan Su |
| 2024 | Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem. Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari |
| 2024 | Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric. Zeyu Guo, Chaoping Xing, Chen Yuan, Zihan Zhang |
| 2024 | Replicability in High Dimensional Statistics. Max Hopkins, Russell Impagliazzo, Daniel M. Kane, Sihan Liu, Christopher Ye |
| 2024 | Reverse Mathematics of Complexity Lower Bounds. Lijie Chen, Jiatu Li, Igor C. Oliveira |
| 2024 | Revisiting Agnostic PAC Learning. Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy |
| 2024 | Sampling, Counting, and Large Deviations for Triangle-Free Graphs Near the Critical Density. Matthew Jenssen, Will Perkins, Aditya Potukuchi, Michael Simkin |
| 2024 | Semi-Bandit Learning for Monotone Stochastic Optimization. Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan |
| 2024 | Semirandom Planted Clique and the Restricted Isometry Property. Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer |
| 2024 | Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn |
| 2024 | Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems. Friedrich Eisenbrand, Lars Rohwedder, Karol Wegrzycki |
| 2024 | Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries. Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen |
| 2024 | Sparse Graph Counting and Kelley-Meka Bounds for Binary Systems. Yuval Filmus, Hamed Hatami, Kaave Hosseini, Esty Kelman |
| 2024 | Spectral Guarantees for Adversarial Streaming PCA. Eric Price, Zhiyang Xun |
| 2024 | Stochastic Online Correlated Selection. Ziyun Chen, Zhiyi Huang, Enze Sun |
| 2024 | Strong vs. Weak Range Avoidance and the Linear Ordering Principle. Oliver Korten, Toniann Pitassi |
| 2024 | Structure Learning of Hamiltonians from Real-Time Evolution. Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang |
| 2024 | Succinct Arguments for QMA from Standard Assumptions via Compiled Nonlocal Games. Tony Metger, Anand Natarajan, Tina Zhang |
| 2024 | Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis. Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, Aaron Potechin |
| 2024 | Tensor Cumulants for Statistical Inference on Invariant Distributions. Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein |
| 2024 | The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller Than 2. Jaroslaw Byrka, Fabrizio Grandoni, Vera Traub |
| 2024 | The Communication Complexity of Approximating Matrix Rank. Alexander A. Sherstov, Andrey A. Storozhenko |
| 2024 | The ESPRIT Algorithm Under High Noise: Optimal Error Scaling and Noisy Super-Resolution. Zhiyan Ding, Ethan N. Epperly, Lin Lin, Ruizhe Zhang |
| 2024 | The Online Submodular Assignment Problem. Daniel Hathcock, Billy Jin, Kalen Patton, Sherry Sarkar, Michael Zlatin |
| 2024 | The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. Ryan Williams |
| 2024 | The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem. Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan |
| 2024 | The Tractability Border of Reachability in Simple Vector Addition Systems with States. Dmitry Chistikov, Wojciech Czerwinski, Filip Mazowiecki, Lukasz Orlikowski, Henry Sinclair-Banks, Karol Wegrzycki |
| 2024 | Three-Edge-Coloring Projective Planar Cubic Graphs: A Generalization of the Four Color Theorem. Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe |
| 2024 | Tight Analyses of Ordered and Unordered Linear Probing. Mark Braverman, William Kuszmaul |
| 2024 | Tight Bounds for Classical Open Addressing. Michael A. Bender, William Kuszmaul, Renfei Zhou |
| 2024 | Tight Bounds for Sorting Under Partial Information. Ivor van der Hoog, Daniel Rutschmann |
| 2024 | Tight Bounds for the Zig-Zag Product. Gil Cohen, Itay Cohen, Gal Maor |
| 2024 | Towards Instance-Optimal Euclidean Spanners. Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang |
| 2024 | Trading Determinism for Noncommutativity in Edmonds' Problem. Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay |
| 2024 | Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps. Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek |
| 2024 | Verifying Groups in Linear Time. Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski |
| 2024 | ∏ Dmitriy Zhuk |