FOCS

Publications

2023

Eric Blais, Cameron Seth
Testing Graph Properties with the Container Method. FOCS (2023)
Greg Bodwin, Gary Hoppenworth
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. FOCS (2023)
Vida Dujmovic, Louis Esperet, Pat Morin, David R. Wood
Proof of the Clustered Hadwiger Conjecture. FOCS (2023)
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski
Dynamic treewidth. FOCS (2023)
Mohsen Ghaffari, Christoph Grunau, Václav Rozhon
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence. FOCS (2023)
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase
Parameterized Approximation Schemes for Clustering with General Norm Objectives. FOCS (2023)
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. FOCS (2023)
Rainie Bozzai, Victor Reis, Thomas Rothvoss
The Vector Balancing Constant for Zonotopes. FOCS (2023)
Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time. FOCS (2023)
Tal Herman, Guy N. Rothblum
Doubley-Efficient Interactive Proofs for Distribution Properties. FOCS (2023)
Caleb Koch, Carmen Strassle, Li-Yang Tan
Properly learning decision trees with queries is NP-hard. FOCS (2023)
Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, Mikkel Thorup
Locally Uniform Hashing. FOCS (2023)
Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement. FOCS (2023)
Vishesh Jain, Marcus Michelen, Huy Tuan Pham, Thuy-Duong Vuong
Optimal mixing of the down-up walk on independent sets of a given size. FOCS (2023)
Szymon Torunczyk
Flip-width: Cops and Robber on dense graphs. FOCS (2023)
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. FOCS (2023)
Guy Bresler, Chenghao Guo, Yury Polyanskiy
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles. FOCS (2023)
Tony Metger, Henry Yuen
stateQIP = statePSPACE. FOCS (2023)
Alexandr Andoni, Hengjie Zhang
Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. FOCS (2023)
Shachar Lovett, Jiapeng Zhang
Streaming Lower Bounds and Asymmetric Set-Disjointness. FOCS (2023)
Ohad Klein
Hyperplanes. FOCS (2023)
Michael Elkin, Idan Shabat
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). FOCS (2023)
Gal Arnon, Alessandro Chiesa, Eylon Yogev
IOPs with Inverse Polynomial Soundness Error. FOCS (2023)
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs. FOCS (2023)
Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. FOCS (2023)
Antonio Blanca, Reza Gheissari
Sampling from the Potts model at low temperatures via Swendsen-Wang dynamics. FOCS (2023)
Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan
The Price of Explainability for Clustering. FOCS (2023)
Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, Shyam Narayanan
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. FOCS (2023)
Jan Van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. FOCS (2023)
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
Approximating Edit Distance in the Fully Dynamic Model. FOCS (2023)
Benny Applebaum, Oded Nir
Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography. FOCS (2023)
Edward Pyne, Ran Raz, Wei Zhan
Certified Hardness vs. Randomness for Log-Space. FOCS (2023)
Merav Parter
Secure Computation Meets Distributed Universal Optimality. FOCS (2023)
Nick Gravin, Enze Sun, Zhihao Gavin Tang
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity. FOCS (2023)
Sepehr Assadi, Janani Sundaresan
Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings. FOCS (2023)
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
Sparsifying Sums of Norms. FOCS (2023)
Silas Richelson, Sourya Roy
Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes. FOCS (2023)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS (2023)
Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang
Improved Hardness of Approximating k-Clique under ETH. FOCS (2023)
Hung Le, Shay Solomon, Cuong Than
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier. FOCS (2023)
Louis Golowich
From Grassmannian to Simplicial High-Dimensional Expanders. FOCS (2023)
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time. FOCS (2023)
Jan van den Brand, Daniel J. Zhang
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques. FOCS (2023)
Dor Minzer, Kai Zhe Zheng
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries. FOCS (2023)
Neil Olver, Leon Sering, Laura Vargas Koch
Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time. FOCS (2023)
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. FOCS (2023)
Vaggos Chatziafratis, Konstantin Makarychev
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. FOCS (2023)
Binghui Peng, Aviad Rubinstein
Near Optimal Memory-Regret Tradeoff for Online Learning. FOCS (2023)
Soh Kumabe, Yuichi Yoshida
Lipschitz Continuous Algorithms for Graph Problems. FOCS (2023)
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. FOCS (2023)