{"id":1479,"date":"2023-07-25T21:50:22","date_gmt":"2023-07-25T21:50:22","guid":{"rendered":"https:\/\/focs.computer.org\/2023\/?page_id=1479"},"modified":"2023-12-10T20:31:21","modified_gmt":"2023-12-10T20:31:21","slug":"focs-2023-list-of-accepted-papers","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2023\/focs-2023-list-of-accepted-papers\/","title":{"rendered":"FOCS 2023 List of Accepted Papers"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

FOCS Accepted Papers<\/h1><\/a><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\r\n\r\n \r\n
Accepted Paper<\/strong><\/td> Authors<\/strong><\/td>\r\n <\/tr>\r\n
Parallel Repetition for the GHZ Game: Exponential Decay<\/td> Mark Braverman (Princeton University); Subhash Khot (NYU); Dor Minzer (MIT)<\/td>\r\n <\/tr>\r\n
Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets<\/td> Zeyu Guo and Zihan Zhang (The Ohio State University)<\/td>\r\n <\/tr>\r\n
Streaming Lower Bounds and Asymmetric Set-Disjointness<\/td> Shachar Lovett (UC San Diego); Jiapeng Zhang (University of Southern California)<\/td>\r\n <\/tr>\r\n
Traversing combinatorial 0\/1-polytopes via optimization<\/td> Arturo Merino (TU Berlin); Torsten Mutze (University of Warwick)<\/td>\r\n <\/tr>\r\n
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries<\/td> Dor Minzer and Kai Zhe Zheng (MIT)<\/td>\r\n <\/tr>\r\n
Strongly History Independent Storage Allocation: New Upper and Lower bounds<\/td> William Kuszmaul (MIT)<\/td>\r\n <\/tr>\r\n
Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon<\/a><\/td> Reilly Browne (Department of Computer Science, Stony Brook University); Prahlad Narasimham Kasthurirangan and Joseph S. B. Mitchell (Stony Brook University); Valentin Polishchuk (Linköping University, Sweden)<\/td>\r\n <\/tr>\r\n
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs<\/td> Ran Duan and Jiayi Mao (Tsinghua University); Xinkai Shu (The University of Hong Kong); Longhui Yin (Tsinghua University)<\/td>\r\n <\/tr>\r\n
Directed Acyclic Outerplanar Graphs Have Constant Stack Number<\/td> Paul Jungeblut, Laura Merker, and Torsten Ueckerdt (Karlsruhe Institute of Technology)<\/td>\r\n <\/tr>\r\n
Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification<\/td> Anand Natarajan and Tina Zhang (MIT)<\/td>\r\n <\/tr>\r\n
Distribution of the threshold for the symmetric perceptron<\/td> Mehtaab Sawhney and Ashwin Sah (MIT)<\/td>\r\n <\/tr>\r\n
Faster high-accuracy log-concave sampling via algorithmic warm starts<\/td> Jason M. Altschuler (New York University); Sinho Chewi (Massachusetts Institute of Technology)<\/td>\r\n <\/tr>\r\n
Separating MAX 2-AND, MAX DI-CUT and MAX CUT<\/td> Joshua Brakensiek (Stanford University); Neng Huang and Aaron Potechin (University of Chicago); Uri Zwick (Tel Aviv University)<\/td>\r\n <\/tr>\r\n
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications<\/td> Zongchen Chen, Kuikui Liu, and Nitya Mani (MIT); Ankur Moitra (Math & CSAIL, MIT)<\/td>\r\n <\/tr>\r\n
Slicing all Edges of an $n$-cube Requires $n^{2\/3}$ Hyperplanes<\/td> Ohad Klein (Hebrew University)<\/td>\r\n <\/tr>\r\n
A $d^{1\/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids<\/td> Hadley Black (University of California, Los Angeles); Deeparnab Chakrabarty (Dartmouth College); C. Seshadhri (University of California, Santa Cruz)<\/td>\r\n <\/tr>\r\n
On small-depth Frege proofs for PHP<\/td> Johan Håstad (KTH Royal Institute of Technology, Stockholm)<\/td>\r\n <\/tr>\r\n
Fast Numerical Multivariate Multipoint Evaluation<\/td> Sumanta Ghosh (Caltech); Prahladh Harsha (TIFR); Simao Herdade (Yahoo Research); Mrinal Kumar and Ramprasad Saptharishi (TIFR)<\/td>\r\n <\/tr>\r\n
Towards derandomising Markov chain Monte Carlo<\/a><\/td> Weiming Feng and Heng Guo (University of Edinburgh); Chunyang Wang (Nanjing University); Jiaheng Wang (University of Edinburgh); Yitong Yin (Nanjing University)<\/td>\r\n <\/tr>\r\n
Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time<\/td> Sayan Bhattacharya and Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan)<\/td>\r\n <\/tr>\r\n
Parameterized Approximation Schemes for Clustering with General Norm Objectives<\/td> Fateme Abbasi, Sandip Banerjee, and Jaroslaw Byrka (University of Wroc≈\u00c7aw, Poland); Parinya Chalermsook and Ameet Gadekar (Aalto University, Espoo, Finland); Kamyar Khodamoradi (University of British Columbia); Daniel Marx (CISPA Helmholtz Center for Information Security, Saarbrucken, Germany); Roohani Sharma (Max Planck Institute for Informatics, Saarbrucken, Germany); Joachim Spoerhase (University of Sheffield, United Kingdom)<\/td>\r\n <\/tr>\r\n
Sparsifying Sums of Norms<\/td> Arun Jambulapati and James R. Lee (University of Washington); Yang P. Liu and Aaron Sidford (Stanford University)<\/td>\r\n <\/tr>\r\n
stateQIP = statePSPACE<\/td> Tony Metger (ETH Zurich); Henry Yuen (Columbia University)<\/td>\r\n <\/tr>\r\n
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant<\/td> Vaggos Chatziafratis (UC Santa Cruz); Konstantin Makarychev (Northwestern University)<\/td>\r\n <\/tr>\r\n
Constant Approximation for Private Interdependent Valuations<\/td> Alon Eden (The Hebrew University of Jerusalem); Michal Feldman (Tel Aviv University); Kira Goldner (Boston University); Simon Mauras and Divyarthi Mohan (Tel Aviv University)<\/td>\r\n <\/tr>\r\n
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More<\/td> Xin Li (Johns Hopkins University)<\/td>\r\n <\/tr>\r\n
Agnostic proper learning of monotone functions: beyond black-box correction barrier<\/td> Jane Lange and Arsen Vasilyan (MIT)<\/td>\r\n <\/tr>\r\n
Quartic Samples Suffice for Fourier Interpolation<\/td> Zhao Song (Adobe Research); Baocheng Sun (Weizmann Institute of Science); Omri Weinstein (The Hebrew University and Columbia University.); Ruizhe Zhang (The University of Texas at Austin)<\/td>\r\n <\/tr>\r\n
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time<\/td> Amir Abboud (Weizmann Institute of Science); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (University of Michigan)<\/td>\r\n <\/tr>\r\n
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries<\/td> Tianxiao Li and Jingxun Liang (IIIS, Tsinghua University); Huacheng Yu (Princeton University); Renfei Zhou (IIIS, Tsinghua University)<\/td>\r\n <\/tr>\r\n
Thin trees for laminar families<\/td> Nathan Klein (University of Washington); Neil Olver (London School of Economics and Political Science)<\/td>\r\n <\/tr>\r\n
Extracting Randomness from Samplable Distributions, Revisited<\/td> Marshall Ball (NYU); Dana Dachman-Soled (University of Maryland, College Park); Eli Goldin (NYU); Saachi Mutreja (University Of California, Berkeley)<\/td>\r\n <\/tr>\r\n
From Grassmannian to Simplicial High-Dimensional Expanders<\/td> Louis Golowich (UC Berkeley)<\/td>\r\n <\/tr>\r\n
Super-Logarithmic Lower Bounds for Dynamic Graph Problems<\/td> Kasper Green Larsen (Aarhus University); Huacheng Yu (Princeton University)<\/td>\r\n <\/tr>\r\n
Certified Hardness vs. Randomness for Log-Space<\/td> Edward Pyne (MIT); Ran Raz and Wei Zhan (Princeton)<\/td>\r\n <\/tr>\r\n
A deterministic near-linear time approximation scheme for geometric transportation<\/a><\/td> Emily Fox and Jiashuai Lu (The University of Texas at Dallas)<\/td>\r\n <\/tr>\r\n
Lipschitz Continuous Algorithms for Graph Problems<\/td> Soh Kumabe (The University of Tokyo); Yuichi Yoshida (National Institute of Informatics)<\/td>\r\n <\/tr>\r\n
The Vector Balancing Constant for Zonotopes<\/a><\/td> Rainie Bozzai, Victor Reis, and Thomas Rothvoss (University of Washington)<\/td>\r\n <\/tr>\r\n
The Complexity of Dynamic Least-Squares Regression<\/td> Shunhua Jiang, Binghui Peng, and Omri Weinstein (Columbia University)<\/td>\r\n <\/tr>\r\n
The Subspace Flatness Conjecture and Faster Integer Programming<\/td> Victor Reis and Thomas Rothvoss (University of Washington)<\/td>\r\n <\/tr>\r\n
Improved Hardness of Approximating k-Clique under ETH<\/td> Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Xiuhan Wang (Tsinghua University)<\/td>\r\n <\/tr>\r\n
Explicit orthogonal and unitary designs<\/td> Ryan O'Donnell (Carnegie Mellon University); Rocco A. Servedio (Columbia University); Pedro Paredes (Princeton University)<\/td>\r\n <\/tr>\r\n
Canonical decompositions of 3-connected graphs<\/td> Johannes Carmesin and Jan Kurkofka (University of Birmingham)<\/td>\r\n <\/tr>\r\n
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model<\/td> Xiaoyu Chen, Jingcheng Liu, and Yitong Yin (Nanjing University)<\/td>\r\n <\/tr>\r\n
HDX Condensers<\/td> Itay Cohen, Roy Roth, and Amnon Ta-Shma (Tel Aviv University)<\/td>\r\n <\/tr>\r\n
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold<\/td> Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh, Pravesh K. Kothari, and Peter Manohar (Carnegie Mellon University)<\/td>\r\n <\/tr>\r\n
Chasing Positive Bodies<\/td> Sayan Bhattacharya (University of Warwick); Niv Buchbinder and Roie Levin (Tel Aviv University); Thatchaphol Saranurak (University of Michigan)<\/td>\r\n <\/tr>\r\n
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1<\/td> Vincent Cohen-Addad (Google Research, France); Hung Le (University of Massachusetts); Marcin Pilipczuk (University of Warsaw and IT University of Copenhagen); Michał Pilipczuk (University of Warsaw)<\/td>\r\n <\/tr>\r\n
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering<\/td> Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (University at Buffalo); Alantha Newman (Universit√\u00a9 Grenoble Alpes)<\/td>\r\n <\/tr>\r\n
Approximating Edit Distance in the Fully Dynamic Model<\/td> Tomasz Kociumaka (Max Planck Institute for Informatics); Anish Mukherjee (University of Warwick); Barna Saha (University of California San Diego)<\/td>\r\n <\/tr>\r\n
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques<\/td> Jan van den Brand and Daniel Zhang (Georgia Institute of Technology)<\/td>\r\n <\/tr>\r\n
Generalizations of Matrix Multiplication can solve the Light Bulb Problem<\/td> Josh Alman and Hengjie Zhang (Columbia University)<\/td>\r\n <\/tr>\r\n
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity<\/td> Nick Gravin (Shanghai University of Finance and Economics); Enze Sun (The University of Hong Kong); Zhihao Gavin Tang (Shanghai University of Finance and Economics)<\/td>\r\n <\/tr>\r\n
Near Optimal Memory-Regret Tradeoff for Online Learning<\/a><\/td> Binghui Peng (Columbia University); Aviad Rubinstein (Stanford University)<\/td>\r\n <\/tr>\r\n
Bridge Girth: A Unifying Notion in Network Design<\/td> Greg Bodwin and Gary Hoppenworth (University of Michigan); Ohad Trabelsi (Toyota Technological Institute at Chicago)<\/td>\r\n <\/tr>\r\n
Polynomial-Time Pseudodeterministic Construction of Primes<\/a><\/td> Lijie Chen (UC Berkeley); Zhenjian Lu (University of Oxford); Igor C. Oliveira (University of Warwick); Hanlin Ren and Rahul Santhanam (University of Oxford)<\/td>\r\n <\/tr>\r\n
On Symmetric Factorizations of Hankel Matrices<\/td> Mehrdad Ghadiri (Georgia Institute of Technology)<\/td>\r\n <\/tr>\r\n
Locally Uniform Hashing<\/td> Ioana-Oriana Bercea (IT University of Copenhagen); Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, and Mikkel Thorup (University of Copenhagen)<\/td>\r\n <\/tr>\r\n
Query-optimal estimation of unitary channels in diamond distance<\/td> Jeongwan Haah (Microsoft Research); Robin Kothari (Google); Ryan O'Donnell (Carnegie Mellon University); Ewin Tang (University of Washington)<\/td>\r\n <\/tr>\r\n
Planar Disjoint Paths, Treewidth, and Kernels<\/a><\/td> Michal Wlodarczyk and Meirav Zehavi (Ben-Gurion University)<\/td>\r\n <\/tr>\r\n
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow<\/td> Maximilian Probst Gutenberg (ETH Zürich); Jan van den Brand and Li Chen (Georgia Institute of Technology); Rasmus Kyng (ETH Zurich); Yang P. Liu (Stanford University); Richard Peng (University of Waterloo); Sushant Sachdeva (University of Toronto); Aaron Sidford (Stanford University)<\/td>\r\n <\/tr>\r\n
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation<\/td> Vincent Cohen-Addad (Google Research, France); David Saulpic (IST Austria); Chris Schwiegelshohn (Aarhus University)<\/td>\r\n <\/tr>\r\n
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond<\/td> Nathaniel Johnston (Mount Allison University); Benjamin Lovitz (Northeastern University); Aravindan Vijayaraghavan (Northwestern University)<\/td>\r\n <\/tr>\r\n
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming<\/td> Praneeth Kacham (Carnegie Mellon University); Rasmus Pagh and Mikkel Thorup (University of Copenhagen); David P. Woodruff (Carnegie Mellon University)<\/td>\r\n <\/tr>\r\n
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!<\/td> Divesh Aggarwal (National University of Singapore); Rajendra Kumar (Weizmann Institute of Science)<\/td>\r\n <\/tr>\r\n
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!<\/td> Alejandro Cassis and Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics); Nick Fischer (Weizmann Institute of Science)<\/td>\r\n <\/tr>\r\n
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements<\/td> Martin Grohe (RWTH Aachen University); Moritz Lichter (TU Darmstadt); Daniel Neuen (University of Bremen); Pascal Schweitzer (TU Darmstadt)<\/td>\r\n <\/tr>\r\n
The minimal canonical form of a tensor network<\/td> Arturo Acuaviva (unaffiliated); Visu Makam (Radix trading); Harold Nieuwboer (University of Amsterdam); David P√\u00a9rez-Garc√≠a (Universidad Complutense de Madrid); Friedrich Sittner (unaffiliated); Michael Walter (Ruhr-Universit√\u00a7t Bochum); Freek Witteveen (University of Copenhagen)<\/td>\r\n <\/tr>\r\n
Krylov Methods are (nearly) Optimal for Low-Rank Approximation<\/td> Ainesh Bakshi and Shyam Narayanan (Massachusetts Institute of Technology)<\/td>\r\n <\/tr>\r\n
Query lower bounds for log-concave sampling<\/td> Sinho Chewi (MIT); Jaume de Dios Pont (University of California, Los Angeles); Jerry Li (Microsoft Research); Chen Lu (MIT); Shyam Narayanan (Massachusetts Institute of Technology)<\/td>\r\n <\/tr>\r\n
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree<\/td> Costas Busch (Augusta University); Da Qi Chen (University of Virginia); Arnold Filtser (Bar-Ilan University); Daniel Hathcock (Carnegie Mellon University); D Ellis Hershkowitz (ETH Zurich); Rajmohan Rajaraman (Northeastern University)<\/td>\r\n <\/tr>\r\n
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)<\/td> Michael Elkin and Idan Shabat (Ben-Gurion University)<\/td>\r\n <\/tr>\r\n
Sub-quadratic $(1+\\eps)$-approximate Euclidean Spanner, with Applications<\/a><\/td> Hengjie Zhang and Alexandr Andoni (Columbia University)<\/td>\r\n <\/tr>\r\n
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels<\/td> Emmanuel Abbe and Colin Sandon (EPFL)<\/td>\r\n <\/tr>\r\n
Properly Learning Decision Trees with Queries is NP-Hard<\/td> Caleb Koch, Carmen Strassle, and Li-Yang Tan (Stanford University)<\/td>\r\n <\/tr>\r\n
Streaming Euclidean $k$-median and $k$-means with $o(\\log n)$ Space<\/td> Vincent Cohen-Addad (Google Research, France); David P. Woodruff (Carnegie Mellon University); Samson Zhou (UC Berkeley and Rice University)<\/td>\r\n <\/tr>\r\n
Testing Graph Properties with the Container Method<\/td> Eric Blais and Cameron Seth (University of Waterloo)<\/td>\r\n <\/tr>\r\n
Interior-point methods on manifolds: theory and applications<\/td> Hiroshi Hirai (Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan); Harold Nieuwboer (Korteweg-de Vries Institute for Mathematics and QuSoft, University of Amsterdam, The Netherlands and Faculty of Computer Science, Ruhr University Bochum, Germany); Michael Walter (Faculty of Computer Science, Ruhr University Bochum, Germany)<\/td>\r\n <\/tr>\r\n
Fourier Growth of Communication Protocols for XOR Functions<\/a><\/td> Uma Girish (Princeton University); Makrand Sinha (Simons Institute and UC Berkeley); Avishay Tal and Kewen Wu (University of California Berkeley)<\/td>\r\n <\/tr>\r\n
Optimal Algorithms for Bounded Weighted Edit Distance<\/td> Alejandro Cassis (Saarland University, Saarland Informatics Campus, Max Planck Institute for Informatics); Tomasz Kociumaka and Philip Wellnitz (Max Planck Institute for Informatics; Saarland Informatics Campus)<\/td>\r\n <\/tr>\r\n
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs<\/td> Suprovat Ghoshal (Northwestern University, TTIC); Euiwoong Lee (University of Michigan)<\/td>\r\n <\/tr>\r\n
Envy-Free Cake-Cutting for Four Agents<\/td> Alexandros Hollender (EPFL); Aviad Rubinstein (Stanford University)<\/td>\r\n <\/tr>\r\n
New Lower Bounds for Adaptive Tolerant Junta Testing<\/td> Xi Chen and Shyamal Patel (Columbia University)<\/td>\r\n <\/tr>\r\n
Optimal mixing of the down-up walk on independent sets of a given size<\/td> Vishesh Jain and Marcus Michelen (University of Illinois Chicago); Huy Tuan Pham and Thuy-Duong Vuong (Stanford University)<\/td>\r\n <\/tr>\r\n
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers<\/td> Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan (Stanford University)<\/td>\r\n <\/tr>\r\n
Top-Down Lower Bounds for Depth-Four Circuits<\/td> Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov (EPFL)<\/td>\r\n <\/tr>\r\n
ReSQueing Parallel and Private Stochastic Convex Optimization<\/td> Yair Carmon (Tel Aviv University); Arun Jambulapati (University of Washington); Yujia Jin (Stanford University); Yin Tat Lee (Microsoft Research); Daogao Liu (University of Washington); Aaron Sidford (Stanford University); Kevin Tian (Microsoft Research)<\/td>\r\n <\/tr>\r\n
Matrix Completion in Almost-Verification Time<\/td> Jonathan Kelner (MIT); Jerry Li (Microsoft Research); Allen Liu (MIT); Aaron Sidford (Stanford University); Kevin Tian (Microsoft Research)<\/td>\r\n <\/tr>\r\n
Dynamic ``Succincter''<\/td> Tianxiao Li and Jingxun Liang (IIIS, Tsinghua University); Huacheng Yu (Princeton University); Renfei Zhou (IIIS, Tsinghua University)<\/td>\r\n <\/tr>\r\n
Dynamic treewidth<\/td> Tuukka Korhonen (University of Bergen); Konrad Majewski, Wojciech Nadara, Micha≈\u00c7 Pilipczuk, and Marek Soko≈\u00c7owski (University of Warsaw)<\/td>\r\n <\/tr>\r\n
The Bit Complexity of Efficient Continuous Optimization<\/td> Mehrdad Ghadiri (Georgia Institute of Technology); Richard Peng (University of Waterloo); Santosh Vempala (Georgia Institute of Technology)<\/td>\r\n <\/tr>\r\n
Faster Matrix Multiplication via Asymmetric Hashing<\/td> Ran Duan (IIIS, Tsinghua University); Hongxun Wu (University of California at Berkeley); Renfei Zhou (IIIS, Tsinghua University)<\/td>\r\n <\/tr>\r\n
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization<\/td> Lijie Chen (Miller Institute for Basic Research in Science, UC Berkeley); Roei Tell (The Institute for Advanced Study at Princeton NJ and the DIMACS Center at Rutgers University, NJ); Ryan Williams (MIT)<\/td>\r\n <\/tr>\r\n
Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\\sqrt{n}$ Barrier<\/td> Greg Bodwin and Gary Hoppenworth (University of Michigan)<\/td>\r\n <\/tr>\r\n
The Price of Explainability for Clustering<\/td> Anupam Gupta and Madhusudhan Pittu (Carnegie Mellon University); Ola Svensson (EPFL); Rachel Yuan (Carnegie Mellon University)<\/td>\r\n <\/tr>\r\n
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space<\/td> Dominik Kempa (Stony Brook University); Tomasz Kociumaka (Max Planck Institute for Informatics)<\/td>\r\n <\/tr>\r\n
Deterministic Fully Dynamic SSSP and More<\/td> Jan van den Brand (Georgia Institute of Technology); Adam Karczmarz (University of Warsaw and IDEAS NCBR)<\/td>\r\n <\/tr>\r\n
Faster Algorithms for Text-to-Pattern Hamming Distances<\/td> Timothy M. Chan (UIUC); Ce Jin (MIT); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu (MIT)<\/td>\r\n <\/tr>\r\n
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error<\/a><\/td> He Jia (Georgia Tech); Pravesh Kothari (CMU); Santosh Vempala (Georgia Tech)<\/td>\r\n <\/tr>\r\n
On the tractability of sampling from the Potts model at low-temperatures via Swendsen--Wang dynamics<\/td> Antonio Blanca (Pennsylvania State University); Reza Gheissari (Northwestern University)<\/td>\r\n <\/tr>\r\n
Tight Time-Space Lower Bounds for Constant-Pass Learning<\/td> Xin Lyu, Avishay Tal, and Hongxun Wu (UC Berkeley); Junzhao Yang (Tsinghua Univesity)<\/td>\r\n <\/tr>\r\n
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles<\/td> Guy Bresler, Chenghao Guo, and Yury Polyanskiy (MIT)<\/td>\r\n <\/tr>\r\n
Sparse Submodular Function Minimization<\/td> Andrei Graur (Stanford University); Haotian Jiang (Microsoft Research); Aaron Sidford (Stanford University)<\/td>\r\n <\/tr>\r\n
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting<\/td> Lijie Chen (University of California at Berkeley); William Hoza (University of Chicago); Xin Lyu, Avishay Tal, and Hongxun Wu (University of California at Berkeley)<\/td>\r\n <\/tr>\r\n
When Does Adaptivity Help for Quantum State Learning?<\/td> Sitan Chen (UC Berkeley, Harvard); Brice Huang (MIT); Jerry Li (Microsoft Research); Allen Liu (MIT); Mark Sellke (Amazon, Harvard)<\/td>\r\n <\/tr>\r\n
Learning in Pessiland via Inductive Inference<\/td> Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology)<\/td>\r\n <\/tr>\r\n
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form<\/td> Adam Karczmarz and Piotr Sankowski (University of Warsaw and IDEAS NCBR)<\/td>\r\n <\/tr>\r\n
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition<\/td> Or Meir (University of Haifa)<\/td>\r\n <\/tr>\r\n
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle<\/td> Rahul Ilango (MIT)<\/td>\r\n <\/tr>\r\n
Secure Computation Meets Distributed Universal Optimality<\/td> Merav Parter (Weizmann IS)<\/td>\r\n <\/tr>\r\n
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination<\/td> Cl√\u00a9ment Canonne (University of Sydney); Samuel B Hopkins (Massachusetts Institute of Technology); Jerry Li (Microsoft Research); Allen Liu and Shyam Narayanan (Massachusetts Institute of Technology)<\/td>\r\n <\/tr>\r\n
Proof of the Clustered Hadwiger Conjecture<\/td> Vida Dujmovi\u0192\u00e1 (University of Ottawa); Louis Esperet (Laboratoire G-SCOP, Grenoble); Pat Morin (Carleton University); David Wood (Monash University)<\/td>\r\n <\/tr>\r\n
Doubly-Efficient Interactive Proofs for Distribution Properties<\/td> Tal Herman (Weizmann Institute of Science); Guy N. Rothblum (Apple)<\/td>\r\n <\/tr>\r\n
IOPs with Inverse Polynomial Soundness Error<\/td> Gal Arnon (Weizmann Institute); Alessandro Chiesa (EPFL); Eylon Yogev (Bar-Ilan University)<\/td>\r\n <\/tr>\r\n
Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time<\/td> Neil Olver (London School of Economics and Political Science); Leon Sering and Laura Vargas Koch (ETH Zurich)<\/td>\r\n <\/tr>\r\n
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding<\/td> Ariel Kulik (CISPA); Matthias Mnich (TU Hamburg); Hadas Shachnai (Technion)<\/td>\r\n <\/tr>\r\n
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $\\Omega(\\log n)$ Lightness Barrier<\/td> Cuong Than (University of Massachusetts at Amherst); Shay Solomon (Tel Aviv University); Hung Le (University of Massachusettsat Amherst)<\/td>\r\n <\/tr>\r\n
Flip-width: Cops and Robber on dense graphs<\/td> Szymon Toru≈\u00d1czyk (University of Warsaw)<\/td>\r\n <\/tr>\r\n
Stability and replicability in learning<\/td> Zachary Chase (Oxford); Shay Moran (Technion-IIT and Google Research); Amir Yehudayoff (Technion-IIT)<\/td>\r\n <\/tr>\r\n
Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography<\/td> Oded Nir and Benny Applebaum (Tel Aviv University)<\/td>\r\n <\/tr>\r\n
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots<\/td> Raghuvansh Saxena (Microsoft Research); Noah Singer (Carnegie Mellon University); Santhoshini Velusamy and Madhu Sudan (Harvard University)<\/td>\r\n <\/tr>\r\n
Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes<\/td> Silas Richelson and Sourya Roy (University of California, Riverside)<\/td>\r\n <\/tr>\r\n
Covering Planar Metrics (and Beyond): O(1) Trees Suffice<\/td> Hsien-Chih Chang and Jonathan Conroy (Dartmouth College); Hung Le (University of Massachusetts); Lazar Milenkovi\u0192\u00e1 and Shay Solomon (Tel Aviv University); Cuong Than (College of Information and Computer Sciences, University of Massachusetts Amherst)<\/td>\r\n <\/tr>\r\n
Strong Bounds for 3-Progressions<\/td> Zander Kelley (UIUC); Raghu Meka (UCLA)<\/td>\r\n <\/tr>\r\n
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs<\/td> AmirMahdi Ahmadinejad (Amazon); John Peebles (Apple); Edward Pyne (MIT); Aaron Sidford (Stanford University); Salil Vadhan (Harvard University)<\/td>\r\n <\/tr>\r\n
On Pseudolinear Codes for Correcting Adversarial Errors<\/td> Eric Ruzomberka and Homa Nikbakht (Princeton University); Christopher G. Brinton (Purdue University); H. Vincent Poor (Princeton University)<\/td>\r\n <\/tr>\r\n
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates<\/td> Fernando Granha Jeronimo (Institute for Advanced Study); Shashank Srivastava and Madhur Tulsiani (TTIC)<\/td>\r\n <\/tr>\r\n
Memory-Query Tradeoffs for Randomized Convex Optimization<\/a><\/td> Xi Chen and Binghui Peng (Columbia University)<\/td>\r\n <\/tr>\r\n
Optimal PAC Bounds Without Uniform Convergence<\/td> Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy (UC Berkeley)<\/td>\r\n <\/tr>\r\n
Exponential quantum speedup in simulating coupled classical oscillators<\/td> Ryan Babbush (Google); Dominic Berry (Macquarie University); Robin Kothari and Rolando Somma (Google); Nathan Wiebe (University of Toronto)<\/td>\r\n <\/tr>\r\n
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting<\/td> Ofer Grossman (MIT); Meghal Gupta (UC Berkeley); Mark Sellke (Harvard)<\/td>\r\n <\/tr>\r\n
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence<\/td> Mohsen Ghaffari (MIT); Christoph Grunau and Vaclav Rozhon (ETH Zurich)<\/td>\r\n <\/tr>\r\n
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement<\/td> Marshall Ball (NYU); Yanyi Liu (Cornell University); Noam Mazor (Cornell Tech); Rafael Pass (Tel-Aviv University & Cornell Tech)<\/td>\r\n <\/tr>\r\n
Graph Colouring is Hard on Average for Polynomial Calculus and Nullstellensatz<\/td> Jonas Conneryd (Lund University and University of Copenhagen); Susanna F. de Rezende (Lund University); Jakob Nordström and Shuo Pang (University of Copenhagen and Lund University); Kilian Risse (EPFL)<\/td>\r\n <\/tr>\r\n
Clique is Hard on Average for Unary Sherali-Adams<\/td> Susanna de Rezende (Lund University); Aaron Potechin (University of Chicago); Kilian Risse (EPFL)<\/td>\r\n <\/tr>\r\n
Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings<\/td> Sepehr Assadi (Rutgers University and University of Waterloo); Janani Sundaresan (Rutgers University)<\/td>\r\n <\/tr>\r\n
A New Approach to Post-Quantum Non-Malleability<\/td> Xiao Liang (NTT Research); Omkant Pandey (Stony Brook University); Takashi Yamakawa (NTT Social Informatics Laboratories)<\/td>\r\n <\/tr>\r\n
ABE for Circuits with poly(λ)-sized Keys from LWE<\/td> Valerio Cini (AIT, Austria); Hoeteck Wee (NTT Research, USA)<\/td>\r\n <\/tr>\r\n
Self-Improving Output-Sensitive Convex Hull Algorithm<\/td> Siu-Wing Cheng (HKUST)<\/td>\r\n <\/tr>\r\n
Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders<\/td> Yang Cai (Yale University); Ziyun Chen (Tsinghua University); Jinzhao Wu (Yale University)<\/td>\r\n <\/tr>\r\n
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices<\/td> Yao-Ching Hsieh, Huijia (Rachel) Lin, and Ji Luo (University of Washington)<\/td>\r\n <\/tr>\r\n
Separating Computational and Statistical Differential Privacy Under Plausible Assumptions<\/td> Badih Ghazi (Google); Rahul Ilango (Massachusetts Institute of Technology); Pritish Kamath (Google Research); Ravi Kumar (Google); Pasin Manurangsi (Google Research)<\/td>\r\n <\/tr>\r\n
Local Computation Algorithms for Maximum Matching: New Lower Bounds<\/td> Soheil Behnezhad (Northeastern University); Mohammad Roghani and Aviad Rubinstein (Stanford University)<\/td>\r\n <\/tr>\r\n<\/table>\r\n\r\n\r\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

FOCS Accepted Papers Accepted Paper Authors Parallel Repetition for the GHZ Game: Exponential Decay Mark Braverman (Princeton University); Subhash Khot (NYU); Dor Minzer (MIT) Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets Zeyu Guo and Zihan Zhang (The Ohio State University) Streaming Lower Bounds and Asymmetric Set-Disjointness Shachar Lovett (UC San […]<\/p>\n","protected":false},"author":4,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1479","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2023\/wp-json\/wp\/v2\/pages\/1479","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2023\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2023\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2023\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2023\/wp-json\/wp\/v2\/comments?post=1479"}],"version-history":[{"count":0,"href":"https:\/\/focs.computer.org\/2023\/wp-json\/wp\/v2\/pages\/1479\/revisions"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2023\/wp-json\/wp\/v2\/media?parent=1479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}