- Zongchen Chen, Kuikui Liu, Nitya Mani, Ankur Moitra:
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications. FOCS 2023: 810-845 - Xi Chen, Binghui Peng:
Memory-Query Tradeoffs for Randomized Convex Optimization. FOCS 2023: 1400-1413 - Xi Chen, Shyamal Patel:
New Lower Bounds for Adaptive Tolerant Junta Testing. FOCS 2023: 1778-1786 - Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, Shyam Narayanan:
Query lower bounds for log-concave sampling. FOCS 2023: 2139-2148 - Valerio Cini, Hoeteck Wee:
ABE for Circuits with poly (λ) -sized Keys from LWE. FOCS 2023: 435-446 - Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman:
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. FOCS 2023: 1082-1104 - 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: 2262-2277 - Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. FOCS 2023: 1105-1130 - Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. FOCS 2023: 883-908 - 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: 1-11 - Ran Duan, Jiayi Mao, Xinkai Shu
, Longhui Yin:
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs. FOCS 2023: 484-492 - Ran Duan, Hongxun Wu, Renfei Zhou:
Faster Matrix Multiplication via Asymmetric Hashing. FOCS 2023: 2129-2138 - Vida Dujmovic, Louis Esperet, Pat Morin, David R. Wood:
Proof of the Clustered Hadwiger Conjecture. FOCS 2023: 1921-1930 - Alon Eden, Michal Feldman, Kira Goldner, Simon Mauras, Divyarthi Mohan:
Constant Approximation for Private Interdependent Valuations. FOCS 2023: 148-163 - Michael Elkin, Idan Shabat:
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). FOCS 2023: 2278-2311 - Emily Fox, Jiashuai Lu:
A deterministic near-linear time approximation scheme for geometric transportation. FOCS 2023: 1301-1315 - Mehrdad Ghadiri:
On Symmetric Factorizations of Hankel Matrices. FOCS 2023: 2081-2092 - Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala:
The Bit Complexity of Efficient Continuous Optimization. FOCS 2023: 2059-2070 - Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi:
Towards Separating Computational and Statistical Differential Privacy. FOCS 2023: 580-599 - Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi:
Fast Numerical Multivariate Multipoint Evaluation. FOCS 2023: 1426-1439 - Suprovat Ghoshal, Euiwoong Lee:
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. FOCS 2023: 26-36 - Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu:
Fourier Growth of Communication Protocols for XOR Functions. FOCS 2023: 721-732 - Louis Golowich:
From Grassmannian to Simplicial High-Dimensional Expanders. FOCS 2023: 1639-1648 - Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Top-Down Lower Bounds for Depth-Four Circuits. FOCS 2023: 1048-1055 - Andrei Graur, Haotian Jiang, Aaron Sidford:
Sparse Submodular Function Minimization. FOCS 2023: 2071-2080 - Nick Gravin, Enze Sun, Zhihao Gavin Tang:
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity. FOCS 2023: 1863-1876 - Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer:
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. FOCS 2023: 798-809 - Ofer Grossman, Meghal Gupta, Mark Sellke:
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting. FOCS 2023: 1496-1504 - Zeyu Guo, Zihan Zhang:
Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets. FOCS 2023: 164-176 - Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar:
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. FOCS 2023: 307-327