- Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang:
Query-optimal estimation of unitary channels in diamond distance. FOCS 2023: 363-390 - Johan Håstad:
On small-depth Frege proofs for PHP. FOCS 2023: 37-49 - Tal Herman, Guy N. Rothblum:
Doubley-Efficient Interactive Proofs for Distribution Properties. FOCS 2023: 743-751 - Shuichi Hirahara, Mikito Nanashima:
Learning in Pessiland via Inductive Inference. FOCS 2023: 447-457 - Alexandros Hollender, Aviad Rubinstein:
Envy-Free Cake-Cutting for Four Agents. FOCS 2023: 113-122 - Yao-Ching Hsieh, Huijia Lin, Ji Luo
:
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices. FOCS 2023: 415-434 - Rahul Ilango:
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle. FOCS 2023: 733-742 - 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: 1665-1681 - Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford:
Sparsifying Sums of Norms. FOCS 2023: 1953-1962 - Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani:
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. FOCS 2023: 1682-1693 - He Jia, Pravesh K. Kothari, Santosh S. Vempala:
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. FOCS 2023: 2408-2429 - Shunhua Jiang, Binghui Peng, Omri Weinstein:
The Complexity of Dynamic Least-Squares Regression. FOCS 2023: 1605-1627 - Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan:
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. FOCS 2023: 1316-1336 - Paul Jungeblut
, Laura Merker, Torsten Ueckerdt:
Directed Acyclic Outerplanar Graphs Have Constant Stack Number. FOCS 2023: 1937-1952 - Praneeth Kacham, Rasmus Pagh, Mikkel Thorup
, David P. Woodruff:
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. FOCS 2023: 1515-1550 - Adam Karczmarz, Piotr Sankowski:
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form. FOCS 2023: 1745-1756 - Zander Kelley, Raghu Meka:
Strong Bounds for 3-Progressions. FOCS 2023: 933-973 - Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian:
Matrix Completion in Almost-Verification Time. FOCS 2023: 2102-2128 - Dominik Kempa, Tomasz Kociumaka:
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. FOCS 2023: 1877-1886 - Ohad Klein:
Slicing all Edges of an n-cube Requires n2/3 Hyperplanes. FOCS 2023: 1931-1936 - Nathan Klein, Neil Olver:
Thin Trees for Laminar Families. FOCS 2023: 50-59 - Caleb Koch, Carmen Strassle, Li-Yang Tan:
Properly learning decision trees with queries is NP-hard. FOCS 2023: 2383-2407 - Tomasz Kociumaka, Anish Mukherjee, Barna Saha:
Approximating Edit Distance in the Fully Dynamic Model. FOCS 2023: 1628-1638 - Tuukka Korhonen
, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski:
Dynamic treewidth. FOCS 2023: 1734-1744 - Ariel Kulik, Matthias Mnich, Hadas Shachnai:
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding. FOCS 2023: 1366-1376 - Soh Kumabe, Yuichi Yoshida:
Lipschitz Continuous Algorithms for Graph Problems. FOCS 2023: 762-797 - William Kuszmaul:
Strongly History-Independent Storage Allocation: New Upper and Lower Bounds. FOCS 2023: 1822-1841 - Jane Lange, Arsen Vasilyan:
Agnostic proper learning of monotone functions: beyond the black-box correction barrier. FOCS 2023: 1149-1170 - Kasper Green Larsen, Huacheng Yu:
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. FOCS 2023: 1589-1604 - Hung Le, Shay Solomon, Cuong Than:
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier. FOCS 2023: 77-97