Santosh Vempala is the chair of this FOCS 2024 conference. Here is the schedule of the talks. And in our next section are the accepted papers with links so you can see the results now.
His committee is:
Daniel Alabi, Columbia
Nima Anari, Stanford
Maryam Aliakbarpour, Rice
Xiaotie Deng, Peking University
Jelena Diakonikolas, Wisconsin
Alina Ene, BU
Funda Ergun, Indiana
Vipul Goyal, NTT Research
Sean Hallgren, Penn State
Russell Impagliazzo, UCSD
Varun Kanade, Oxford
Ravi Kannan, CMU
Bhavana Kanukurthi, IISc
Lap Chi Lau, Waterloo
Francois Le Gall, Nagoya
Andrea Lincoln, BU
Yang P. Liu, IAS and CMU
Daniel Lokshtanov, UCSB
Meena Mahajan, IMSc
Yury Makarychev, TTIC
Tal Malkin, Columbia
Dana Moshkovitz, UT Austin
Anand Natarajan, MIT
Alantha Newman, CNRS
Noam Nisan, Hebrew University
Huy Nguyen, Northeastern
Rafail Ostrovsky, UCLA
Ioannis Panageas, UC Irvine
Will Perkins, Georgia Tech
Prasad Raghavendra, Berkeley
Victor Reis, IAS
Rahul Santhanam, Oxford
Mohit Singh, Georgia Tech
Daniel Stefankovic, Rochester
David Steurer, ETH
Xiaorui Sun, UIC
Ewin Tang, Berkeley
Kavitha Telikepalli, TIFR Mumbai
Vera Traub, Bonn
Chris Umans, Caltech
Vinod Vaikuntanathan, MIT
Adrian Vetta, McGill
Yusu Wang, UCSD
Andre Wibisono, Yale
Mihalis Yannakakis, Columbia
Huacheng Yu, Princeton
Accepted Papers
O(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 University); Chaoping Xing, Chen Yuan (Shanghai Jiao Tong University); Zihan Zhang (The Ohio State University)
Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
Sasank Mouli (Mahindra University)
Capacity Threshold for the Ising Perceptron
Brice Huang (MIT)
{Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
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)
On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
Yang Liu (IAS)
Online Combinatorial Allocations and Auctions with Few Samples
Paul Duetting (Google); Thomas Kesselheim (University of Bonn); Brendan Lucier (Microsoft Research); Rebecca Reiffenhauser (University of Amsterdam); Sahil Singla (Georgia Tech)
Efficient approximate unitary designs from random Pauli rotations
Jeongwan Haah (Microsoft Quantum); Yunchao Liu (UC Berkeley); Xinyu Tan (MIT)
Verifying Groups in Linear Time
Ohad Klein (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research); Shai Evra, Shay Gadot (Hebrew University)
Fast list decoding of univariate multiplicity and folded Reed-Solomon codes
Rohan Goyal (Chennai Mathematical Institute); Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar (Tata Institute of Fundamental Research)
First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier (TU Wien); Ioannis Eleftheriadis (University of Cambridge); Nikolas Mahlmann (University of Bremen); Rose McCarty (Georgia Institute of Technology); Micha Pilipczuk, Szymon Toruczyk (University of Warsaw)
Proofs of Space with Maximal Hardness
Leonid Reyzin (Boston University)
A Dense Model Theorem for the Boolean Slice
Gil Kalai, Noam Lifshitz, Tamar Ziegler (Hebrew University of Jerusalem); Dor Minzer (MIT)
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
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 Zurich); Sushant Sachdeva (University of Toronto / Google)
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh (Carnegie Mellon University); Prasad Raghavendra (U.C. Berkeley)
Power Series Composition in Near-Linear Time
Yasunori Kinoshita (Tokyo Institute of Technology); Baitian Li (Tsinghua University)
The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution
Zhiyan Ding (University of California, Berkeley); Ethan N. Epperly (Caltech); Lin Lin (University of California, Berkeley); Ruizhe Zhang (Simons Institute for the Theory of Computing)
Obstructions to Erdos—Posa Dualities for Minors
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos (LIRMM, Univ. Montpellier, CNRS, France); Sebastian Wiederrecht (Discrete Mathematics Group, IBS, South Korea)
Optimal Bounds for Open Addressing Without Reordering
Martin Farach-Colton (NYU); Andrew Krapivin (Rutgers University); William Kuszmaul (Harvard University)
Tight Bounds for Classical Open Addressing
Michael Bender (Stony Brook University); William Kuszmaul (Harvard University); Renfei Zhou (Tsinghua University)
Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa)
Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
Shiri Ron (Weizmann Institute of Science); Clayton Thomas (Microsoft Research); S. Matthew Weinberg, Qianfan Zhang (Princeton University)
High-Temperature Gibbs States are Unentangled and Efficiently Preparable
Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math \& CSAIL, MIT); Ewin Tang (UC Berkeley)
Structure learning of Hamiltonians from real-time evolution
Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math \& CSAIL, MIT); Ewin Tang (UC Berkeley)
Gaussian Approximation of Convex Sets by Intersections of Halfspaces
Anindya De (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University)
Constant Degree Direct Product Testers with Small Soundness
Mitali Bafna (MIT); Noam Lifshitz (Hebrew University); Dor Minzer (MIT)
On Approximating Cutwidth and Pathwidth
Nikhil Bansal (University of Michigan); Dor Katzelnick (Technion —Israel Institute of Technology); Roy Schwartz (Technion)
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler (ETHZ \& Carnegie Mellon University); Richard Hladik, Vaclav Rozhon (ETH Zurich); Robert Tarjan (Princeton University); Jakub T?tek (BARC, University of Copenhagen)
Gapped Clique Homology is QMA1-hard and contained in QMA
Robbie King (Caltech); Tamara Kohler (Stanford)
Boosting uniformity in quasirandom groups: faster and simpler
Emanuele Viola (NEU); Harm Derksern (Northeatern University); Chin Ho Lee (NCSU)
The sample complexity of smooth boosting and the tightness of the hardcore theorem
Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan (Stanford University)
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
Omar Alrabiah, Venkatesan Guruswami (UC Berkeley)
Reverse Mathematics of Complexity Lower Bounds
Lijie Chen (University of California at Berkeley); Jiatu Li (Massachusetts Institute of Technology); Igor C. Oliveira (University of Warwick)
Agnostically Learning Multi-index Models with Queries
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)
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan (MIT); Vaclav Rozho (ETH Zurich); Jakub Ttek, Mikkel Thorup (University of Copenhagen)
Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
Sayan Bhattacharya (University of Warwick); Din Carmon (Tel Aviv University); Martin Costa (University of Warwick); Shay Solomon, Tianyi Zhang (Tel Aviv University)
Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilo (University of LAquila); 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)
An Improved Line-Point Low-Degree Test
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi (Tata Institute of Fundamental Research); Madhu Sudan (Harvard University)
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
Yaonan Jin (Huawei TCS Lab); Pinyan Lu (Shanghai University of Finance and Economics)
An Improved Pseudopolynomial Time Algorithm for Subset Sum
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
Sayan Bhattacharya, Martin Costa (University of Warwick); Naveen Garg (IIT Delhi); Silvio Lattanzi, Nikos Parotsidis (Google Research)
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
Robert Andrews, Avi Wigderson (Institute for Advanced Study)
Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$ Worst-Case Update Time
Bernhard Haeupler (ETH Zurich \& Carnegie Mellon University); Yaowei Long, Thatchaphol Saranurak (University of Michigan)
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa (Stony Brook University); Tomasz Kociumaka (Max Planck Institute for Informatics)
The Tractability Border of Reachability in Simple Vector Addition Systems with States
Dmitry Chistikov (Centre for Discrete Mathematics and its Applications (DIMAP) \& Department of Computer Science, University of Warwick, Coventry, UK); Wojciech Czerwiski, ukasz 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?grzycki (Saarland University and Max Planck Institute for Informatics, Saarbrucken, Germany)
Semi-Bandit Learning for Monotone Stochastic Optimization
Arpit Agarwal (Columbia University); Rohan Ghuge (Georgia Institute of Technology); Viswanath Nagarajan (University of Michigan)
Sparse graph counting and Kelley—Meka bounds for binary systems
Yuval Filmus (Technion—Israel Institute of Technology); Hamed Hatami (McGill University); Kaave Hosseini (University of Rochester); Esty Kelman (MIT, Boston University)
Replicability in High Dimensional Statistics
Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye (University of California, San Diego)
Efficient Unitary Designs from Random Sums and Permutations
Chi-Fang Chen (Caltech); Jordan Docter, Michelle Xu, Adam Bouland (Stanford); Fernando Brandao (Caltech); Patrick Hayden (Stanford)
Commitments are equivalent to one-way state generators
Rishabh Batra (CQT); Rahul Jain (National University of Singapore)
On the Existence of Seedless Condensers: Exploring the Terrain
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach (Cornell University)
Fast decision tree learning solves hard coding-theoretic problems
Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)
Nearly Optimal List Labeling
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)
Quantum eigenvalue processing
Guang Hao Low (Microsoft Research); Yuan Su (Microsoft)
Quantum computational advantage with constant-temperature Gibbs sampling
Thiago Bergamaschi (UC Berkeley); Chi-Fang Chen (Caltech); Yunchao Liu (UC Berkeley)
Towards Instance-Optimal Euclidean Spanners
Hung Le (University of Massachusetts Amherst); Shay Solomon (Tel Aviv University); Cuong Than (University of Massachusetts Amherst); Csaba D. Toth (California State University Northridge and Tufts University); Tianyi Zhang (Tel Aviv University)
Stochastic Online Correlated Selection
Ziyun Chen (Tsinghua University); Zhiyi Huang, Enze Sun (The University of Hong Kong)
Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
Lunjia Hu (Stanford University); Yifan Wu (Northwestern University)
Simple constructions of linear-depth t-designs and pseudorandom unitaries
Tony Metger (ETH Zurich); Alexander Poremba (MIT); Makrand Sinha (UIUC); Henry Yuen (Columbia University)
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Noah Golowich (MIT); Ankur Moitra (Math \& CSAIL, MIT); Dhruv Rohatgi (MIT)
Optimal tradeoffs for estimating Pauli observables
Sitan Chen, Weiyuan Gong (Harvard University); Qi Ye (Tsinghua University)
Dot-Product Proofs and Their Applications
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)
Fast Mixing in Sparse Random Ising Models
Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman (MIT); David X Wu (UC Berkeley)
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
Sanjeev Khanna (University of Pennsylvania); Aaron (Louie) Putterman, Madhu Sudan (Harvard University)
Efficient Certificates of Anti-Concentration Beyond Gaussians
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)
Minor Containment and Disjoint Paths in almost-linear time
Tuukka Korhonen (University of Bergen); Micha? Pilipczuk, Giann?s Stamoulis (University of Warsaw)
Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems
Hiroshi Hirai (Graduate School of Mathematics, Nagoya University); Keiya Sakabe (Graduate School of Information Science and Technology, The University of Tokyo)
A Sampling Lovasz Local Lemma for Large Domain Sizes
Chunyang Wang, Yitong Yin (Nanjing University)
Naively Sorting Evolving Data is Optimal and Robust
George Giakkoupis (INRIA); Marcos Kiwi (U. Chile); Dimitrios Los (University of Cambridge)
Tight Bounds for Sorting Under Partial Information
Ivor van der Hoog (Technical University of Denmark); Daniel Rutschmann (Technical University of Denmark, DTU)
Revisiting Agnostic PAC Learning
Steve Hanneke (Purdue University); Kasper Green Larsen (Aarhus University); Nikita Zhivotovskiy (UC Berkeley)
Computing the 3-edge-connected components of directed graphs in linear time
Evangelos Kosinas (ISTA (Institute of Science and Technology Austria)); Loukas Georgiadis (University of Ioannina); Giuseppe F. Italiano (LUISS University of Rome)
Decoding Quasi-Cyclic Quantum LDPC Codes
Louis Golowich, Venkatesan Guruswami (UC Berkeley)
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
Mikkel Abrahamsen, Jack Stade (University of Copenhagen, Denmark)
Semirandom Planted Clique and the Restricted Isometry Property
Jarosaw Basiok, Rares-Darius Buhai (ETH Zurich); Pravesh K Kothari (Princeton University and IAS); David Steurer (ETH Zurich)
A Lossless Deamortization for Dynamic Greedy Set Cover
Shay Solomon, Amitai Uzrad, Tianyi Zhang (Tel Aviv University)
Ramsey Theorems for Trees and a General Private Learning Implies Online Learning Theorem
Simone Fioravanti (Gran Sasso Science Institute); Steve Hanneke (Purdue University); Shay Moran, Hilla Schefler, Iska Tsubari (Technion)
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
Yotam Dikstein (IAS); Irit Dinur (Weizmann Institute of Science); Alexander Lubotzky (Weizmann)
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
Jarosaw Byrka (University of Wrocaw); Fabrizio Grandoni (IDSIA, University of Lugano); Vera Traub (University of Bonn)
Chernoff-Hoeffding and Reverse Hypercontractivity on High Dimensional Expanders
Yotam Dikstein (IAS); Max Hopkins (UCSD)
Three-edge-coloring projective planar cubic graphs:\\ A generalization of the Four Color Theorem
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)
Interactive Proofs for General Distribution Properties
Tal Herman (Weizmann Institute); Guy Rothblum (Apple)
Tight Bounds for the Zig-Zag Product
Gil Cohen, Gal Maor, Itay Cohen (Tel Aviv University)
Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications
Shuichi Hirahara (National Institute of Informatics); Zhenjian Lu (University of Warwick); Mikito Nanashima (Tokyo Institute of Technology)
Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
Nikhil Bansal (University of Michigan); Vincent Cohen-Addad (Google Research, France); Milind Prabhu (University of Michigan); David Saulpic (Universite Paris Cite, CNRS); Chris Schwiegelshohn (Aarhus University)
The Online Submodular Assignment Problem
Sherry Sarkar, Daniel Hathcock, Mik Zlatin (Carnegie Mellon University); Billy Jin (Cornell University); Kalen Patton (Georgia Tech)
Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Pravesh K. Kothari (Princeton University and IAS); Peter Manohar (Carnegie Mellon University)
Efficient Approximation of Hypertree Width
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)
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
Jiatu Li, Edward Pyne (MIT); Roei Tell (University of Toronto)
Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
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)
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
Friedrich Eisenbrand (EPFL); Lars Rohwedder (Maastricht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)
The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds
Ryan Williams (MIT)
Trading Determinism for Noncommutativity in Edmonds Problem
Arvind (Institute of Mathematical Sciences (HBNI), and CMI); Abhranil Chatterjee (Indian Statistical Institute, Kolkata); Partha Mukhopadhyay (Chennai Mathematical Institute)
Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Sushrut Karmalkar (UW-Madison); Shuo Pang (University of Copenhagen); Aaron Potechin (UChicago)
$\Pi_2^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
Dmitriy Zhuk (Charles University, Prague)
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
Renato Ferreira Pinto Jr. (University of Waterloo)
On Robustness to k-wise Independence of Optimal Bayesian Mechanisms
Nick Gravin, Zhiqi Wang (Shanghai University of Finance and Economics)
Expansion of high-dimensional cubical complexes with application to quantum locally Testable codes
Irit Dinur (Weizmann); Ting-Chun Lin (UCSD); Thomas Vidick (Weizmann Institute of Science)
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)
A computational test of quantum contextuality, and even simpler proofs of quantumness
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.)
On Pigeonhole Principles and Ramsey in TFNP
Siddhartha Jain, Jiawei Li (UT Austin); Robert Robere (McGill); Zhiyang Xun (UT Austin)
New investigations into noncommutative CSPs
Eric Culf (University of Waterloo); Hamoon Mousavi (University of California at Berkeley); Taro Spirig (University of Copenhagen)
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Moise Blanchard (MIT)
Strong vs. Weak Range Avoidance and the Linear Ordering Principle
Oliver Korten, Toniann Pitassi (Columbia University)
Novel properties of hierarchical probabilistic partitions and their algorithmic applications
Sandip Banerjee (IDSIA, USI-SUPSI, Lugano, Switzerland); Yair Bartal (Heberew University); Lee-Ad Gottlieb (Ariel University); Alon Hovav (Hebrew University)
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
Michal Opler (Czech Technical University, Prague)
Succinct arguments for QMA from standard assumptions via compiled nonlocal games
Tony Metger (ETH Zurich); Anand Natarajan, Tina Zhang (MIT)
An XOR Lemma for Deterministic Communication Complexity
Siddharth Iyer, Anup Rao (University of Washington)
Certifying almost all quantum states with few single-qubit measurements
Hsin-Yuan Huang (Google Quantum AI, Caltech); John Preskill (Caltech, AWS Center for Quantum Computing); Mehdi Soleimanifar (Caltech)
Locally Stationary Distributions
Kuikui Liu, Sidhanth Mohanty (MIT); Prasad Raghavendra (UC Berkeley); Amit Rajaraman (MIT); David X Wu (UC Berkeley)
Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Xifan Yu, Dmitriy Kunisky (Yale University)
Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
Krishnamurthy (Dj) Dvijotham (Google DeepMind); H. Brendan McMahan (Google); Krishna Pillutla (IIT Madras); Thomas Steinke, Abhradeep Guha Thakurta (Google DeepMind)
The Communication Complexity of Approximating Matrix Rank
Alexander A. Sherstov, Andrey A. Storozhenko (University of California, Los Angeles)
Jump operators, Interactive Proofs and Proof Complexity Generators
Erfan Khaniki (Institute of math of the CAS)
Optimal quantile estimation: beyond the comparison model
Mihir Singhal, Meghal Gupta, Hongxun Wu (UC Berkeley)
New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler (ETH Zurich \& CMU); D Ellis Hershkowitz (Brown University); Zihan Tan (DIMACS, Rutgers)
Tensor cumulants for statistical inference on invariant distributions
Dmitriy Kunisky (Yale University); Cristopher Moore (Santa Fe Institute); Alex Wein (UC Davis)
Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians
Jane Lee, Anay Mehrotra, Manolis Zampetakis (Yale University)
A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
Elena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A\&M University)
Fully Dynamic Matching and Ordered Ruzsa—Szemeredi Graphs
Soheil Behnezhad, Alma Ghafari (Northeastern University)
Faster isomorphism testing of p-groups of Frattini class-2
Gabor Ivanyos (Institute for Computer Science and Control, Eotvos Lorand 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)
Spectral Guarantees for Adversarial Streaming PCA
Zhiyang Xun, Eric Price (The University of Texas at Austin)
Open Problems
I have always loved the FOCS conference. Hope that you can be there this October. I hope also to be there too.
