- 2023
- Weiming Feng, Heng Guo, Chunyang Wang, Jiaheng Wang, Yitong Yin:
Towards derandomising Markov chain Monte Carlo. FOCS 2023: 1963-1990 - Yang Cai, Ziyun Chen, Jinzhao Wu:
Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders. FOCS 2023: 134-147 - Mohsen Ghaffari, Christoph Grunau, Václav Rozhon:
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence. FOCS 2023: 1551-1562 - Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu:
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. FOCS 2023: 1224-1239 - Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren
, Rahul Santhanam:
Polynomial-Time Pseudodeterministic Construction of Primes. FOCS 2023: 1261-1270 - Zachary Chase, Shay Moran, Amir Yehudayoff:
Stability and Replicability in Learning. FOCS 2023: 2430-2439 - Hiroshi Hirai, Harold Nieuwboer, Michael Walter:
Interior-point methods on manifolds: theory and applications. FOCS 2023: 2021-2030 - Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan:
The Price of Explainability for Clustering. FOCS 2023: 1131-1148 - Lijie Chen, Roei Tell, Ryan Williams
:
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. FOCS 2023: 1008-1047 - Michal Wlodarczyk, Meirav Zehavi:
Planar Disjoint Paths, Treewidth, and Kernels. FOCS 2023: 649-662 - Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang:
Quartic Samples Suffice for Fourier Interpolation. FOCS 2023: 1414-1425 - Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang:
Tight Time-Space Lower Bounds for Constant-Pass Learning. FOCS 2023: 1195-1202 - Itay Cohen, Roy Roth, Amnon Ta-Shma:
HDX Condensers. FOCS 2023: 1649-1664 - Xiao Liang, Omkant Pandey, Takashi Yamakawa:
A New Approach to Post-Quantum Non-Malleability. FOCS 2023: 568-579 - 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: 1377-1399 - Emmanuel Abbe, Colin Sandon:
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels. FOCS 2023: 177-193 - 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: 2204-2212 - Arturo Acuaviva, Visu Makam, Harold Nieuwboer, David Pérez-García, Friedrich Sittner, Michael Walter, Freek Witteveen:
The minimal canonical form of a tensor network. FOCS 2023: 328-362 - Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy:
Optimal PAC Bounds without Uniform Convergence. FOCS 2023: 1203-1223 - Divesh Aggarwal, Rajendra Kumar:
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms! FOCS 2023: 2213-2230 - AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan:
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs. FOCS 2023: 846-854 - Josh Alman, Hengjie Zhang:
Generalizations of Matrix Multiplication can solve the Light Bulb Problem. FOCS 2023: 1471-1495 - Jason M. Altschuler, Sinho Chewi:
Faster high-accuracy log-concave sampling via algorithmic warm starts. FOCS 2023: 2169-2176 - Alexandr Andoni, Hengjie Zhang:
Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. FOCS 2023: 98-112 - Benny Applebaum, Oded Nir:
Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography. FOCS 2023: 539-555 - Gal Arnon, Alessandro Chiesa, Eylon Yogev:
IOPs with Inverse Polynomial Soundness Error. FOCS 2023: 752-761 - Sepehr Assadi, Janani Sundaresan:
Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings. FOCS 2023: 909-932 - Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, Nathan Wiebe:
Exponential quantum speedup in simulating coupled classical oscillators*. FOCS 2023: 405-414 - Ainesh Bakshi, Shyam Narayanan:
Krylov Methods are (nearly) Optimal for Low-Rank Approximation. FOCS 2023: 2093-2101 - Marshall Ball
, Eli Goldin, Dana Dachman-Soled, Saachi Mutreja:
Extracting Randomness from Samplable Distributions, Revisited. FOCS 2023: 1505-1514