| 2023 | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 |
| 2023 | A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford |
| 2023 | A New Approach to Post-Quantum Non-Malleability. Xiao Liang, Omkant Pandey, Takashi Yamakawa |
| 2023 | A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs. Ran Duan, Jiayi Mao, Xinkai Shu, Longhui Yin |
| 2023 | A d Hadley Black, Deeparnab Chakrabarty, C. Seshadhri |
| 2023 | A deterministic near-linear time approximation scheme for geometric transportation. Emily Fox, Jiashuai Lu |
| 2023 | A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels. Emmanuel Abbe, Colin Sandon |
| 2023 | A strong composition theorem for junta complexity and the boosting of property testers. Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan |
| 2023 | ABE for Circuits with poly (λ) -sized Keys from LWE. Valerio Cini, Hoeteck Wee |
| 2023 | Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography. Benny Applebaum, Oded Nir |
| 2023 | Agnostic proper learning of monotone functions: beyond the black-box correction barrier. Jane Lange, Arsen Vasilyan |
| 2023 | Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles. Guy Bresler, Chenghao Guo, Yury Polyanskiy |
| 2023 | All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time. Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak |
| 2023 | Approximating Edit Distance in the Fully Dynamic Model. Tomasz Kociumaka, Anish Mukherjee, Barna Saha |
| 2023 | Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices. Yao-Ching Hsieh, Huijia Lin, Ji Luo |
| 2023 | Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. He Jia, Pravesh K. Kothari, Santosh S. Vempala |
| 2023 | Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification. Anand Natarajan, Tina Zhang |
| 2023 | Bridge Girth: A Unifying Notion in Network Design. Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi |
| 2023 | Canonical decompositions of 3-connected graphs. Johannes Carmesin, Jan Kurkofka |
| 2023 | Certified Hardness vs. Randomness for Log-Space. Edward Pyne, Ran Raz, Wei Zhan |
| 2023 | Chasing Positive Bodies. Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak |
| 2023 | Clique Is Hard on Average for Unary Sherali-Adams. Susanna F. de Rezende, Aaron Potechin, Kilian Risse |
| 2023 | Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. Dominik Kempa, Tomasz Kociumaka |
| 2023 | Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer |
| 2023 | Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan |
| 2023 | Constant Approximation for Private Interdependent Valuations. Alon Eden, Michal Feldman, Kira Goldner, Simon Mauras, Divyarthi Mohan |
| 2023 | Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon. Reilly Browne, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, Valentin Polishchuk |
| 2023 | Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time. Neil Olver, Leon Sering, Laura Vargas Koch |
| 2023 | Covering Planar Metrics (and Beyond): O(1) Trees Suffice. Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than |
| 2023 | Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. Lijie Chen, Roei Tell, Ryan Williams |
| 2023 | Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn |
| 2023 | Deterministic Fully Dynamic SSSP and More. Jan van den Brand, Adam Karczmarz |
| 2023 | Directed Acyclic Outerplanar Graphs Have Constant Stack Number. Paul Jungeblut, Laura Merker, Torsten Ueckerdt |
| 2023 | Distribution of the threshold for the symmetric perceptron. Ashwin Sah, Mehtaab Sawhney |
| 2023 | Doubley-Efficient Interactive Proofs for Distribution Properties. Tal Herman, Guy N. Rothblum |
| 2023 | Dynamic "Succincter". Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou |
| 2023 | Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time. Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak |
| 2023 | Dynamic treewidth. Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski |
| 2023 | Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar |
| 2023 | Envy-Free Cake-Cutting for Four Agents. Alexandros Hollender, Aviad Rubinstein |
| 2023 | Explicit orthogonal and unitary designs. Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes |
| 2023 | Exponential quantum speedup in simulating coupled classical oscillators Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, Nathan Wiebe |
| 2023 | Extracting Randomness from Samplable Distributions, Revisited. Marshall Ball, Eli Goldin, Dana Dachman-Soled, Saachi Mutreja |
| 2023 | Fast Numerical Multivariate Multipoint Evaluation. Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi |
| 2023 | Faster Algorithms for Text-to-Pattern Hamming Distances. Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu |
| 2023 | Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques. Jan van den Brand, Daniel J. Zhang |
| 2023 | Faster Matrix Multiplication via Asymmetric Hashing. Ran Duan, Hongxun Wu, Renfei Zhou |
| 2023 | Faster high-accuracy log-concave sampling via algorithmic warm starts. Jason M. Altschuler, Sinho Chewi |
| 2023 | Flip-width: Cops and Robber on dense graphs. Szymon Torunczyk |
| 2023 | Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. Greg Bodwin, Gary Hoppenworth |
| 2023 | Fourier Growth of Communication Protocols for XOR Functions. Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu |
| 2023 | From Grassmannian to Simplicial High-Dimensional Expanders. Louis Golowich |
| 2023 | Generalizations of Matrix Multiplication can solve the Light Bulb Problem. Josh Alman, Hengjie Zhang |
| 2023 | Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes. Silas Richelson, Sourya Roy |
| 2023 | Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse |
| 2023 | HDX Condensers. Itay Cohen, Roy Roth, Amnon Ta-Shma |
| 2023 | Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman |
| 2023 | Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings. Sepehr Assadi, Janani Sundaresan |
| 2023 | IOPs with Inverse Polynomial Soundness Error. Gal Arnon, Alessandro Chiesa, Eylon Yogev |
| 2023 | Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding. Ariel Kulik, Matthias Mnich, Hadas Shachnai |
| 2023 | Improved Hardness of Approximating k-Clique under ETH. Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang |
| 2023 | Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy |
| 2023 | Interior-point methods on manifolds: theory and applications. Hiroshi Hirai, Harold Nieuwboer, Michael Walter |
| 2023 | Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement. Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass |
| 2023 | Krylov Methods are (nearly) Optimal for Low-Rank Approximation. Ainesh Bakshi, Shyam Narayanan |
| 2023 | Learning in Pessiland via Inductive Inference. Shuichi Hirahara, Mikito Nanashima |
| 2023 | Lipschitz Continuous Algorithms for Graph Problems. Soh Kumabe, Yuichi Yoshida |
| 2023 | List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani |
| 2023 | Local Computation Algorithms for Maximum Matching: New Lower Bounds. Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2023 | Locally Uniform Hashing. Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, Mikkel Thorup |
| 2023 | Matrix Completion in Almost-Verification Time. Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian |
| 2023 | Memory-Query Tradeoffs for Randomized Convex Optimization. Xi Chen, Binghui Peng |
| 2023 | Near Optimal Memory-Regret Tradeoff for Online Learning. Binghui Peng, Aviad Rubinstein |
| 2023 | Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! Karl Bringmann, Alejandro Cassis, Nick Fischer |
| 2023 | New Lower Bounds for Adaptive Tolerant Junta Testing. Xi Chen, Shyamal Patel |
| 2023 | On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. Suprovat Ghoshal, Euiwoong Lee |
| 2023 | On Pseudolinear Codes for Correcting Adversarial Errors. Eric Ruzomberka, Homa Nikbakht, Christopher G. Brinton, H. Vincent Poor |
| 2023 | On Symmetric Factorizations of Hankel Matrices. Mehrdad Ghadiri |
| 2023 | On small-depth Frege proofs for PHP. Johan Håstad |
| 2023 | One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree. Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D. Ellis Hershkowitz, Rajmohan Rajaraman |
| 2023 | Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity. Nick Gravin, Enze Sun, Zhihao Gavin Tang |
| 2023 | Optimal Algorithms for Bounded Weighted Edit Distance. Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz |
| 2023 | Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier. Hung Le, Shay Solomon, Cuong Than |
| 2023 | Optimal PAC Bounds without Uniform Convergence. Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy |
| 2023 | Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries. Dor Minzer, Kai Zhe Zheng |
| 2023 | Optimal mixing of the down-up walk on independent sets of a given size. Vishesh Jain, Marcus Michelen, Huy Tuan Pham, Thuy-Duong Vuong |
| 2023 | Parallel Repetition for the GHZ Game: Exponential Decay. Mark Braverman, Subhash Khot, Dor Minzer |
| 2023 | Parameterized Approximation Schemes for Clustering with General Norm Objectives. Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase |
| 2023 | Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). Michael Elkin, Idan Shabat |
| 2023 | Planar Disjoint Paths, Treewidth, and Kernels. Michal Wlodarczyk, Meirav Zehavi |
| 2023 | Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk |
| 2023 | Polynomial-Time Pseudodeterministic Construction of Primes. Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam |
| 2023 | Proof of the Clustered Hadwiger Conjecture. Vida Dujmovic, Louis Esperet, Pat Morin, David R. Wood |
| 2023 | Properly learning decision trees with queries is NP-hard. Caleb Koch, Carmen Strassle, Li-Yang Tan |
| 2023 | Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff |
| 2023 | Quartic Samples Suffice for Fourier Interpolation. Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang |
| 2023 | Query lower bounds for log-concave sampling. Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan |
| 2023 | Query-optimal estimation of unitary channels in diamond distance. Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang |
| 2023 | Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets. Zeyu Guo, Zihan Zhang |
| 2023 | ReSQueing Parallel and Private Stochastic Convex Optimization. Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian |
| 2023 | SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle. Rahul Ilango |
| 2023 | Sampling from the Potts model at low temperatures via Swendsen-Wang dynamics. Antonio Blanca, Reza Gheissari |
| 2023 | Secure Computation Meets Distributed Universal Optimality. Merav Parter |
| 2023 | Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form. Adam Karczmarz, Piotr Sankowski |
| 2023 | Separating MAX 2-AND, MAX DI-CUT and MAX CUT. Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick |
| 2023 | Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders. Yang Cai, Ziyun Chen, Jinzhao Wu |
| 2023 | Singular Value Approximation and Sparsifying Random Walks on Directed Graphs. AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan |
| 2023 | Slicing all Edges of an n-cube Requires n Ohad Klein |
| 2023 | Sparse Submodular Function Minimization. Andrei Graur, Haotian Jiang, Aaron Sidford |
| 2023 | Sparsifying Sums of Norms. Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford |
| 2023 | Stability and Replicability in Learning. Zachary Chase, Shay Moran, Amir Yehudayoff |
| 2023 | Streaming Euclidean k-median and k-means with o(log n) Space. Vincent Cohen-Addad, David P. Woodruff, Samson Zhou |
| 2023 | Streaming Lower Bounds and Asymmetric Set-Disjointness. Shachar Lovett, Jiapeng Zhang |
| 2023 | Strong Bounds for 3-Progressions. Zander Kelley, Raghu Meka |
| 2023 | Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications. Zongchen Chen, Kuikui Liu, Nitya Mani, Ankur Moitra |
| 2023 | Strongly History-Independent Storage Allocation: New Upper and Lower Bounds. William Kuszmaul |
| 2023 | Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. Alexandr Andoni, Hengjie Zhang |
| 2023 | Super-Logarithmic Lower Bounds for Dynamic Graph Problems. Kasper Green Larsen, Huacheng Yu |
| 2023 | Testing Graph Properties with the Container Method. Eric Blais, Cameron Seth |
| 2023 | The Bit Complexity of Efficient Continuous Optimization. Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala |
| 2023 | The Complexity of Dynamic Least-Squares Regression. Shunhua Jiang, Binghui Peng, Omri Weinstein |
| 2023 | The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan |
| 2023 | The Price of Explainability for Clustering. Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan |
| 2023 | The Subspace Flatness Conjecture and Faster Integer Programming. Victor Reis, Thomas Rothvoss |
| 2023 | The Vector Balancing Constant for Zonotopes. Rainie Bozzai, Victor Reis, Thomas Rothvoss |
| 2023 | The minimal canonical form of a tensor network. Arturo Acuaviva, Visu Makam, Harold Nieuwboer, David Pérez-García, Friedrich Sittner, Michael Walter, Freek Witteveen |
| 2023 | Thin Trees for Laminar Families. Nathan Klein, Neil Olver |
| 2023 | Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries. Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou |
| 2023 | Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting. Ofer Grossman, Meghal Gupta, Mark Sellke |
| 2023 | Tight Time-Space Lower Bounds for Constant-Pass Learning. Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang |
| 2023 | Top-Down Lower Bounds for Depth-Four Circuits. Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov |
| 2023 | Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition. Or Meir |
| 2023 | Towards Separating Computational and Statistical Differential Privacy. Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi |
| 2023 | Towards derandomising Markov chain Monte Carlo. Weiming Feng, Heng Guo, Chunyang Wang, Jiaheng Wang, Yitong Yin |
| 2023 | Traversing combinatorial 0/1-polytopes via optimization. Arturo Merino, Torsten Mütze |
| 2023 | Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. Vaggos Chatziafratis, Konstantin Makarychev |
| 2023 | Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More. Xin Li |
| 2023 | Uniqueness and Rapid Mixing in the Bipartite Hardcore Model (extended abstract). Xiaoyu Chen, Jingcheng Liu, Yitong Yin |
| 2023 | Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu |
| 2023 | When Does Adaptivity Help for Quantum State Learning? Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke |
| 2023 | Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms! Divesh Aggarwal, Rajendra Kumar |
| 2023 | Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence. Mohsen Ghaffari, Christoph Grunau, Václav Rozhon |
| 2023 | stateQIP = statePSPACE. Tony Metger, Henry Yuen |