{"id":1642,"date":"2024-06-26T02:13:51","date_gmt":"2024-06-26T02:13:51","guid":{"rendered":"https:\/\/focs.computer.org\/2024\/?page_id=1642"},"modified":"2024-10-05T12:38:46","modified_gmt":"2024-10-05T12:38:46","slug":"accepted-papers-for-focs-2024","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2024\/accepted-papers-for-focs-2024\/","title":{"rendered":"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 2024 Accepted Papers<\/b><\/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
\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

FOCS 2024 Accepted Papers<\/strong><\/h2>
  1. \u00a0O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold<\/li><\/ol>

    Tolson Bell, Alan Frieze (Carnegie Mellon University)<\/p>

    1. A stronger bound for linear 3-LCC<\/li><\/ol>

      Tal Yankovitz (Tel Aviv University)<\/p>

      1. Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric<\/li><\/ol>

        Zeyu Guo (The Ohio State University); Chaoping Xing, Chen Yuan (Shanghai Jiao Tong University); Zihan Zhang (The Ohio State University)<\/p>

        1. Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable<\/li><\/ol>

          Sasank Mouli (Mahindra University)<\/p>

          1. Capacity Threshold for the Ising Perceptron<\/li><\/ol>

            Brice Huang (MIT)<\/p>

            1. Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem<\/li><\/ol>

              Marcelo Garlet Milani (National Institute of Informatics, Tokyo, Japan); Stephan Kreutzer (TU Berlin); Irene Muzi (Universitaet Hamburg); Meike Hatzel (National Institute of Informatics, Tokyo, Japan)<\/p>

              1. On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication<\/li><\/ol>

                Yang Liu (IAS)<\/p>

                1. Online Combinatorial Allocations and Auctions with Few Samples<\/li><\/ol>

                  Paul Duetting (Google); Thomas Kesselheim (University of Bonn); Brendan Lucier (Microsoft Research); Rebecca Reiffenhauser (University of Amsterdam); Sahil Singla (Georgia Tech)<\/p>

                  1. Efficient approximate unitary designs from random Pauli rotations<\/li><\/ol>

                    Jeongwan Haah (Microsoft Quantum); Yunchao Liu (UC Berkeley); Xinyu Tan (MIT)<\/p>

                    1. Verifying Groups in Linear Time<\/li><\/ol>

                      Ohad Klein (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research); Shai Evra, Shay Gadot (Hebrew University)<\/p>

                      1. Fast list decoding of univariate multiplicity and folded Reed-Solomon codes<\/li><\/ol>

                        Rohan Goyal (Chennai Mathematical Institute); Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar (Tata Institute of Fundamental Research)<\/p>

                        1. First-Order Model Checking on Monadically Stable Graph Classes<\/li><\/ol>

                          Jan Dreier (TU Wien); Ioannis Eleftheriadis (University of Cambridge); Nikolas M\u00e4hlmann (University of Bremen); Rose McCarty (Georgia Institute of Technology); Micha\u0142 Pilipczuk, Szymon Toru\u0144czyk (University of Warsaw)<\/p>

                          1. Proofs of Space with Maximal Hardness<\/li><\/ol>

                            Leonid Reyzin (Boston University)<\/p>

                            1. A Dense Model Theorem for the Boolean Slice<\/li><\/ol>

                              Gil Kalai, Noam Lifshitz, Tamar Ziegler (Hebrew University of Jerusalem); Dor Minzer (MIT)<\/p>

                              1. Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality<\/li><\/ol>

                                Jan van den Brand (Georgia Tech); Li Chen (Carnegie Mellon University); Rasmus Kyng (ETH Zurich); Yang P. Liu (Institute for Advanced Study); Simon Meierhans (ETH Zurich); Maximilian Probst Gutenberg (ETH Z\u00fcrich); Sushant Sachdeva (University of Toronto \/ Google)<\/p>

                                1. Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\\sqrt{n}$ Dimension Threshold<\/li><\/ol>

                                  Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh (Carnegie Mellon University); Prasad Raghavendra (U.C. Berkeley)<\/p>

                                  1. Power Series Composition in Near-Linear Time<\/li><\/ol>

                                    Yasunori Kinoshita (Tokyo Institute of Technology); Baitian Li (Tsinghua University)<\/p>

                                    1. The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution<\/li><\/ol>

                                      Zhiyan Ding (University of California, Berkeley); Ethan N. Epperly (Caltech); Lin Lin (University of California, Berkeley); Ruizhe Zhang (Simons Institute for the Theory of\u00a0 Computing)<\/p>

                                      1. Obstructions to Erd\u0151s-P\u00f3sa Dualities for Minors<\/li><\/ol>

                                        Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos (LIRMM, Univ. Montpellier, CNRS, France); Sebastian Wiederrecht (Discrete Mathematics Group, IBS, South Korea)<\/p>

                                        1. Optimal Bounds for Open Addressing Without Reordering<\/li><\/ol>

                                          Martin Farach-Colton (NYU); Andrew Krapivin (Rutgers University); William Kuszmaul (Harvard University)<\/p>

                                          1. Tight Analyses of Ordered and Unordered Linear Probing<\/li><\/ol>

                                            Mark Braverman (Princeton University); William Kuszmaul (Harvard University)<\/p>

                                            1. Tight Bounds for Classical Open Addressing<\/li><\/ol>

                                              Michael Bender (Stony Brook University); William Kuszmaul (Harvard University); Renfei Zhou (Tsinghua University)<\/p>

                                              1. Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint<\/li><\/ol>

                                                Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa)<\/p>

                                                1. Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier<\/li><\/ol>

                                                  Shiri Ron (Weizmann Institute of Science); Clayton Thomas (Microsoft Research); S. Matthew Weinberg, Qianfan Zhang (Princeton University)<\/p>

                                                  1. High-Temperature Gibbs States are Unentangled and Efficiently Preparable<\/li><\/ol>

                                                    Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley)<\/p>

                                                    1. Structure learning of Hamiltonians from real-time evolution<\/li><\/ol>

                                                      Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley)<\/p>

                                                      1. Gaussian Approximation of Convex Sets by Intersections of Halfspaces<\/li><\/ol>

                                                        Anindya De (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University)<\/p>

                                                        1. Constant Degree Direct Product Testers with Small Soundness<\/li><\/ol>

                                                          Mitali Bafna (MIT); Noam Lifshitz (Hebrew University); Dor Minzer (MIT)<\/p>

                                                          1. On Approximating Cutwidth and Pathwidth<\/li><\/ol>

                                                            Nikhil Bansal (University of Michigan); Dor Katzelnick (Technion – Israel Institute of Technology); Roy Schwartz (Technion)<\/p>

                                                            1. Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps<\/li><\/ol>
                                                              Bernhard Haeupler, Richard Hlad\u00edk (INSAIT, University of Sofia “St. Kliment Ohridski” & ETH Zurich); Vaclav Rozhon (INSAIT, University of Sofia “St. Kliment Ohridski”); Robert Tarjan (Princeton University); Jakub T\u011btek (INSAIT, University of Sofia “St. Kliment Ohridski”)<\/div>
                                                              1. Gapped Clique Homology is QMA1-hard and contained in QMA<\/li><\/ol>

                                                                Robbie King (Caltech); Tamara Kohler (Stanford)<\/p>

                                                                1. Boosting uniformity in quasirandom groups: faster and simpler<\/li><\/ol>

                                                                  Emanuele Viola (NEU); Harm Derksern (Northeatern University); Chin Ho Lee (NCSU)<\/p>

                                                                  1. The sample complexity of smooth boosting and the tightness of the hardcore theorem<\/li><\/ol>

                                                                    Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan (Stanford University)<\/p>

                                                                    1. Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles<\/li><\/ol>

                                                                      Omar Alrabiah, Venkatesan Guruswami (UC Berkeley)<\/p>

                                                                      1. Reverse Mathematics of Complexity Lower Bounds<\/li><\/ol>

                                                                        Lijie Chen (University of California at Berkeley); Jiatu Li (Massachusetts Institute of Technology); Igor C. Oliveira (University of Warwick)<\/p>

                                                                        1. Agnostically Learning Multi-index Models with Queries<\/li><\/ol>

                                                                          Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Vasilis Kontonis (University of Texas-Austin); Christos Tzamos, Nikos Zarifis (University of Wisconsin-Madison)<\/p>

                                                                          1. Instance-Optimality in I\/O-Efficient Sampling and Sequential Estimation<\/li><\/ol>

                                                                            Shyam Narayanan (MIT); V\u00e1clav Rozho\u0148 (INSAIT, University of Sofia “St. Kliment Ohridski”); Jakub T\u011btek (INSAIT, University of Sofia “St. Kliment Ohridski”), Mikkel Thorup (University of Copenhagen)<\/p>

                                                                            1. Faster $(\\Delta + 1)$-Edge Coloring: Breaking the $m \\sqrt{n}$ Time Barrier<\/li><\/ol>

                                                                              Sayan Bhattacharya (University of Warwick); Din Carmon (Tel Aviv University); Martin Costa (University of Warwick); Shay Solomon, Tianyi Zhang (Tel Aviv University)<\/p>

                                                                              1. Improved Distance (Sensitivity) Oracles with Subquadratic Space<\/li><\/ol>

                                                                                Davide Bil\u00f2 (University of L’Aquila); Shiri Chechik (Tel-Aviv University); Keerti Choudhary (Indian Institute of Technology); Sarel Cohen (The Academic College of Tel Aviv-Yaffo, Israel); Tobias Friedrich (Hasso Plattner Institute); Martin Schirneck (University of Vienna, Austria)<\/p>

                                                                                1. An Improved Line-Point Low-Degree Test<\/li><\/ol>

                                                                                  Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi (Tata Institute of Fundamental Research); Madhu Sudan (Harvard University)<\/p>

                                                                                  1. Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer<\/li><\/ol>

                                                                                    Yaonan Jin (Huawei TCS Lab); Pinyan Lu (Shanghai University of Finance and Economics)<\/p>

                                                                                    1. An Improved Pseudopolynomial Time Algorithm for Subset Sum<\/li><\/ol>

                                                                                      Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)<\/p>

                                                                                      1. Fully Dynamic k-Clustering with Fast Update Time and Small Recourse<\/li><\/ol>

                                                                                        Sayan Bhattacharya, Martin Costa (University of Warwick); Naveen Garg (IIT Delhi); Silvio Lattanzi, Nikos Parotsidis (Google Research)<\/p>

                                                                                        1. Constant-Depth Arithmetic Circuits for Linear Algebra Problems<\/li><\/ol>

                                                                                          Robert Andrews, Avi Wigderson (Institute for Advanced Study)<\/p>

                                                                                          1. Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\\epsilon}$ Worst-Case Update Time<\/li><\/ol>

                                                                                            Bernhard Haeupler (INSAIT, University of Sofia “St. Kliment Ohridski” & ETH Zurich); Yaowei Long, Thatchaphol Saranurak (University of Michigan)<\/p>

                                                                                            1. Lempel-Ziv (LZ77) Factorization in Sublinear Time<\/li><\/ol>

                                                                                              Dominik Kempa (Stony Brook University); Tomasz Kociumaka (INSAIT, University of Sofia “St. Kliment Ohridski”)<\/p>

                                                                                              1. The Tractability Border of Reachability in Simple Vector Addition Systems with States<\/li><\/ol>

                                                                                                Dmitry Chistikov (Centre for Discrete Mathematics and its Applications (DIMAP) & Department of Computer Science, University of Warwick, Coventry, UK); Wojciech Czerwi\u0144ski, \u0141ukasz Orlikowski, Filip Mazowiecki (University of Warsaw); Henry Sinclair-Banks (Centre for Discrete Mathematics and its Applications (DIMAP) & Department of Computer Science, University of Warwick, Coventry, UK); Karol W\u0119grzycki (Saarland University and Max Planck Institute for Informatics, Saarbrucken, Germany)<\/p>

                                                                                                1. Semi-Bandit Learning for Monotone Stochastic Optimization<\/li><\/ol>

                                                                                                  Arpit Agarwal (Columbia University); Rohan Ghuge (Georgia Institute of Technology); Viswanath Nagarajan (University of Michigan)<\/p>

                                                                                                  1. Sparse graph counting and Kelley\u2013Meka bounds for binary systems<\/li><\/ol>

                                                                                                    \u00a0Yuval Filmus (Technion – Israel Institute of Technology); Hamed Hatami (McGill University); Kaave Hosseini (University of Rochester); Esty Kelman (MIT, Boston University)<\/p>

                                                                                                    1. Replicability in High Dimensional Statistics<\/li><\/ol>

                                                                                                      Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye (University of California, San Diego)<\/p>

                                                                                                      1. Efficient Unitary Designs from Random Sums and Permutations<\/li><\/ol>

                                                                                                        Chi-Fang Chen (Caltech); Jordan Docter, Michelle Xu, Adam Bouland (Stanford); Fernando Brandao (Caltech); Patrick Hayden (Stanford)<\/p>

                                                                                                        1. Commitments are equivalent to one-way state generators<\/li><\/ol>

                                                                                                          Rishabh Batra (CQT); Rahul Jain (National University of Singapore)<\/p>

                                                                                                          1. On the Existence of Seedless Condensers: Exploring the Terrain<\/li><\/ol>

                                                                                                            Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach (Cornell University)<\/p>

                                                                                                            1. Computing Approximate Centerpoints in Polynomial Time<\/li><\/ol>

                                                                                                              Yeshwanth Cherapanamjeri (MIT)<\/p>

                                                                                                              1. Fast decision tree learning solves hard coding-theoretic problems<\/li><\/ol>

                                                                                                                Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)<\/p>

                                                                                                                1. Nearly Optimal List Labeling<\/li><\/ol>

                                                                                                                  Michael A. Bender (Stony Brook University); Alex Conway (Cornell Tech); Martin Farach-Colton, Hanna Komlos (New York University); Michal Koucky (Charles University); William Kuszmaul (Harvard University); Michael Saks (Rutgers University)<\/p>

                                                                                                                  1. Quantum eigenvalue processing<\/li><\/ol>

                                                                                                                    Guang Hao Low (Microsoft Research); Yuan Su (Microsoft)<\/p>

                                                                                                                    1. Quantum computational advantage with constant-temperature Gibbs sampling<\/li><\/ol>

                                                                                                                      Thiago Bergamaschi (UC Berkeley); Chi-Fang Chen (Caltech); Yunchao Liu (UC Berkeley)<\/p>

                                                                                                                      1. Towards Instance-Optimal Euclidean Spanners<\/li><\/ol>

                                                                                                                        Hung Le (University of Massachusetts Amherst);\u00a0 Shay Solomon (Tel Aviv University); Cuong Than (University of Massachusetts Amherst); Csaba D. T\\’oth (California State University Northridge and Tufts University); Tianyi Zhang (Tel Aviv University)<\/p>

                                                                                                                        1. Stochastic Online Correlated Selection<\/li><\/ol>

                                                                                                                          Ziyun Chen (Tsinghua University); Zhiyi Huang, Enze Sun (The University of Hong Kong)<\/p>

                                                                                                                          1. Predict to Minimize Swap Regret for All Payoff-Bounded Tasks<\/li><\/ol>

                                                                                                                            Lunjia Hu (Stanford University); Yifan Wu (Northwestern University)<\/p>

                                                                                                                            1. Simple constructions of linear-depth t-designs and pseudorandom unitaries<\/li><\/ol>

                                                                                                                              Tony Metger (ETH Zurich); Alexander Poremba (MIT); Makrand Sinha (UIUC); Henry Yuen (Columbia University)<\/p>

                                                                                                                              1. Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning<\/li><\/ol>

                                                                                                                                Noah Golowich (MIT); Ankur Moitra (Math & CSAIL, MIT); Dhruv Rohatgi (MIT)<\/p>

                                                                                                                                1. Optimal tradeoffs for estimating Pauli observables<\/li><\/ol>

                                                                                                                                  Sitan Chen, Weiyuan Gong (Harvard University); Qi Ye (Tsinghua University)<\/p>

                                                                                                                                  1. Dot-Product Proofs and Their Applications<\/li><\/ol>

                                                                                                                                    Nir Bitansky (New York University and Tel Aviv University); Prahladh Harsha (Tata Institute of Fundamental Research); Yuval Ishai, Ron Rothblum (Technion); David J. Wu (UT Austin)<\/p>

                                                                                                                                    1. Fast Mixing in Sparse Random Ising Models<\/li><\/ol>

                                                                                                                                      Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman (MIT); David X Wu (UC Berkeley)<\/p>

                                                                                                                                      1. Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers<\/li><\/ol>

                                                                                                                                        Sanjeev Khanna (University of Pennsylvania); Aaron (Louie) Putterman, Madhu Sudan (Harvard University)<\/p>

                                                                                                                                        1. Efficient Certificates of Anti-Concentration Beyond Gaussians<\/li><\/ol>

                                                                                                                                          Ainesh Bakshi (MIT); Pravesh Kothari (Princeton University and IAS); Goutham Rajendran (Carnegie Mellon University); Madhur Tulsiani (Toyota Technological Institute at Chicago); Aravindan Vijayaraghavan (Northwestern University)<\/p>

                                                                                                                                          1. Minor Containment and Disjoint Paths in almost-linear time<\/li><\/ol>

                                                                                                                                            Tuukka Korhonen (University of Bergen); Micha\u0142 Pilipczuk, Giann\u03bfs Stamoulis (University of Warsaw)<\/p>

                                                                                                                                            1. Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems<\/li><\/ol>

                                                                                                                                              Hiroshi Hirai (Graduate School of Mathematics, Nagoya University); Keiya Sakabe (Graduate School of Information Science and Technology, The University of Tokyo)<\/p>

                                                                                                                                              1. A Sampling Lov\u00e1sz Local Lemma for Large Domain Sizes<\/li><\/ol>

                                                                                                                                                Chunyang Wang, Yitong Yin (Nanjing University)<\/p>

                                                                                                                                                1. Naively Sorting Evolving Data is Optimal and Robust<\/li><\/ol>

                                                                                                                                                  George Giakkoupis (INRIA); Marcos Kiwi (U. Chile); Dimitrios Los (University of Cambridge)<\/p>

                                                                                                                                                  1. Tight Bounds for Sorting Under Partial Information<\/li><\/ol>

                                                                                                                                                    Ivor van der Hoog (Technical University of Denmark); Daniel Rutschmann (Technical University of Denmark, DTU)<\/p>

                                                                                                                                                    1. Revisiting Agnostic PAC Learning<\/li><\/ol>

                                                                                                                                                      Steve Hanneke (Purdue University); Kasper Green Larsen (Aarhus University); Nikita Zhivotovskiy (UC Berkeley)<\/p>

                                                                                                                                                      1. Computing the 3-edge-connected components of directed graphs in linear time<\/li><\/ol>

                                                                                                                                                        Evangelos Kosinas (ISTA (Institute of Science and Technology Austria)); Loukas Georgiadis (University of Ioannina); Giuseppe F. Italiano (LUISS University of Rome)<\/p>

                                                                                                                                                        1. Decoding Quasi-Cyclic Quantum LDPC Codes<\/li><\/ol>

                                                                                                                                                          Louis Golowich, Venkatesan Guruswami (UC Berkeley)<\/p>

                                                                                                                                                          1. Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares<\/li><\/ol>

                                                                                                                                                            Mikkel Abrahamsen, Jack Stade (University of Copenhagen, Denmark)<\/p>

                                                                                                                                                            1. Semirandom Planted Clique and the Restricted Isometry Property<\/li><\/ol>

                                                                                                                                                              Jaros\u0142aw B\u0142asiok, Rares-Darius Buhai (ETH Zurich); Pravesh K Kothari (Princeton University and IAS); David Steurer (ETH Zurich)<\/p>

                                                                                                                                                              1. A Lossless Deamortization for Dynamic Greedy Set Cover<\/li><\/ol>

                                                                                                                                                                Shay Solomon, Amitai Uzrad, Tianyi Zhang (Tel Aviv University)<\/p>

                                                                                                                                                                1. Ramsey Theorems for Trees and a General \u2018Private Learning Implies Online Learning\u2019 Theorem<\/li><\/ol>

                                                                                                                                                                  Simone Fioravanti (Gran Sasso Science Institute); Steve Hanneke (Purdue University); Shay Moran, Hilla Schefler, Iska Tsubari (Technion)<\/p>

                                                                                                                                                                  1. Sampling, counting, and large deviations for triangle-free graphs near the critical density<\/li><\/ol>

                                                                                                                                                                    Matthew Jenssen (King’s College London); Will Perkins (Georgia Tech); Aditya Potukuchi (York University); Michael Simkin (MIT)<\/p>

                                                                                                                                                                    1. Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs<\/li><\/ol>

                                                                                                                                                                      Yotam Dikstein (IAS); Irit Dinur (Weizmann Institute of Science); Alexander Lubotzky (Weizmann)<\/p>

                                                                                                                                                                      1. The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2.<\/li><\/ol>

                                                                                                                                                                        Jaros\u0142aw Byrka (University of Wroc\u0142aw); Fabrizio Grandoni (IDSIA, University of Lugano); Vera Traub (University of Bonn)<\/p>

                                                                                                                                                                        1. Chernoff-Hoeffding and Reverse Hypercontractivity on High Dimensional Expanders<\/li><\/ol>

                                                                                                                                                                          Yotam Dikstein (IAS); Max Hopkins (UCSD)<\/p>

                                                                                                                                                                          1. Three-edge-coloring projective planar cubic graphs:\\\\ A generalization of the Four Color Theorem<\/li><\/ol>

                                                                                                                                                                            Yuta Inoue (The University of Tokyo); Kenichi Kawarabayashi (National Institute of Informatics and The University of Tokyo); Atsuyuki Miyashita (The University of Tokyo); Bojan Mohar (Simon Fraser University); Tomohiro Sonobe (National Institute of Informatics)<\/p>

                                                                                                                                                                            1. Interactive Proofs for General Distribution Properties<\/li><\/ol>

                                                                                                                                                                              Tal Herman (Weizmann Institute); Guy Rothblum (Apple)<\/p>

                                                                                                                                                                              1. Tight Bounds for the Zig-Zag Product<\/li><\/ol>

                                                                                                                                                                                Gil Cohen, Gal Maor, Itay Cohen (Tel Aviv University)<\/p>

                                                                                                                                                                                1. Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications<\/li><\/ol>

                                                                                                                                                                                  Shuichi Hirahara (National Institute of Informatics); Zhenjian Lu (University of Warwick); Mikito Nanashima (Tokyo Institute of Technology)<\/p>

                                                                                                                                                                                  1. Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds<\/li><\/ol>

                                                                                                                                                                                    Nikhil Bansal (University of Michigan); Vincent Cohen-Addad (Google Research, France); Milind Prabhu (University of Michigan); David Saulpic (Universit\u00e9 Paris Cit\u00e9, CNRS); Chris Schwiegelshohn (Aarhus University)<\/p>

                                                                                                                                                                                    1. The Online Submodular Assignment Problem<\/li><\/ol>

                                                                                                                                                                                      Sherry Sarkar, Daniel Hathcock, Mik Zlatin (Carnegie Mellon University); Billy Jin (Cornell University); Kalen Patton (Georgia Tech)<\/p>

                                                                                                                                                                                      1. Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs<\/li><\/ol>

                                                                                                                                                                                        Pravesh K. Kothari (Princeton University and IAS); Peter Manohar (Carnegie Mellon University)<\/p>

                                                                                                                                                                                        1. Efficient Approximation of Hypertree Width<\/li><\/ol>

                                                                                                                                                                                          Vaishali Surianarayanan (University of California Santa Barbara); Daniel Lokshtanov (University of California Santa Barbara, USA); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai); Vika Korchemna (TU Wien)<\/p>

                                                                                                                                                                                          1. Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness<\/li><\/ol>

                                                                                                                                                                                            Jiatu Li, Edward Pyne (MIT); Roei Tell (University of Toronto)<\/p>

                                                                                                                                                                                            1. Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time<\/li><\/ol>

                                                                                                                                                                                              Aaron Bernstein (Rutgers University); Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); Thatchaphol Saranurak (University of Michigan); Ta-Wei Tu (Stanford University)<\/p>

                                                                                                                                                                                              1. Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems<\/li><\/ol>

                                                                                                                                                                                                Friedrich Eisenbrand (EPFL); Lars Rohwedder (Maastricht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)<\/p>

                                                                                                                                                                                                1. The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds<\/li><\/ol>

                                                                                                                                                                                                  Ryan Williams (MIT)<\/p>

                                                                                                                                                                                                  1. Computational Dynamical Systems<\/li><\/ol>

                                                                                                                                                                                                    Jordan Cotler (Harvard University); Semon Rezchikov (Princeton University)<\/p>

                                                                                                                                                                                                    1. On the Complexity of Avoiding Heavy Elements<\/li><\/ol>

                                                                                                                                                                                                      Zhenjian Lu, Igor C. Oliveira (University of Warwick); Hanlin Ren, Rahul Santhanam (University of Oxford)<\/p>

                                                                                                                                                                                                      1. Trading Determinism for Noncommutativity in Edmonds’ Problem<\/li><\/ol>

                                                                                                                                                                                                        Arvind (Institute of Mathematical Sciences (HBNI), and CMI); Abhranil Chatterjee (Indian Statistical Institute, Kolkata); Partha Mukhopadhyay (Chennai Mathematical Institute)<\/p>

                                                                                                                                                                                                        1. Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis<\/li><\/ol>

                                                                                                                                                                                                          Ilias Diakonikolas, Sushrut Karmalkar (UW-Madison); Shuo Pang (University of Copenhagen); Aaron Potechin (UChicago)<\/p>

                                                                                                                                                                                                          1. $\\Pi_2^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem<\/li><\/ol>

                                                                                                                                                                                                            Dmitriy Zhuk (Charles University, Prague)<\/p>

                                                                                                                                                                                                            1. Near-Optimal $(1+\\epsilon)$-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs<\/li><\/ol>

                                                                                                                                                                                                              Arnold Filtser (Bar-Ilan University); Gramoz Goranci (University of Vienna); Neel Patel (University of Southern California); Maximilian Probst Gutenberg (ETH Zurich)<\/p>

                                                                                                                                                                                                              1. Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach<\/li><\/ol>

                                                                                                                                                                                                                Renato Ferreira Pinto Jr. (University of Waterloo)<\/p>

                                                                                                                                                                                                                1. On Robustness to k-wise Independence of Optimal Bayesian Mechanisms<\/li><\/ol>

                                                                                                                                                                                                                  Nick Gravin, Zhiqi Wang (Shanghai University of Finance and Economics)<\/p>

                                                                                                                                                                                                                  1. Expansion of high-dimensional cubical complexes with application to quantum locally Testable codes<\/li><\/ol>

                                                                                                                                                                                                                    Irit Dinur (Weizmann); Ting-Chun Lin (UCSD); Thomas Vidick (Weizmann Institute of Science)<\/p>

                                                                                                                                                                                                                    1. Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS<\/li><\/ol>

                                                                                                                                                                                                                      Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)<\/p>

                                                                                                                                                                                                                      1. A computational test of quantum contextuality, and even simpler proofs of quantumness<\/li><\/ol>

                                                                                                                                                                                                                        Atul Singh Arora (University of Maryland, Caltech); Andrea Coladangelo (University of Washington); Alexandru Cojocaru (University of Edinburgh, University of Maryland); Kishor Bharti (A*STAR Quantum Innovation Centre (Q.InC), Institute of High Performance Computing (IHPC), Agency for Science, Technology and Research (A*STAR), Singapore. Centre for Quantum Engineering, Research and Education, TCG CREST, India.)<\/p>

                                                                                                                                                                                                                        1. On Pigeonhole Principles and Ramsey in TFNP<\/li><\/ol>

                                                                                                                                                                                                                          Siddhartha Jain, Jiawei Li (UT Austin); Robert Robere (McGill); Zhiyang Xun (UT Austin)<\/p>

                                                                                                                                                                                                                          1. New investigations into noncommutative CSPs<\/li><\/ol>

                                                                                                                                                                                                                            Eric Culf (University of Waterloo); Hamoon Mousavi (University of California at Berkeley); Taro Spirig (University of Copenhagen)<\/p>

                                                                                                                                                                                                                            1. Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems<\/li><\/ol>

                                                                                                                                                                                                                              Mo\u00efse Blanchard (MIT)<\/p>

                                                                                                                                                                                                                              1. Strong vs. Weak Range Avoidance and the Linear Ordering Principle<\/li><\/ol>

                                                                                                                                                                                                                                Oliver Korten, Toniann Pitassi (Columbia University)<\/p>

                                                                                                                                                                                                                                1. Novel properties of hierarchical probabilistic partitions and their algorithmic applications<\/li><\/ol>

                                                                                                                                                                                                                                  Sandip Banerjee (IDSIA, USI-SUPSI, Lugano, Switzerland); Yair Bartal (Heberew University); Lee-Ad Gottlieb (Ariel University); Alon Hovav (Hebrew University)<\/p>

                                                                                                                                                                                                                                  1. An Optimal Algorithm for Sorting Pattern-Avoiding Sequences<\/li><\/ol>

                                                                                                                                                                                                                                    Michal Opler (Czech Technical University, Prague)<\/p>

                                                                                                                                                                                                                                    1. Succinct arguments for QMA from standard assumptions via compiled nonlocal games<\/li><\/ol>

                                                                                                                                                                                                                                      Tony Metger (ETH Zurich); Anand Natarajan, Tina Zhang (MIT)<\/p>

                                                                                                                                                                                                                                      1. An XOR Lemma for Deterministic Communication Complexity<\/li><\/ol>

                                                                                                                                                                                                                                        Siddharth Iyer, Anup Rao (University of Washington)<\/p>

                                                                                                                                                                                                                                        1. Certifying almost all quantum states with few single-qubit measurements<\/li><\/ol>

                                                                                                                                                                                                                                          Hsin-Yuan Huang (Google Quantum AI, Caltech); John Preskill (Caltech, AWS Center for Quantum Computing); Mehdi Soleimanifar (Caltech)<\/p>

                                                                                                                                                                                                                                          1. Canonical forms for matrix tuples in polynomial time<\/li><\/ol>

                                                                                                                                                                                                                                            Youming Qiao (University of Technology Sydney); Xiaorui Sun (University of Illinois at Chicago)<\/p>

                                                                                                                                                                                                                                            1. Locally Stationary Distributions<\/li><\/ol>

                                                                                                                                                                                                                                              Kuikui Liu, Sidhanth Mohanty (MIT); Prasad Raghavendra (UC Berkeley); Amit Rajaraman (MIT); David X Wu (UC Berkeley)<\/p>

                                                                                                                                                                                                                                              1. Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs<\/li><\/ol>

                                                                                                                                                                                                                                                Xifan Yu, Dmitriy Kunisky (Yale University)<\/p>

                                                                                                                                                                                                                                                1. Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy<\/li><\/ol>

                                                                                                                                                                                                                                                  Krishnamurthy (Dj) Dvijotham (Google DeepMind); H. Brendan McMahan (Google); Krishna Pillutla (IIT Madras); Thomas Steinke, Abhradeep Guha Thakurta (Google DeepMind)<\/p>

                                                                                                                                                                                                                                                  1. The Communication Complexity of Approximating Matrix Rank<\/li><\/ol>

                                                                                                                                                                                                                                                    Alexander A. Sherstov, Andrey A. Storozhenko (University of California, Los Angeles)<\/p>

                                                                                                                                                                                                                                                    1. Jump operators, Interactive Proofs and Proof Complexity Generators<\/li><\/ol>

                                                                                                                                                                                                                                                      Erfan Khaniki (Institute of math of the CAS)<\/p>

                                                                                                                                                                                                                                                      1. Optimal quantile estimation: beyond the comparison model<\/li><\/ol>

                                                                                                                                                                                                                                                        Mihir Singhal, Meghal Gupta, Hongxun Wu (UC Berkeley)<\/p>

                                                                                                                                                                                                                                                        1. New Structures and Algorithms for Length-Constrained Expander Decompositions<\/li><\/ol>

                                                                                                                                                                                                                                                          Bernhard Haeupler (INSAIT, University of Sofia “St. Kliment Ohridski” & ETH Zurich); D Ellis Hershkowitz (Brown University); Zihan Tan (DIMACS, Rutgers)<\/p>

                                                                                                                                                                                                                                                          1. How to Simulate Random Oracles with Auxiliary Input<\/li><\/ol>

                                                                                                                                                                                                                                                            Yevgeniy Dodis (New York University); Aayush Jain (CMU); Rachel (Huijia) Lin, Ji Luo (University of Washington); Daniel Wichs (Northeastern University, NTT Research)<\/p>

                                                                                                                                                                                                                                                            1. Tensor cumulants for statistical inference on invariant distributions<\/li><\/ol>

                                                                                                                                                                                                                                                              Dmitriy Kunisky (Yale University); Cristopher Moore (Santa Fe Institute); Alex Wein (UC Davis)<\/p>

                                                                                                                                                                                                                                                              1. Improved Condensers for Chor-Goldreich Sources<\/li><\/ol>

                                                                                                                                                                                                                                                                Jesse Goodman (UT Austin); Xin Li (Johns Hopkins University); David Zuckerman (University of Texas at Austin)<\/p>

                                                                                                                                                                                                                                                                1. Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians<\/li><\/ol>

                                                                                                                                                                                                                                                                  Jane Lee, Anay Mehrotra, Manolis Zampetakis (Yale University)<\/p>

                                                                                                                                                                                                                                                                  1. A Strong Separation for Adversarially Robust $\\ell_0$ Estimation for Linear Sketches<\/li><\/ol>

                                                                                                                                                                                                                                                                    Elena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A&M University)<\/p>

                                                                                                                                                                                                                                                                    1. Fully Dynamic Matching and Ordered Ruzsa-Szemer\\’edi Graphs<\/li><\/ol>

                                                                                                                                                                                                                                                                      Soheil Behnezhad, Alma Ghafari (Northeastern University)<\/p>

                                                                                                                                                                                                                                                                      1. Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting<\/li><\/ol>

                                                                                                                                                                                                                                                                        Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi (Stanford University)<\/p>

                                                                                                                                                                                                                                                                        1. Faster isomorphism testing of p-groups of Frattini class-2<\/li><\/ol>

                                                                                                                                                                                                                                                                          G\\’abor Ivanyos (Institute for Computer Science and Control, E\\”otv\\”os Lor\\’and Research Network (ELKH), Budapest, Hungary); Euan Jacob Mendoza (University of Technology Sydney); Youming Qiao (Center for Quantum Software and Information, University of Technology, Ultimo NSW 2007, Australia); Xiaorui Sun (University of Illinois at Chicago); Chuanqi Zhang (University of Technology Sydney)<\/p>

                                                                                                                                                                                                                                                                          1. Spectral Guarantees for Adversarial Streaming PCA<\/li><\/ol>

                                                                                                                                                                                                                                                                            Zhiyang Xun, Eric Price (The University of Texas at Austin)<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

                                                                                                                                                                                                                                                                            FOCS 2024 Accepted Papers FOCS 2024 Accepted Papers \u00a0O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold Tolson Bell, Alan Frieze (Carnegie Mellon University) A stronger bound for linear 3-LCC Tal Yankovitz (Tel Aviv University) Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric Zeyu Guo (The Ohio State […]<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1642","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/pages\/1642","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/comments?post=1642"}],"version-history":[{"count":0,"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/pages\/1642\/revisions"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/media?parent=1642"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}