FOCS 2024 Accepted Papers

FOCS 2024 Accepted Papers

1.  O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold

Tolson Bell, Alan Frieze (Carnegie Mellon University)

2. A stronger bound for linear 3-LCC

Tal Yankovitz (Tel Aviv University)

3. 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)

4. Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable

Sasank Mouli (Mahindra University)

5. Capacity Threshold for the Ising Perceptron

Brice Huang (MIT)

6. 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)

7. On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication

Yang Liu (IAS)

8. 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)

9. Efficient approximate unitary designs from random Pauli rotations

Jeongwan Haah (Microsoft Quantum); Yunchao Liu (UC Berkeley); Xinyu Tan (MIT)

10. Verifying Groups in Linear Time

Ohad Klein (Hebrew University); Ilan Komargodski (Hebrew University and NTT Research); Shai Evra, Shay Gadot (Hebrew University)

11. 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)

12. First-Order Model Checking on Monadically Stable Graph Classes

Jan Dreier (TU Wien); Ioannis Eleftheriadis (University of Cambridge); Nikolas Mählmann (University of Bremen); Rose McCarty (Georgia Institute of Technology); Michał Pilipczuk, Szymon Toruńczyk (University of Warsaw)

13. Proofs of Space with Maximal Hardness

Leonid Reyzin (Boston University)

14. A Dense Model Theorem for the Boolean Slice

Gil Kalai, Noam Lifshitz, Tamar Ziegler (Hebrew University of Jerusalem); Dor Minzer (MIT)

15. 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 Zürich); Sushant Sachdeva (University of Toronto / Google)

16. 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)

17. Power Series Composition in Near-Linear Time

Yasunori Kinoshita (Tokyo Institute of Technology); Baitian Li (Tsinghua University)

18. 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)

19. Obstructions to Erdős-Pósa Dualities for Minors

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

20. Optimal Bounds for Open Addressing Without Reordering

Martin Farach-Colton (NYU); Andrew Krapivin (Rutgers University); William Kuszmaul (Harvard University)

21. Tight Analyses of Ordered and Unordered Linear Probing

Mark Braverman (Princeton University); William Kuszmaul (Harvard University)

22. Tight Bounds for Classical Open Addressing

Michael Bender (Stony Brook University); William Kuszmaul (Harvard University); Renfei Zhou (Tsinghua University)

23. Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint

Niv Buchbinder (Tel Aviv University); Moran Feldman (University of Haifa)

24. 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)

25. High-Temperature Gibbs States are Unentangled and Efficiently Preparable

Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley)

26. Structure learning of Hamiltonians from real-time evolution

Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT); Ewin Tang (UC Berkeley)

27. Gaussian Approximation of Convex Sets by Intersections of Halfspaces

Anindya De (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University)

28. Constant Degree Direct Product Testers with Small Soundness

Mitali Bafna (MIT); Noam Lifshitz (Hebrew University); Dor Minzer (MIT)

29. On Approximating Cutwidth and Pathwidth

Nikhil Bansal (University of Michigan); Dor Katzelnick (Technion – Israel Institute of Technology); Roy Schwartz (Technion)

30. Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps

31. Gapped Clique Homology is QMA1-hard and contained in QMA

Robbie King (Caltech); Tamara Kohler (Stanford)

32. Boosting uniformity in quasirandom groups: faster and simpler

Emanuele Viola (NEU); Harm Derksern (Northeatern University); Chin Ho Lee (NCSU)

33. The sample complexity of smooth boosting and the tightness of the hardcore theorem

Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan (Stanford University)

34. Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Omar Alrabiah, Venkatesan Guruswami (UC Berkeley)

35. 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)

36. 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)

37. Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation

Shyam Narayanan (MIT); Václav Rozhoň (INSAIT, University of Sofia “St. Kliment Ohridski”); Jakub Tětek (INSAIT, University of Sofia “St. Kliment Ohridski”), Mikkel Thorup (University of Copenhagen)

38. 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)

39. Improved Distance (Sensitivity) Oracles with Subquadratic Space

Davide Bilò (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)

40. An Improved Line-Point Low-Degree Test

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi (Tata Institute of Fundamental Research); Madhu Sudan (Harvard University)

41. 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)

42. An Improved Pseudopolynomial Time Algorithm for Subset Sum

Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang (Zhejiang University)

43. 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)

44. Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Robert Andrews, Avi Wigderson (Institute for Advanced Study)

45. Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$ Worst-Case Update Time

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

46. Lempel-Ziv (LZ77) Factorization in Sublinear Time

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

47. 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 Czerwiński, Ł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)

48. Semi-Bandit Learning for Monotone Stochastic Optimization

Arpit Agarwal (Columbia University); Rohan Ghuge (Georgia Institute of Technology); Viswanath Nagarajan (University of Michigan)

49. 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)

50. Replicability in High Dimensional Statistics

Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye (University of California, San Diego)

51. 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)

52. Commitments are equivalent to one-way state generators

Rishabh Batra (CQT); Rahul Jain (National University of Singapore)

53. On the Existence of Seedless Condensers: Exploring the Terrain

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach (Cornell University)

54. Computing Approximate Centerpoints in Polynomial Time

Yeshwanth Cherapanamjeri (MIT)

55. Fast decision tree learning solves hard coding-theoretic problems

Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)

56. 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)

57. Quantum eigenvalue processing

Guang Hao Low (Microsoft Research); Yuan Su (Microsoft)

58. Quantum computational advantage with constant-temperature Gibbs sampling

Thiago Bergamaschi (UC Berkeley); Chi-Fang Chen (Caltech); Yunchao Liu (UC Berkeley)

59. Towards Instance-Optimal Euclidean Spanners

Hung Le (University of Massachusetts Amherst);  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)

60. Stochastic Online Correlated Selection

Ziyun Chen (Tsinghua University); Zhiyi Huang, Enze Sun (The University of Hong Kong)

61. Predict to Minimize Swap Regret for All Payoff-Bounded Tasks

Lunjia Hu (Stanford University); Yifan Wu (Northwestern University)

62. Simple constructions of linear-depth t-designs and pseudorandom unitaries

Tony Metger (ETH Zurich); Alexander Poremba (MIT); Makrand Sinha (UIUC); Henry Yuen (Columbia University)

63. Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning

Noah Golowich (MIT); Ankur Moitra (Math & CSAIL, MIT); Dhruv Rohatgi (MIT)

64. Optimal tradeoffs for estimating Pauli observables

Sitan Chen, Weiyuan Gong (Harvard University); Qi Ye (Tsinghua University)

65. 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)

66. Fast Mixing in Sparse Random Ising Models

Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman (MIT); David X Wu (UC Berkeley)

67. Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers

Sanjeev Khanna (University of Pennsylvania); Aaron (Louie) Putterman, Madhu Sudan (Harvard University)

68. 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)

69. Minor Containment and Disjoint Paths in almost-linear time

Tuukka Korhonen (University of Bergen); Michał Pilipczuk, Giannοs Stamoulis (University of Warsaw)

70. 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)

71. A Sampling Lovász Local Lemma for Large Domain Sizes

Chunyang Wang, Yitong Yin (Nanjing University)

72. Naively Sorting Evolving Data is Optimal and Robust

George Giakkoupis (INRIA); Marcos Kiwi (U. Chile); Dimitrios Los (University of Cambridge)

73. Tight Bounds for Sorting Under Partial Information

Ivor van der Hoog (Technical University of Denmark); Daniel Rutschmann (Technical University of Denmark, DTU)

74. Revisiting Agnostic PAC Learning

Steve Hanneke (Purdue University); Kasper Green Larsen (Aarhus University); Nikita Zhivotovskiy (UC Berkeley)

75. 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)

76. Decoding Quasi-Cyclic Quantum LDPC Codes

Louis Golowich, Venkatesan Guruswami (UC Berkeley)

77. Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares

Mikkel Abrahamsen, Jack Stade (University of Copenhagen, Denmark)

78. Semirandom Planted Clique and the Restricted Isometry Property

Jarosław Błasiok, Rares-Darius Buhai (ETH Zurich); Pravesh K Kothari (Princeton University and IAS); David Steurer (ETH Zurich)

79. A Lossless Deamortization for Dynamic Greedy Set Cover

Shay Solomon, Amitai Uzrad, Tianyi Zhang (Tel Aviv University)

80. 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)

81. Sampling, counting, and large deviations for triangle-free graphs near the critical density

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

82. Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Yotam Dikstein (IAS); Irit Dinur (Weizmann Institute of Science); Alexander Lubotzky (Weizmann)

83. The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2.

Jarosław Byrka (University of Wrocław); Fabrizio Grandoni (IDSIA, University of Lugano); Vera Traub (University of Bonn)

84. Chernoff-Hoeffding and Reverse Hypercontractivity on High Dimensional Expanders

Yotam Dikstein (IAS); Max Hopkins (UCSD)

85. 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)

86. Interactive Proofs for General Distribution Properties

Tal Herman (Weizmann Institute); Guy Rothblum (Apple)

87. Tight Bounds for the Zig-Zag Product

Gil Cohen, Gal Maor, Itay Cohen (Tel Aviv University)

88. 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)

89. 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 (Université Paris Cité, CNRS); Chris Schwiegelshohn (Aarhus University)

90. The Online Submodular Assignment Problem

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

91. Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

Pravesh K. Kothari (Princeton University and IAS); Peter Manohar (Carnegie Mellon University)

92. 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)

93. Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness

Jiatu Li, Edward Pyne (MIT); Roei Tell (University of Toronto)

94. 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)

95. 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)

96. The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds

Ryan Williams (MIT)

97. Computational Dynamical Systems

Jordan Cotler (Harvard University); Semon Rezchikov (Princeton University)

98. On the Complexity of Avoiding Heavy Elements

Zhenjian Lu, Igor C. Oliveira (University of Warwick); Hanlin Ren, Rahul Santhanam (University of Oxford)

99. 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)

100. Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis

Ilias Diakonikolas, Sushrut Karmalkar (UW-Madison); Shuo Pang (University of Copenhagen); Aaron Potechin (UChicago)

101. $\Pi_2^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem

Dmitriy Zhuk (Charles University, Prague)

102. Near-Optimal $(1+\epsilon)$-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs

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

103. Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach

Renato Ferreira Pinto Jr. (University of Waterloo)

104. On Robustness to k-wise Independence of Optimal Bayesian Mechanisms

Nick Gravin, Zhiqi Wang (Shanghai University of Finance and Economics)

105. 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)

106. Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS

Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich)

107. 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.)

108. On Pigeonhole Principles and Ramsey in TFNP

Siddhartha Jain, Jiawei Li (UT Austin); Robert Robere (McGill); Zhiyang Xun (UT Austin)

109. New investigations into noncommutative CSPs

Eric Culf (University of Waterloo); Hamoon Mousavi (University of California at Berkeley); Taro Spirig (University of Copenhagen)

110. Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems

Moïse Blanchard (MIT)

111. Strong vs. Weak Range Avoidance and the Linear Ordering Principle

Oliver Korten, Toniann Pitassi (Columbia University)

112. 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)

113. An Optimal Algorithm for Sorting Pattern-Avoiding Sequences

Michal Opler (Czech Technical University, Prague)

114. Succinct arguments for QMA from standard assumptions via compiled nonlocal games

Tony Metger (ETH Zurich); Anand Natarajan, Tina Zhang (MIT)

115. An XOR Lemma for Deterministic Communication Complexity

Siddharth Iyer, Anup Rao (University of Washington)

116. 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)

117. Canonical forms for matrix tuples in polynomial time

Youming Qiao (University of Technology Sydney); Xiaorui Sun (University of Illinois at Chicago)

118. Locally Stationary Distributions

Kuikui Liu, Sidhanth Mohanty (MIT); Prasad Raghavendra (UC Berkeley); Amit Rajaraman (MIT); David X Wu (UC Berkeley)

119. Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs

Xifan Yu, Dmitriy Kunisky (Yale University)

120. 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)

121. The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko (University of California, Los Angeles)

122. Jump operators, Interactive Proofs and Proof Complexity Generators

Erfan Khaniki (Institute of math of the CAS)

123. Optimal quantile estimation: beyond the comparison model

Mihir Singhal, Meghal Gupta, Hongxun Wu (UC Berkeley)

124. New Structures and Algorithms for Length-Constrained Expander Decompositions

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

125. How to Simulate Random Oracles with Auxiliary Input

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

126. Tensor cumulants for statistical inference on invariant distributions

Dmitriy Kunisky (Yale University); Cristopher Moore (Santa Fe Institute); Alex Wein (UC Davis)

127. Improved Condensers for Chor-Goldreich Sources

Jesse Goodman (UT Austin); Xin Li (Johns Hopkins University); David Zuckerman (University of Texas at Austin)

128. Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians

Jane Lee, Anay Mehrotra, Manolis Zampetakis (Yale University)

129. 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)

130. Fully Dynamic Matching and Ordered Ruzsa-Szemer\’edi Graphs

Soheil Behnezhad, Alma Ghafari (Northeastern University)

131. Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting

Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi (Stanford University)

132. Faster isomorphism testing of p-groups of Frattini class-2

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)

133. Spectral Guarantees for Adversarial Streaming PCA

Zhiyang Xun, Eric Price (The University of Texas at Austin)