- Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass:
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement. FOCS 2023: 458-483 - Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Local Computation Algorithms for Maximum Matching: New Lower Bounds. FOCS 2023: 2322-2335 - Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, Mikkel Thorup:
Locally Uniform Hashing. FOCS 2023: 1440-1470 - Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak:
Chasing Positive Bodies. FOCS 2023: 1694-1714 - Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak:
Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time. FOCS 2023: 1563-1588 - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids. FOCS 2023: 1796-1821 - Eric Blais, Cameron Seth:
Testing Graph Properties with the Container Method. FOCS 2023: 1787-1795 - Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan:
A strong composition theorem for junta complexity and the boosting of property testers. FOCS 2023: 1757-1777 - Antonio Blanca, Reza Gheissari:
Sampling from the Potts model at low temperatures via Swendsen-Wang dynamics. FOCS 2023: 2006-2020 - Greg Bodwin, Gary Hoppenworth:
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. FOCS 2023: 701-720 - Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi:
Bridge Girth: A Unifying Notion in Network Design. FOCS 2023: 600-648 - Rainie Bozzai, Victor Reis, Thomas Rothvoss:
The Vector Balancing Constant for Zonotopes. FOCS 2023: 1292-1300 - Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS 2023: 234-252 - 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: 503-514 - Jan van den Brand, Adam Karczmarz:
Deterministic Fully Dynamic SSSP and More. FOCS 2023: 2312-2321 - Jan van den Brand, Daniel J. Zhang:
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques. FOCS 2023: 493-502 - Mark Braverman, Subhash Khot, Dor Minzer:
Parallel Repetition for the GHZ Game: Exponential Decay. FOCS 2023: 1337-1341 - Guy Bresler, Chenghao Guo, Yury Polyanskiy:
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles. FOCS 2023: 2149-2158 - Karl Bringmann, Alejandro Cassis, Nick Fischer:
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! FOCS 2023: 515-538 - Reilly Browne, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, Valentin Polishchuk:
Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon. FOCS 2023: 1357-1365 - Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D. Ellis Hershkowitz, Rajmohan Rajaraman:
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree. FOCS 2023: 60-76 - 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: 2159-2168 - Johannes Carmesin, Jan Kurkofka:
Canonical decompositions of 3-connected graphs. FOCS 2023: 1887-1920 - Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian:
ReSQueing Parallel and Private Stochastic Convex Optimization. FOCS 2023: 2031-2058 - Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz:
Optimal Algorithms for Bounded Weighted Edit Distance. FOCS 2023: 2177-2187 - Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu:
Faster Algorithms for Text-to-Pattern Hamming Distances. FOCS 2023: 2188-2203 - Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than:
Covering Planar Metrics (and Beyond): O(1) Trees Suffice. FOCS 2023: 2231-2261 - Vaggos Chatziafratis, Konstantin Makarychev:
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. FOCS 2023: 253-284 - Xiaoyu Chen, Jingcheng Liu, Yitong Yin:
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model (extended abstract). FOCS 2023: 1991-2005 - Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke:
When Does Adaptivity Help for Quantum State Learning? FOCS 2023: 391-404