STOC 2023
55th Annual ACM Symposium on Theory of Computing (STOC 2023)
Powered by
Conference Publishing Consulting

55th Annual ACM Symposium on Theory of Computing (STOC 2023), June 20–23, 2023, Orlando, FL, USA

STOC 2023 – Proceedings

Contents - Abstracts - Authors

Frontmatter

Title Page


Welcome from the Program Chair
The papers in this volume were presented at the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). The conference was held in Orlando, Florida, as part of the ACM Federated Computing Research Conference (FCRC). The papers were presented as live talks during sessions held between June 20-23, 2023. STOC 2023 was part of Theory Fest, which included a range of panels, meetings, and social activities. FCRC 2023 featured plenary talks given by Kunle Olukotun, Margaret Martonosi, Shafi Goldwasser, Don Towsley, and Torsten Hoefler.

STOC 2023 Conference Organization
Conference organization (committees, including PC and external reviewers)

Sponsors
Sponsors page

Session 1A

Almost Chor-Goldreich Sources and Adversarial Random Walks
Dean Doron ORCID logo, Dana Moshkovitz ORCID logo, Justin Oh ORCID logo, and David Zuckerman ORCID logo
(Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA)
A Chor–Goldreich (CG) source is a sequence of random variables X = X1 ∘ … ∘ Xt, where each Xi ∼ {0,1}d and Xi has δ d min-entropy conditioned on any fixing of X1 ∘ … ∘ Xi−1. The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each Xi to only have conditional Shannon entropy δ d.
We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources: We construct a deterministic condenser that on input X, outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ {0,1}m for m ≈ δ dt with min-entropy mO(1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders.
Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to X1∘ … ∘ Xt, accumulate most of the entropy in X.

Publisher's Version
A New Berry-Esseen Theorem for Expander Walks
Louis Golowich ORCID logo
(University of California at Berkeley, Berkeley, USA)
We prove that the sum of t boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of O(λ/t1/2−o(1)), where λ is the second largest eigenvalue of the random walk matrix in absolute value. To the best of our knowledge, among known Berry-Esseen bounds for Markov chains, our result is the first to show convergence in total variation distance, and is also the first to incorporate a linear dependence on expansion λ. In contrast, prior Markov chain Berry-Esseen bounds showed a convergence rate of O(1/√t) in weaker metrics such as Kolmogorov distance.
Our result also improves upon prior work in the pseudorandomness literature, which showed that the total variation distance is O(λ) when the approximating distribution is taken to be a binomial distribution. We achieve the faster O(λ/t1/2−o(1)) convergence rate by generalizing the binomial distribution to discrete normals of arbitrary variance. We specifically construct discrete normals using a random walk on an appropriate 2-state Markov chain. Our bound can therefore be viewed as a regularity lemma that reduces the study of arbitrary expanders to a small class of particularly simple expanders.

Publisher's Version
Near-Optimal Derandomization of Medium-Width Branching Programs
Aaron (Louie) Putterman ORCID logo and Edward Pyne ORCID logo
(Harvard University, USA; Massachusetts Institute of Technology, USA)
We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length n and width w in space
Õ(logn+√logn
·logw).
In particular, we obtain an almost optimal space Õ(logn) derandomization of programs up to width w=2√logn. Previously, the best known space complexity for this problem was
O(min{logn· logw,log3/2n+√logn
· logw})
via the classic algorithms of Savitch (JCSS 1970) and Saks and Zhou (JCSS 1999), which only achieve space Õ(logn) for w=polylog(n).
We prove this result by showing that a variant of the Saks-Zhou algorithm developed by Cohen, Doron, and Sberlo (ECCC 2022) still works without executing one of the steps in the algorithm, the so-called random shift step. This allows us to extend their algorithm from computing the nth power of a w× w stochastic matrix to multiplying n distinct w× w stochastic matrices with no degradation in space consumption. In the regime where wn, we also show that our approach can achieve parameters matching those of the original Saks-Zhou algorithm (with no loglog factors). Finally, we show that for w≤ 2√logn, an algorithm even simpler than our algorithm and that of Saks and Zhou achieves space O(log3/2 n).

Publisher's Version
Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Gil Cohen ORCID logo, Dean Doron ORCID logo, Ori Sberlo ORCID logo, and Amnon Ta-Shma ORCID logo
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space complexity as it constitutes the main route towards resolving the BPL vs. L problem. The seminal work by Saks and Zhou [JCSS ’99] gives a deterministic algorithm for approximating the product of n stochastic matrices of dimension w × w in space O(log3/2n + √logn · logw). The first improvement upon Saks–Zhou was achieved by Hoza [RANDOM ’21] who gave a logarithmic improvement in the n=poly(w) regime, attaining O(1/√loglogn · log3/2n) space.
We give the first polynomial improvement over Saks and Zhou’s algorithm. Our algorithm achieves space complexity of O(logn + √logn· logw). In particular, in the regime logn > log2 w, our algorithm runs in nearly-optimal O(logn) space, improving upon the previous best O(log3/2n).
To obtain our result for the special case of matrix powering, we harness recent machinery from time- and space-bounded Laplacian solvers to the Saks–Zhou framework and devise an intricate precision-alternating recursive scheme. This enables us to bypass the bottleneck of paying logn-space per recursion level. The general case of iterated matrix multiplication poses several additional challenges, the substantial of which is handled by devising an improved shift and truncate mechanism. The new mechanism is made possible by a novel use of the Richardson iteration.

Publisher's Version
Extractors for Images of Varieties
Zeyu Guo ORCID logo, Ben Lee Volk ORCID logo, Akhil Jalan ORCID logo, and David Zuckerman ORCID logo
(Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA)
We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map f : Fqr → Fqn to an element sampled uniformly at random from a k-dimensional variety V ⊆ Fqr. This class of sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012).
Assuming certain natural non-degeneracy conditions on the map f and the variety V, which in particular ensure that the source has enough min-entropy, we extract almost all the min-entropy of the distribution. Unlike the Dvir–Gabizon–Wigderson and Dvir results, our construction works over large enough finite fields of arbitrary characteristic. One key part of our construction is an improved deterministic rank extractor for varieties. As a by-product, we obtain explicit Noether normalization lemmas for affine varieties and affine algebras.
Additionally, we generalize a construction of affine extractors with exponentially small error due to Bourgain, Dvir and Leeman (Comput. Complex. 2016) by extending it to all finite prime fields of quasipolynomial size.

Publisher's Version
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems
Lijie Chen ORCID logo and Roei Tell ORCID logo
(University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of derandomizing interactive proofs systems.
First, we show conditional derandomization of MA and of AM with optimal runtime overhead, where optimality is under the #NSETH assumption. Specifically, denote by AMTIME[⇌ c][T] a protocol with c turns of interaction in which the verifier runs in polynomial time T. We prove that, for every constant є>0,
MATIME[T] ⊆ NTIME[T2+є] ,  
AMTIME[⇌ c][T] ⊆ NTIME[n· T⌈ c/2 ⌉ + є] ;  
assuming the existence of properties of Boolean functions that can be recognized quickly from the function’s truth-table such that functions with the property are hard for proof systems that receive near-maximal amount of non-uniform advice.
To obtain faster derandomization, we introduce the notion of a deterministic effective argument system. This is an NP-type proof system in which the verifier is deterministic, and the soundness is relaxed to be computational, as follows: For every probabilistic polynomial-time adversary P, the probability that P finds an input xL and misleading proof π such that V(x,π)=1 is negligible.
Under strong hardness assumptions, we prove that any constant-round doubly efficient proof system can be compiled into a deterministic effective argument system, with essentially no time overhead. As one corollary, under strong hardness assumptions, for every є>0 there is a deterministic verifier V that gets an n-bit formula Φ of size 2o(n), runs in time 2є · n, and satisfies the following: An honest prover running in time 2O(n) can print, for every Φ, a proof π such that V(Φ,π) outputs the number of satisfying assignments for Φ; and for every adversary P running in time 2O(n), the probability that P finds Φ and π such that V(Φ,π) outputs an incorrect count is 2−ω(n).

Publisher's Version
Hardness Self-Amplification: Simplified, Optimized, and Unified
Shuichi Hirahara ORCID logo and Nobutaka Shimizu ORCID logo
(National Institute of Informatics, Japan; Tokyo Institute of Technology, Japan)
Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove hardness self-amplification for popular problems, such as matrix multiplication, online matrix-vector multiplication, triangle counting of Erdős–Rényi random graphs, and the planted clique problem. As a corollary, we obtain the first search-to-decision reduction for the planted clique problem in a high-error regime. Our framework simplifies, improves, and unifies the previous hardness self-amplification results.
Our approach uses a one-query upward self-reduction, that is, a reduction that maps a small instance to a large instance. We demonstrate that this reduction yields hardness self-amplification if the bipartite graph, whose left and right vertices correspond to small and large instances, respectively, has an expansion property. Our key technical contribution is to show the expansion property of the bipartite graph naturally constructed from the planted clique problem by using the coupling method of Markov chains.

Publisher's Version
Sum-of-Squares Lower Bounds for Densest k-Subgraph
Chris Jones ORCID logo, Aaron Potechin ORCID logo, Goutham Rajendran ORCID logo, and Jeff Xu ORCID logo
(Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA)
Given a graph and an integer k, Densest k-Subgraph is the algorithmic task of finding the subgraph on k vertices with the maximum number of edges. This is a fundamental problem that has been subject to intense study for decades, with applications spanning a wide variety of fields. The state-of-the-art algorithm is an O(n1/4 + )-factor approximation (for any > 0) due to Bhaskara et al. [STOC ’10]. Moreover, the so-called log-density framework predicts that this is optimal, i.e. it is impossible for an efficient algorithm to achieve an O(n1/4 − )-factor approximation. In the average case, Densest k-Subgraph is a prototypical noisy inference task which is conjectured to exhibit a statistical-computational gap.
In this work, we provide the strongest evidence yet of hardness for Densest k-Subgraph by showing matching lower bounds against the powerful Sum-of-Squares (SoS) algorithm, a meta-algorithm based on convex programming that achieves state-of-art algorithmic guarantees for many optimization and inference problems. For kn1/2, we obtain a degree nδ SoS lower bound for the hard regime as predicted by the log-density framework.
To show this, we utilize the modern framework for proving SoS lower bounds on average-case problems pioneered by Barak et al. [FOCS ’16]. A key issue is that small denser-than-average subgraphs in the input will greatly affect the value of the candidate pseudoexpectation operator around the subgraph. To handle this challenge, we devise a novel matrix factorization scheme based on the positive minimum vertex separator. We then prove an intersection tradeoff lemma to show that the error terms when using this separator are indeed small.

Publisher's Version
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Elchanan Mossel ORCID logo, Allan Sly ORCID logo, and Youngtak Sohn ORCID logo
(Massachusetts Institute of Technology, USA; Princeton University, USA)
In this paper, we rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (2011) regarding the block model, in particular in the case of q=3 and q=4 communities.
We prove that for q=3 and q=4 there is no computational-statistical gap if the average degree is above some constant by showing that it is information theoretically impossible to detect below the Kesten-Stigum bound. We proceed by showing that for the broadcast process on Galton-Watson trees, reconstruction is impossible for q=3 and q=4 if the average degree is sufficiently large. This improves on the result of Sly (2009), who proved similar results for d-regular trees when q=3. Our analysis of the critical case q=4 provides a detailed picture showing that the tightness of the Kesten-Stigum bound in the antiferromagnetic regime depends on the average degree of the tree. We also prove that for q≥ 5, the Kesten-Stigum bound is not sharp.
Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborová (2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian, and Zdeborová (2019). Our proofs are based on a new general coupling of the tree and graph processes and on a refined analysis of the broadcast process on the tree.

Publisher's Version
Parallel Discrete Sampling via Continuous Walks
Nima Anari ORCID logo, Yizhi Huang ORCID logo, Tianyu Liu ORCID logo, Thuy-Duong Vuong ORCID logo, Brian Xu ORCID logo, and Katherine Yu ORCID logo
(Stanford University, USA; Tsinghua University, China)
We develop a framework for sampling from discrete distributions µ on the hypercube {± 1}n by sampling from continuous distributions supported on ℝn obtained by convolution with spherical Gaussians. We show that for well-studied families of discrete distributions µ, the result of the convolution is well-conditioned log-concave, whenever the Gaussian’s variance is above an O(1) threshold. We plug off-the-shelf continuous sampling methods into our framework to obtain novel discrete sampling algorithms. Additionally, we introduce and study a crucial notion of smoothness for discrete distributions that we call transport stability, which we use to control the propagation of error in our framework. We expect transport stability to be of independent interest, as we connect it to constructions of optimally mixing local random walks and concentration inequalities. As our main application, we resolve open questions raised by Anari, Hu, Saberi, and Schild on the parallel sampling of distributions which admit parallel counting. We show that determinantal point processes can be sampled via RNC algorithms, that is in time log(n)O(1) using nO(1) processors. For a wider class of distributions, we show our framework yields Quasi-RNC sampling, i.e., log(n)O(1) time using nO(logn) processors. This wider class includes non-symmetric determinantal point processes and random Eulerian tours in digraphs, the latter nearly resolving another open question raised by prior work.

Publisher's Version
Sampling from Convex Sets with a Cold Start using Multiscale Decompositions
Hariharan Narayanan ORCID logo, Amit Rajaraman ORCID logo, and Piyush Srivastava ORCID logo
(TIFR, Mumbai, India; IIT Bombay, India)
Running a random walk in a convex body K⊆ℝn is a standard approach to sample approximately uniformly from the body. The requirement is that from a suitable initial distribution, the distribution of the walk comes close to the uniform distribution πK on K after a number of steps polynomial in n and the aspect ratio R/r (i.e., when rB2KRB2). Proofs of rapid mixing of such walks often require the probability density η0 of the initial distribution with respect to πK to be at most poly(n): this is called a “warm start”. Achieving a warm start often requires non-trivial pre-processing before starting the random walk. This motivates proving rapid mixing from a “cold start”, wherein η0 can be as high as exp(poly(n)). Unlike warm starts, a cold start is usually trivial to achieve. However, a random walk need not mix rapidly from a cold start: an example being the well-known “ball walk”. On the other hand, Lovász and Vempala proved that the “hit-and-run” random walk mixes rapidly from a cold start. For the related coordinate hit-and-run (CHR) walk, which has been found to be promising in computational experiments, rapid mixing from a warm start was proved only recently but the question of rapid mixing from a cold start remained open.
We construct a family of random walks inspired by classical decompositions of subsets of ℝn into countably many axis-aligned dyadic cubes. We show that even with a cold start, the mixing times of these walks are bounded by a polynomial in n and the aspect ratio. Our main technical ingredient is an isoperimetric inequality for K for a metric that magnifies distances between points close to the boundary of K. As a corollary, we show that the CHR walk also mixes rapidly from a cold start.

Publisher's Version

Session 1B

On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi ORCID logo, Soheil Behnezhad ORCID logo, Sanjeev Khanna ORCID logo, and Huan Li ORCID logo
(Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA)
We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs:
A deterministic single-pass streaming algorithm that finds a (1−o(1))-approximate matching in o(n2) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm.
A randomized fully dynamic algorithm that with high probability maintains a (1−o(1))-approximate matching in o(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one.
Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log* n)Θ(1) factor. Nevertheless, in each case, they show that the “right” answer to the problem is not what is dictated by the previous bounds.
Finally, in the streaming model, we also present a randomized (1−o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemerédi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

Publisher's Version
Optimal Eigenvalue Approximation via Sketching
William Swartworth ORCID logo and David P. Woodruff ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Carnegie Mellon University, USA)
Given a symmetric matrix A, we show from the simple sketch GAGT, where G is a Gaussian matrix with k = O(1/є2) rows, that there is a procedure for approximating all eigenvalues of A simultaneously to within є ||A||F additive error with large probability. Unlike the work of (Andoni, Nguyen, SODA, 2013), we do not require that A is positive semidefinite and therefore we can recover sign information about the spectrum as well. Our result also significantly improves upon the sketching dimension of recent work for this problem (Needell, Swartworth, Woodruff FOCS 2022), and in fact gives optimal sketching dimension. Our proof develops new properties of singular values of GA for a k × n Gaussian matrix G and an n × n matrix A which may be of independent interest. Additionally we achieve tight bounds in terms of matrix-vector queries. Our sketch can be computed using O(1/є2) matrix-vector multiplies, and by improving on lower bounds for the so-called rank estimation problem, we show that this number is optimal even for adaptive matrix-vector queries.

Publisher's Version
Streaming Euclidean MST to a Constant Factor
Xi ChenORCID logo, Vincent Cohen-Addad ORCID logo, Rajesh Jayaram ORCID logo, Amit Levi ORCID logo, and Erik Waingarten ORCID logo
(Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA)
We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an n-point set X ⊂ ℝd. In the streaming model, the points in X can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, (1+є) approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG ’05]. However, for high dimensional spaces the best known approximation for this problem was Õ(logn), due to [Chen, Jayaram, Levi, Waingarten, STOC ’22], improving on the prior O(log2 n) bound due to [Indyk, STOC ’04] and [Andoni, Indyk, Krauthgamer, SODA ’08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any є≥ 1, our algorithm achieves an Õ(є−2) approximation in nO(є) space.
We complement this by proving that any single pass algorithm which obtains a better than 1.10-approximation must use Ω(√n) space, demonstrating that (1+є) approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that (1+є) approximations are possible in sublinear space with O(1/є) passes over the stream. More generally, for any α ≥ 2, we give a α-pass streaming algorithm which achieves a (1+O(logα + 1/ α є)) approximation in nO(є) dO(1) space.
All our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first (1+є)-approximation to Euclidean MST in a constant number of rounds in the MPC model. Previously, such a result was only known for low-dimensional space [Andoni, Nikolov, Onak, Yaroslavtsev, STOC ’15], or required either O(logn) rounds or a O(logn) approximation.

Publisher's Version
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Xiaoyu Chen ORCID logo, Shaofeng H.-C. Jiang ORCID logo, and Robert Krauthgamer ORCID logo
(Peking University, China; Weizmann Institute of Science, Israel)
Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in ℝd, in the model of dynamic geometric streams, where the input X ⊆ [Δ]d is presented as a sequence of point insertions and deletions. Previously, Frahling and Sohler [STOC 2005] designed a (1+є)-approximation algorithm for the low-dimensional regime, i.e., it uses space exp(d).
To tackle this problem in the high-dimensional regime, which is of growing interest, one must improve the dependence on the dimension d, ideally to space complexity poly−1 d logΔ). Lammersen, Sidiropoulos, and Sohler [WADS 2009] proved that Euclidean Max-Cut admits dimension reduction with target dimension d′ = poly−1). Combining this with the aforementioned algorithm that uses space exp(d′), they obtain an algorithm whose overall space complexity is indeed polynomial in d, but unfortunately exponential in є−1.
We devise an alternative approach of data reduction, based on importance sampling, and achieve space bound poly−1 d logΔ), which is exponentially better (in є) than the dimension-reduction approach. To implement this scheme in the streaming model, we employ a randomly-shifted quadtree to construct a tree embedding. While this is a well-known method, a key feature of our algorithm is that the embedding’s distortion O(dlogΔ) affects only the space complexity, and the approximation ratio remains 1+є.

Publisher's Version
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi ORCID logo and Janani Sundaresan ORCID logo
(Rutgers University, USA)
We continue the study of the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous applications in proving streaming lower bounds. In the noisy gap cycle counting problem (NGC), there is a small integer k ≥ 1 and an n-vertex graph consisted of vertex-disjoint union of either k-cycles or 2k-cycles, plus O(n/k) disjoint paths of length k−1 in both cases (“noise”). The edges of this graph are partitioned between Alice and Bob whose goal is to decide which case the graph belongs to with minimal communication from Alice to Bob.

We study the robust communication complexity of NGC—à la Chakrabarti, Cormode, and McGregor [STOC 2008]—namely, when edges are partitioned randomly between the players. This is in contrast to all prior work on gap cycle counting problems in adversarial partitions. While NGC can be solved trivially with zero communication when k < logn, we prove that when k is a constant factor larger than logn, the robust (one-way) communication complexity of NGC is Ω(n) bits.

As a corollary of this result, we can prove several new graph streaming lower bounds for random order streams. In particular, we show that any streaming algorithm that for every > 0 estimates the number of connected components of a graph presented in a random order stream to within an · n additive factor requires 2Ω(1/є) space, settling a conjecture of Peng and Sohler [SODA 2018]. We further discuss new implications of our lower bounds to other problems such as estimating size of maximum matchings and independent sets on planar graphs, random walks, as well as to stochastic streams.

Publisher's Version
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati ORCID logo, Yang P. LiuORCID logo, and Aaron Sidford ORCID logo
(University of Washington, USA; Stanford University, USA)
We present an algorithm that given any n-vertex, m-edge, rank r hypergraph constructs a spectral sparsifier with O(n ε−2 logn logr) hyperedges in nearly-linear O(mr) time. This improves in both size and efficiency over a line of work [Bansal-Svensson-Trevisan 2019, Kapralov-Krauthgamer-Tardos-Yoshida 2021] for which the previous best size was O(min{n ε−4 log3 n,nr3 ε−2 logn}) and runtime was O(mr + nO(1)).

Publisher's Version
Spectral Hypergraph Sparsification via Chaining
James R. Lee ORCID logo
(University of Washington, USA)
In a hypergraph on n vertices where D is the maximum size of a hyperedge, there is a weighted hypergraph spectral -sparsifier with at most O(−2 log(D) · n logn) hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve O(−4 n (logn)3), as well as the bound O(−2 D3 n logn) obtained by Bansal, Svensson, and Trevisan (2019). The same sparsification result was obtained independently by Jambulapati, Liu, and Sidford (2022).

Publisher's Version
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Sudatta Bhattacharya ORCID logo and Michal Koucký ORCID logo
(Charles University, Prague, Czechia)
In this paper we provide a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ. Our decomposition can be used to design a sketch of size O(k2) for edit distance, and also a rolling sketch for edit distance of size O(k2). The rolling sketch allows to update the sketched string by appending a symbol or removing a symbol from the beginning of the string.

Publisher's Version
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester
Hadley Black ORCID logo, Deeparnab Chakrabarty ORCID logo, and C. Seshadhri ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA)
The problem of testing monotonicity for Boolean functions on the hypergrid, f:[n]d → {0,1} is a classic topic in property testing. When n=2, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making O−2d) queries. Up to polylog d and ε factors, this bound matches the Ω(√d)-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any n > 2, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a O(d5/6)-query upper bound (SODA 2020), quite far from the √d bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant n, up to poly−1logd) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making O−2nd) queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid [n]d. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.

Publisher's Version
Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation
Mahsa Derakhshan ORCID logo, Naveen Durvasula ORCID logo, and Nika Haghtalab ORCID logo
(Northeastern University, USA; University of California at Berkeley, Berkeley, USA)
We study the stochastic vertex cover problem. In this problem, G = (V, E) is an arbitrary known graph, and G is an unknown random subgraph of G where each edge e is realized independently with probability p. Edges of G can only be verified using edge queries. The goal in this problem is to find a minimum vertex cover of G using a small number of queries.
Our main result is designing an algorithm that returns a vertex cover of G with size at most (3/2+є) times the expected size of the minimum vertex cover, using only O(np) non-adaptive queries. This improves over the best-known 2-approximation algorithm by Behnezhad, Blum and Derakhshan [SODA’22] who also show that Ω(n/p) queries are necessary to achieve any constant approximation.
Our guarantees also extend to instances where edge realizations are not fully independent. We complement this upperbound with a tight 3/2-approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations.

Publisher's Version
Sublinear Algorithms for (1.5+𝜖)-Approximate Matching
Sayan Bhattacharya ORCID logo, Peter Kiss ORCID logo, and Thatchaphol SaranurakORCID logo
(University of Warwick, UK; MPI-INF, Germany; University of Michigan, USA)
We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad ‍[FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. ‍[SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time.
We give a strong affirmative answer to this open problem by showing (1.5+є)-approximation algorithms that run in n2−Θ(є2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP’15, SODA’16], distributed [Assadi et al. SODA’19] and streaming [Bernstein ICALP’20] settings, but never before in the sublinear setting.

Publisher's Version
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad ORCID logo, Mohammad Roghani ORCID logo, and Aviad Rubinstein ORCID logo
(Northeastern University, USA; Stanford University, USA)
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of [Behnezhad; FOCS’21] obtains a 1/2-approximation in O(n) time for n-vertex graphs. A more recent algorithm by [Behnezhad, Roghani, Rubinstein, and Saberi; SODA’23] obtains a slightly-better-than-1/2 approximation in O(n1+є) time (for arbitrarily small constant ε>0). On the lower bound side, [Parnas and Ron; TCS’07] showed 15 years ago that obtaining any constant approximation of maximum matching size requires Ω(n) time. Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive since then.
In this paper, we prove the first super-linear in n lower bound for this problem. We show that at least n1.2 − o(1) queries in the adjacency list model are needed for obtaining a (2/3 + Ω(1))-approximation of the maximum matching size. This holds even if the graph is bipartite and is promised to have a matching of size Θ(n). Our lower bound argument builds on techniques such as correlation decay that to our knowledge have not been used before in proving sublinear time lower bounds.
We complement our lower bound by presenting two algorithms that run in strongly sublinear time of n2−Ω(1). The first algorithm achieves a (2/3−ε)-approximation (for any arbitrarily small constant ε>0); this significantly improves prior close-to-1/2 approximations. Our second algorithm obtains an even better approximation factor of (2/3+Ω(1)) for bipartite graphs. This breaks 2/3-approximation which has been a barrier in various settings of the matching problem, and importantly shows that our n1.2−o(1) time lower bound for (2/3+Ω(1))-approximations cannot be improved all the way to n2−o(1).

Publisher's Version

Session 1C

Almost-Optimal Sublinear Additive Spanners
Zihan Tan ORCID logo and Tianyi Zhang ORCID logo
(Rutgers University, USA; Tel Aviv University, Israel)
Given an undirected unweighted graph G = (V, E) on n vertices and m edges, a subgraph HG is a spanner of G with stretch function f: ℝ+ → ℝ+, iff for every pair s, t of vertices in V, distH(s, t)≤ f(distG(s, t)). When f(d) = d + o(d), H is called a sublinear additive spanner; when f(d) = d + o(n), H is called an additive spanner, and f(d) − d is usually called the additive stretch of H.
As our primary result, we show that for any constant δ>0 and constant integer k≥ 2, every graph on n vertices has a sublinear additive spanner with stretch function f(d)=d+O(d1−1/k) and O(n1+1+δ/2k+1−1) edges. When k = 2, this improves upon the previous spanner construction with stretch function f(d) = d + O(d1/2) and Õ(n1+3/17) edges [Chechik, 2013]; for any constant integer k≥ 3, this improves upon the previous spanner construction with stretch function f(d) = d + O(d1−1/k) and O(n1+(3/4)k−2/7 − 2· (3/4)k−2) edges [Pettie, 2009]. Most importantly, the size of our spanners almost matches the lower bound of Ω(n1+1/2k+1−1) [Abboud, Bodwin, Pettie, 2017].
As our second result, we show a new construction of additive spanners with stretch O(n0.403) and O(n) edges, which slightly improves upon the previous stretch bound of O(n3/7+є) achieved by linear-size spanners [Bodwin and Vassilevska Williams, 2016]. An additional advantage of our spanner is that it admits a subquadratic construction runtime of Õ(m + n13/7), while the previous construction in [Bodwin and Vassilevska Williams, 2016] requires all-pairs shortest paths computation which takes O(min{mn, n2.373}) time.

Publisher's Version
A Unified Framework for Light Spanners
Hung LeORCID logo and Shay Solomon ORCID logo
(University of Massachusetts, USA; Tel Aviv University, Israel)
Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Three shortcomings of previous works on light spanners are: (i) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. (ii) These constructions are optimal in the standard and crude sense, but not in a refined sense that takes into account a wider range of involved parameters. (iii) The techniques are ad hoc per graph class, and thus can’t be applied broadly.
This work aims at addressing these shortcomings by presenting a unified framework of light spanners in a variety of graph classes. Informally, the framework boils down to a transformation from sparse spanners to light spanners; since the state-of-the-art for sparse spanners is much more advanced than that for light spanners, such a transformation is powerful. First, we apply our framework to design fast constructions with optimal lightness for several graph classes. Second, we apply our framework to achieve more refined optimality bounds for several graph classes, i.e., the bounds remain optimal when taking into account a wider range of involved parameters, most notably є. Our new constructions are significantly better than the state-of-the-art for every examined graph class.

Publisher's Version
New Algorithms for All Pairs Approximate Shortest Paths
Liam Roditty ORCID logo
(Bar-Ilan University, Israel)
Let G=(V,E) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an (min{n3/2m1/2,n7/3 })-time algorithm that computes estimated distances with an additive approximation of 2 without using Fast Matrix Multiplication (FMM). Recently, Deng, Kirkpatrick, Rong, V. Williams and Zhong [ICALP 2022] improved the running time for dense graphs to (n2.29)-time, using FMM, where an exact solution can be computed with FMM in (nω) time (ω < 2.37286) using Seidel’s algorithm.
Since an additive 2 approximation is also a multiplicative 2 approximation, computing an additive 2 approximation is at least as hard as computing a multiplicative 2 approximation. Thus, computing a multiplicative 2 approximation might be an easier problem. Nevertheless, more than two decades after the paper of Dor, Halperin, and Zwick was first published, no faster algorithm for computing multiplicative 2 approximation in dense graphs is known, rather then simply computing an additive 2 approximation.
In this paper we present faster algorithms for computing a multiplicative 2 approximation without FMM. We show that in (min{ n1/2m ,n9/4 }) time it is possible to compute a multiplicative 2 approximation. For distances at least 4 we can get an even faster algorithm that in (min{ n7/4m1/4,n11/5}) expected time computes a multiplicative 2 approximation.
Our algorithms are obtained by a combination of new ideas that take advantage of a careful new case analysis of the additive approximation algorithms of Dor, Halperin, and Zwick. More specifically, one of the main technical contributions we made is an analysis of the algorithm of Dor, Halperin, and Zwick that reveals certain cases in which their algorithm produces improved additive approximations without any modification. This analysis provides a full characterization of the instances for which it is harder to obtain an improved approximation. Using more ideas we can take care of some of these harder cases and to obtain an improved additive approximation also for them. Our new analysis, therefore, serves as a starting point for future research either on improved upper bounds or on conditional lower bounds.

Publisher's Version
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň ORCID logo, Bernhard Haeupler ORCID logo, Anders Martinsson ORCID logo, Christoph Grunau ORCID logo, and Goran Zuzic ORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only logO(1) n black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1+ε)-approximate distances are equivalent to exact distances in a (1+ε)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1+ε)-approximate ones.

Publisher's Version
A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi ORCID logo, Allen Liu ORCID logo, Ankur Moitra ORCID logo, and Morris Yau ORCID logo
(Massachusetts Institute of Technology, USA)
Linear dynamical systems are the foundational statistical model upon which control theory is built. Both the celebrated Kalman filter and the linear quadratic regulator require knowledge of the system dynamics to provide analytic guarantees. Naturally, learning the dynamics of a linear dynamical system from linear measurements has been intensively studied since Rudolph Kalman's pioneering work in the 1960's. Towards these ends, we provide the first polynomial time algorithm for learning a linear dynamical system from a polynomial length trajectory up to polynomial error in the system parameters under essentially minimal assumptions; observability, controllability, and marginal stability. Our algorithm is built on a method of moments estimator to directly estimate Markov parameters from which the dynamics can be extracted. Furthermore we provide statistical lower bounds when our observability and controllability assumptions are violated.

Publisher's Version
Planning and Learning in Partially Observable Systems via Filter Stability
Noah GolowichORCID logo, Ankur Moitra ORCID logo, and Dhruv Rohatgi ORCID logo
(Massachusetts Institute of Technology, USA)
Partially Observable Markov Decision Processes (POMDPs) are an important model in reinforcement learning that take into account the agent’s uncertainty about its current state. In the literature on POMDPs, it is customary to assume access to a planning oracle that computes an optimal policy when the parameters are known, even though this problem is known to be computationally hard. The major obstruction is the Curse of History, which arises because optimal policies for POMDPs may depend on the entire observation history thus far. In this work, we revisit the planning problem and ask: Are there natural and well-motivated assumptions that avoid the Curse of History in POMDP planning (and beyond)?
We assume one-step observability, which stipulates that well-separated distributions on states lead to well-separated distributions on observations. Our main technical result is a new quantitative bound for filter stability in observable Hidden Markov Models (HMMs) and POMDPs ­– i.e. the rate at which the Bayes filter for the latent state forgets its initialization. We give the following algorithmic applications:
First, a quasipolynomial-time algorithm for planning in one-step observable POMDPs and a matching computational lower bound under the Exponential Time Hypothesis. Crucially, we require no assumptions on the transition dynamics of the POMDP.
Second, a quasipolynomial-time algorithm for improper learning of overcomplete HMMs, which does not require full-rank transitions; full-rankness is violated, for instance, when the number of latent states varies over time. Instead we assume multi-step observability, a generalization of observability which allows observations to be informative in aggregate.
Third, a quasipolynomial-time algorithm for computing approximate coarse correlated equilibria in one-step observable Partially Observable Markov Games (POMGs).
Thus we show that observability gives a blueprint for circumventing computational intractability in a variety of settings with partial observations, including planning, learning and computing equilibria.

Publisher's Version
Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making
Qinghua Liu ORCID logo, Praneeth Netrapalli ORCID logo, Csaba Szepesvari ORCID logo, and Chi Jin ORCID logo
(Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada)
This paper introduces a simple efficient learning algorithms for general sequential decision making. The algorithm combines Optimism for exploration with Maximum Likelihood Estimation for model estimation, which is thus named OMLE. We prove that OMLE learns the near-optimal policies of an enormously rich class of sequential decision making problems in a polynomial number of samples. This rich class includes not only a majority of known tractable model-based Reinforcement Learning (RL) problems (such as tabular MDPs, factored MDPs, low witness rank problems, tabular weakly-revealing/observable POMDPs and multi-step decodable POMDPs ), but also many new challenging RL problems especially in the partially observable setting that were not previously known to be tractable.
Notably, the new problems addressed by this paper include (1) observable POMDPs with continuous observation and function approximation, where we achieve the first sample complexity that is completely independent of the size of observation space; (2) well-conditioned low-rank sequential decision making problems (also known as Predictive State Representations (PSRs)), which include and generalize all known tractable POMDP examples under a more intrinsic representation; (3) general sequential decision making problems under SAIL condition, which unifies our existing understandings of model-based RL in both fully observable and partially observable settings. SAIL condition is identified by this paper, which can be viewed as a natural generalization of Bellman/witness rank to address partial observability. This paper also presents a reward-free variant of OMLE algorithm, which learns approximate dynamic models that enable the computation of near-optimal policies for all reward functions simultaneously.

Publisher's Version Info
Weighted Edit Distance Computation: Strings, Trees, and Dyck
Debarati Das ORCID logo, Jacob Gilbert ORCID logo, MohammadTaghi Hajiaghayi ORCID logo, Tomasz Kociumaka ORCID logo, and Barna Saha ORCID logo
(Pennsylvania State University, USA; University of Maryland, USA; MPI-INF, Germany; University of California at San Diego, San Diego, USA)
Given two strings of length n over alphabet Σ, and an upper bound k on their edit distance, the algorithm of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88) from almost forty years back computes the unweighted string edit distance in O(n+k2) time. To date, it remains the fastest algorithm for exact edit distance computation, and it is optimal under the Strong Exponential Hypothesis (Backurs and Indyk; STOC’15). Over the years, this result has inspired many developments, including fast approximation algorithms for string edit distance as well as similar Õ(n+poly(k))-time algorithms for generalizations to tree and Dyck edit distances. Surprisingly, all these results hold only for unweighted instances.
While unweighted edit distance is theoretically fundamental, almost all real-world applications require weighted edit distance, where different weights are assigned to different edit operations (insertions, deletions, and substitutions), and the weights may vary with the characters being edited. Given a weight function w : Σ∪{ε} × Σ∪{ε} → ℝ≥ 0 (such that w(a,a) = 0 and w(a,b) ≥ 1 for all a, b∈ Σ∪{ε} with ab), the goal is to find an alignment that minimizes the total weight of edits. Except for the vanilla O(n2)-time dynamic-programming algorithm and its almost trivial O(nk)-time implementation (k being an upper bound on the sought total weight), none of the aforementioned developments on the unweighted edit distance applies to the weighted variant.
In this paper, we propose the first O(n+poly(k))-time algorithm that computes the weighted string edit distance exactly, thus bridging a fundamental decades-old gap between our understanding of unweighted and weighted edit distance. We then generalize this result to the weighted tree and Dyck edit distances, bringing in several new techniques, which lead to a deterministic algorithm that improves upon the previous work even for unweighted tree edit distance. Given how fundamental weighted edit distance is, we believe our O(n+poly(k))-time algorithm will be instrumental for further significant developments in the area.

Publisher's Version
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud ORCID logo, Karl Bringmann ORCID logo, and Nick Fischer ORCID logo
(Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany)
The “short cycle removal” technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC ’22) to prove fine-grained hardness of approximation. Its main technical result is that listing all triangles in an n1/2-regular graph is n2−o(1)-hard even when the number of short cycles is small; namely, when the number of k-cycles is O(nk/2+γ) for γ<1/2. Its corollaries are based on the 3-SUM conjecture and their strength depends on γ, i.e. on how effectively the short cycles are removed.
Abboud et al. achieve γ≥ 1/4 by applying structure versus randomness arguments on graphs. In this paper, we take a step back and apply conceptually similar arguments on the numbers of the 3-SUM problem, from which the hardness of triangle listing is derived. Consequently, we achieve the best possible ‍γ=0 and the following lower bound corollaries under the 3-SUM conjecture:
* Approximate distance oracles: The seminal Thorup-Zwick distance oracles achieve stretch 2k± O(1) after preprocessing a graph in O(m n1/k) time. For the same stretch, and assuming the query time is ‍no(1) Abboud et al. proved an Ω(m1+1/12.7552 · k) lower bound on the preprocessing time; we improve it to Ω(m1+1/2k) which is only a factor ‍2 away from the upper bound. Additionally, we obtain tight bounds for stretch 2+o(1) and 3−є and higher lower bounds for dynamic shortest paths.
* Listing 4-cycles: Abboud et al. proved the first super-linear lower bound for listing all 4-cycles in a graph, ruling out (m1.1927+t)1+o(1) time algorithms where t is the number of 4-cycles. We settle the complexity of this basic problem by showing that the O(min(m4/3,n2) +t) upper bound is tight up to no(1) factors.
Our results exploit a rich tool set from additive combinatorics, most notably the Balog-Szemerédi-Gowers theorem and Rusza’s covering lemma. A key ingredient that may be of independent interest is a truly subquadratic algorithm for 3-SUM if one of the sets has small doubling.

Publisher's Version
Removing Additive Structure in 3SUM-Based Reductions
Ce JinORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Our work explores the hardness of 3SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving 3SUM on a size-n integer set that avoids solutions to a+b=c+d for {a, b} ≠ {c, d} still requires n2−o(1) time, under the 3SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics.
Combined with previous reductions, this implies that the All-Edges Sparse Triangle problem on n-vertex graphs with maximum degree √n and at most nk/2 k-cycles for every k ≥ 3 requires n2−o(1) time, under the 3SUM hypothesis. This can be used to strengthen the previous conditional lower bounds by Abboud, Bringmann, Khoury, and Zamir [STOC’22] of 4-Cycle Enumeration, Offline Approximate Distance Oracle and Approximate Dynamic Shortest Path. In particular, we show that no algorithm for the 4-Cycle Enumeration problem on n-vertex m-edge graphs with no(1) delays has O(n2−ε) or O(m4/3−ε) pre-processing time for ε >0. We also present a matching upper bound via simple modifications of the known algorithms for 4-Cycle Detection.
A slight generalization of the main result also extends the result of Dudek, Gawrychowski, and Starikovskaya [STOC’20] on the 3SUM hardness of nontrivial 3-Variate Linear Degeneracy Testing (3-LDTs): we show 3SUM hardness for all nontrivial 4-LDTs.
The proof of our main technical result combines a wide range of tools: Balog-Szemerédi-Gowers theorem, sparse convolution algorithm, and a new almost-linear hash function with almost 3-universal guarantee for integers that do not have small-coefficient linear relations.

Publisher's Version
Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan ORCID logo, Virginia Vassilevska Williams ORCID logo, and Yinzhan Xu ORCID logo
(University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)
In this paper we carefully combine Fredman’s trick [SICOMP’76] and Matoušek’s approach for dominance product [IPL’91] to obtain powerful results in fine-grained complexity.
Under the hypothesis that APSP for undirected graphs with edge weights in {1, 2, …, n} requires n3−o(1) time (when ω=2), we show a variety of conditional lower bounds, including an n7/3−o(1) lower bound for unweighted directed APSP and an n2.2−o(1) lower bound for computing the Minimum Witness Product between two n × n Boolean matrices, even if ω=2, improving upon their trivial n2 lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when ω = 2), if unweighted directed APSP requires n2.5−o(1) time, then Minimum Witness Product requires n7/3−o(1) time.
We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version.
We also obtain new algorithms using new variants of the Balog-Szemerédi-Gowers theorem from additive combinatorics. For example, we get an O(n3.83) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook O(n4) time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in {1, 2, …, n}d.

Publisher's Version

Session 2A

Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝
Xiaorui Sun ORCID logo
(University of Illinois at Chicago, USA)
The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order n, an algorithm with n(logn + O(1)) running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an n(1 / 4 + o(1))logn running time (Rosenbaum 2013).
The isomorphism testing for p-groups of (nilpotent) class 2 and exponent p has been identified as a major barrier to obtaining an no(logn) time algorithm for the group isomorphism problem. Although the p-groups of class 2 and exponent p have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an nO(logn) running time.
In this paper, we present an isomorphism testing algorithm for p-groups of class 2 and exponent p with running time nO((logn)5/6) for any prime p > 2. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces.

Publisher's Version
Linear Independence, Alternants, and Applications
Vishwas Bhargava ORCID logo, Shubhangi Saraf ORCID logo, and Ilya Volkovich ORCID logo
(University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA)
We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence (SWLI) lemma which states the following. If the polynomials f1,f2, …, fkF[X] over X={x1, …, xn} are F-linearly independent then there exists a subset SX of size at most k−1 such that f1,f2, …, fk are also F(XS)-linearly independent.
We show how to effectively combine this lemma with the use of the alternant matrix to analyze linear independence of polynomials. We also give applications of our technique to the questions of polynomial identity testing and arithmetic circuit reconstruction. 1) We give a general technique for lifting efficient polynomial identity testing algorithms from basic classes of circuits, satisfying some closure properties, to more general classes of circuits. As one of the corollaries of this result, we obtain the first algorithm for polynomial identity testing for depth-4, constant-occur circuits that works over all fields. This strengthens a result by [ASSS ’16] (STOC ’12) that works in the case when the characteristic is 0 or sufficiently large. Another corollary is an identity testing algorithm for a special case of depth-5 circuits. To the best of our knowledge, this is the first algorithm for this class of circuits. 2) We give new and efficient black-box reconstruction algorithms for the class of set-multilinear depth-3 circuits of constant top fan-in, where the set-multilinear variable partition is unknown. This generalizes the results of [BSV ’21] (STOC ’21) and [PSV ’22] (ECCC ’22) which work in the case of known variable partition, and correspond to tensor decomposition of constant-rank tensors.

Publisher's Version Info
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
Josh Alman ORCID logo and Kevin Rao ORCID logo
(Columbia University, USA)
We give algorithms with lower arithmetic operation counts for both the Walsh-Hadamard Transform (WHT) and the Discrete Fourier Transform (DFT) on inputs of power-of-2 size N.
For the WHT, our new algorithm has an operation count of 23/24N logN + O(N). To our knowledge, this gives the first improvement on the N logN operation count of the simple, folklore Fast Walsh-Hadamard Transform algorithm.
For the DFT, our new FFT algorithm uses 15/4N logN + O(N) real arithmetic operations. Our leading constant 15/4 = 3.75 improves on the leading constant of 5 from the Cooley-Tukey algorithm from 1965, leading constant 4 from the split-radix algorithm of Yavne from 1968, leading constant 34/9=3.7777 from a modification of the split-radix algorithm by Van Buskirk from 2004, and leading constant 3.76875 from a theoretically optimized version of Van Buskirk’s algorithm by Sergeev from 2017.
Our new WHT algorithm takes advantage of a recent line of work on the non-rigidity of the WHT: we decompose the WHT matrix as the sum of a low-rank matrix and a sparse matrix, and then analyze the structures of these matrices to achieve a lower operation count. Our new DFT algorithm comes from a novel reduction, showing that parts of the previous best FFT algorithms can be replaced by calls to an algorithm for the WHT. Replacing the folklore WHT algorithm with our new improved algorithm leads to our improved FFT.

Publisher's Version
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
Hamed Hatami ORCID logo, Kaave Hosseini ORCID logo, and Xiang Meng ORCID logo
(McGill University, Canada; University of Rochester, USA)
We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.
This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of the Gap Hamming Distance problem is O(1) while its unbounded-error communication complexity is Ω(log(n)). Previously, it was unknown whether the unbounded-error communication complexity could be asymptotically larger than the randomized communication
In connection to learning theory, we prove that, despite its learnability properties, the class of large margin half-spaces in ℝd is genuinely high-dimensional, i.e., it cannot be embedded in d−1. This result is closely related to a recent conjecture of Alon, Hanneke, Holzman, and Moran (FOCS 2021) about the VC dimension of this class.
Our final application is to the theory of dimension reductions. The Johnson-Lindenstrauss theorem implies that any set of N unit vectors is embeddable in dimension O−2logN) without altering the signs of those pairwise inner products that have absolute values at least γ>0. Our result establishes the tightness of this bound, which answers a question of Linial, Mendelson, Schechtman, and Shraibman (Combinatorica, 27(2007)) in the case of partial functions.

Publisher's Version

Session 2B

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen ORCID logo, Xin Lyu ORCID logo, Jelani Nelson ORCID logo, Tamás Sarlós ORCID logo, and Uri Stemmer ORCID logo
(Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel)
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of O−1 log(1/β)) (for generalization error ξ with confidence 1−β). The private version of the problem, however, is more challenging and in particular, the sample complexity must depend on the size |X| of the domain. Progress on quantifying this dependence, via lower and upper bounds, was made in a line of works over the past decade. In this paper, we finally close the gap for approximate-DP and provide a nearly tight upper bound of O(log* |X|), which matches a lower bound by Alon et al (that applies even with improper learning) and improves over a prior upper bound of O((log* |X|)1.5) by Kaplan et al. We also provide matching upper and lower bounds of Θ(2log*|X|) for the additive error of private quasi-concave optimization (a related and more general problem). Our improvement is achieved via the novel Reorder-Slice-Compute paradigm for private data analysis which we believe will have further applications.

Publisher's Version Info
Privately Estimating a Gaussian: Efficient, Robust, and Optimal
Daniel Alabi ORCID logo, Pravesh K. Kothari ORCID logo, Pranay Tankala ORCID logo, Prayaag Venkat ORCID logo, and Fred Zhang ORCID logo
(Columbia University, USA; Carnegie Mellon University, USA; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity.
In the pure DP setting, we give an efficient algorithm that estimates an unknown d-dimensional Gaussian distribution up to an arbitrary tiny total variation error using O(d2 logκ) samples while tolerating a constant fraction of adversarial outliers. Here, κ is the condition number of the target covariance matrix. The sample bound matches best non-private estimators in the dependence on the dimension (up to a polylogarithmic factor). We prove a new lower bound on differentially private covariance estimation to show that the dependence on the condition number κ in the above sample bound is also tight. Prior to our work, only identifiability results (yielding inefficient super-polynomial time algorithms) were known for the problem.
In the approximate DP setting, we give an efficient algorithm to estimate an unknown Gaussian distribution up to an arbitrarily tiny total variation error using O(d2) samples while tolerating a constant fraction of adversarial outliers. Prior to our work, all efficient approximate DP algorithms incurred a super-quadratic sample cost or were not outlier-robust. For the special case of mean estimation, our algorithm achieves the optimal sample complexity of O(d), improving on a O(d1.5) bound from prior work.
Our pure DP algorithm relies on a recursive private preconditioning subroutine that utilizes recent work of Hopkins et al. (STOC 2022) on private mean estimation. Our approximate DP algorithms are based on a substantial upgrade of the method of stabilizing convex relaxations introduced by Kothari et al. (COLT 2022). In particular, we improve on their mechanism by using a new unnormalized entropy regularization and a new and surprisingly simple mechanism for privately releasing covariances.

Publisher's Version
Robustness Implies Privacy in Statistical Estimation
Samuel B. HopkinsORCID logo, Gautam KamathORCID logo, Mahbod MajidORCID logo, and Shyam NarayananORCID logo
(Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA)
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.

Publisher's Version
Concurrent Composition Theorems for Differential Privacy
Salil Vadhan ORCID logo and Wanrong Zhang ORCID logo
(Harvard University, USA)
We study the concurrent composition properties of interactive differentially private mechanisms, whereby an adversary can arbitrarily interleave its queries to the different mechanisms. We prove that all composition theorems for non-interactive differentially private mechanisms extend to the concurrent composition of interactive differentially private mechanisms, whenever differential privacy is measured using the hypothesis testing framework of f-DP, which captures standard (,δ)-DP as a special case. We prove the concurrent composition theorem by showing that every interactive f-DP mechanism can be simulated by interactive post-processing of a non-interactive f-DP mechanism.
In concurrent and independent work, Lyu (NeurIPS ‘22) proves a similar result to ours for (,δ)-DP, as well as a concurrent composition theorem for Rényi DP. We also provide a simple proof of Lyu’s concurrent composition theorem for Rényi DP. Lyu leaves the general case of f-DP as an open problem, which we solve in this paper.

Publisher's Version
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun ORCID logo, Marco Gaboardi ORCID logo, Max Hopkins ORCID logo, Russell Impagliazzo ORCID logo, Rex Lei ORCID logo, Toniann Pitassi ORCID logo, Satchit Sivakumar ORCID logo, and Jessica Sorrell ORCID logo
(Boston University, USA; University of California at San Diego, San Diego, USA; Columbia University, USA; University of Pennsylvania, USA)
The notion of replicable algorithms was introduced by Impagliazzo, Lei, Pitassi, and Sorrell (STOC’22) to describe randomized algorithms that are stable under the resampling of their inputs. More precisely, a replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. Using replicable algorithms for data analysis can facilitate the verification of published results by ensuring that the results of an analysis will be the same with high probability, even when that analysis is performed on a new data set.
In this work, we establish new connections and separations between replicability and standard notions of algorithmic stability. In particular, we give sample-efficient algorithmic reductions between perfect generalization, approximate differential privacy, and replicability for a broad class of statistical problems. Conversely, we show any such equivalence must break down computationally: there exist statistical problems that are easy under differential privacy, but that cannot be solved replicably without breaking public-key cryptography. Furthermore, these results are tight: our reductions are statistically optimal, and we show that any computational separation between DP and replicability must imply the existence of one-way functions.
Our statistical reductions give a new algorithmic framework for translating between notions of stability, which we instantiate to answer several open questions in replicability and privacy. This includes giving sample-efficient replicable algorithms for various PAC learning, distribution estimation, and distribution testing problems, algorithmic amplification of δ in approximate DP, conversions from item-level to user-level privacy, and the existence of private agnostic-to-realizable learning reductions under structured distributions.

Publisher's Version

Session 2C

An Improved Parameterized Algorithm for Treewidth
Tuukka KorhonenORCID logo and Daniel Lokshtanov ORCID logo
(University of Bergen, Norway, Norway; University of California at Santa Barbara, Santa Barbara, USA)
We give an algorithm that takes as input an n-vertex graph G and an integer k, runs in time 2O(k2) nO(1), and outputs a tree decomposition of G of width at most k, if such a decomposition exists. This resolves the long-standing open problem of whether there is a 2o(k3) nO(1) time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2O(k3) nO(1) time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991].
We also give an algorithm that given an n-vertex graph G, an integer k, and a rational ε ∈ (0,1), in time kO(k/ε) nO(1) either outputs a tree decomposition of G of width at most (1+ε)k or determines that the treewidth of G is larger than k. Prior to our work, no approximation algorithms for treewidth with approximation ratio less than 2, other than the exact algorithms, were known. Both of our algorithms work in polynomial space.

Publisher's Version
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan ORCID logo, Matthias Lanzinger ORCID logo, and Marc Roth ORCID logo
(University of Milan, Italy; University of Oxford, UK)
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs H and G, count the number of copies of H in G. The standard setting, where the tractability is well understood, uses only |H| as a parameter. In this paper we adopt as a parameter |H|+d(G), where d(G) is the maximum outdegree of |G|. Under this parameterisation, we completely characterize the fixed-parameter tractability of the problem in both its non-induced and induced versions through two novel structural parameters, the fractional cover number ρ* and the source number αs. On the one hand we give algorithms with running time f(|H|,d(G)) · |G|ρ*(H)+O(1) and f(|H|,d(G)) · |G|αs(H)+O(1) for counting respectively the copies and induced copies of H in G; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class C of directed graphs the restriction of the problem to patterns in C is fixed-parameter tractable if and only if ρ*(C) is bounded (αs(C) for the induced version). These results explain how the orientation of the pattern can make counting easy or hard, and prove that a classic algorithm by Chiba and Nishizeki and its extensions (Chiba and Nishizeki, SICOMP ’85; Bressan, Algorithmica ’21) are optimal unless ETH fails.
Our proofs consist of several layers of parameterised reductions that preserve the outdegree of the host graph. To start with, we establish a tight connection between counting homomorphisms from H to G to #CSP, the problem of counting solutions of constraint satisfactions problems, for special classes of patterns that we call canonical DAGs. To lift these results from canonical DAGs to arbitrary directed graphs, we exploit a combination of several ingredients: existing results for #CSPs (Marx JACM 13; Grohe, Marx TALG 14), an extension of graph motif parameters (Curticapean, Dell, Marx STOC 17) to our setting, the introduction of what we call monotone reversible minors, and a careful analysis of quotients of directed graphs in order to relate their adaptive width and fractional hypertreewidth to our novel parameters. Along the route we establish a novel bound of the integrality gap for the fractional independence number of hypergraphs based on adaptive width, which might be of independent interest.

Publisher's Version
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms
Huck Bennett ORCID logo, Mahdi Cheraghchi ORCID logo, Venkatesan Guruswami ORCID logo, and João RibeiroORCID logo
(Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal)
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that SVP in the ℓp norm is W[1]-hard to approximate within any constant factor for any fixed p >1 and W[1]-hard to approximate within a factor approaching 2 for p=1. (We show hardness under randomized reductions in each case.)
These results answer the main questions left open (and explicitly posed) by Bhattacharyya, Bonnet, Egri, Ghoshal, Karthik C. S., Lin, Manurangsi, and Marx (Journal of the ACM, 2021) on the complexity of parameterized MDP and SVP. For MDP, they established similar hardness for binary linear codes and left the case of general fields open. For SVP in ℓp norms with p > 1, they showed inapproximability within some constant factor (depending on p) and left open showing such hardness for arbitrary constant factors. They also left open showing W[1]-hardness even of exact SVP in the ℓ1 norm.

Publisher's Version
First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier ORCID logo, Nikolas Mählmann ORCID logo, and Sebastian Siebertz ORCID logo
(TU Wien, Austria; University of Bremen, Germany)
A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly generalize nowhere dense classes and constitute important examples of monadically stable classes. We show that the first-order model checking problem is fixed-parameter tractable on every structurally nowhere dense class of graphs.
Our result builds on a recently developed game-theoretic characterization of monadically stable graph classes. As a second key ingredient of independent interest, we provide a polynomial-time algorithm for approximating weak neighborhood covers (on general graphs). We combine the two tools into a recursive locality-based model checking algorithm. This algorithm is efficient on every monadically stable graph class admitting flip-closed sparse weak neighborhood covers, where flip-closure is a mild additional assumption. Thereby, establishing efficient first-order model checking on monadically stable classes is reduced to proving the existence of flip-closed sparse weak neighborhood covers on these classes -- a purely combinatorial problem. We complete the picture by proving the existence of the desired covers for structurally nowhere dense classes: we show that every structurally nowhere dense class can be sparsified by contracting local sets of vertices, enabling us to lift the existence of covers from sparse classes.

Publisher's Version

Session 3: Best Papers

The Randomized 𝑘-Server Conjecture Is False!
Sébastien BubeckORCID logo, Christian Coester ORCID logo, and Yuval Rabani ORCID logo
(Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel)
We prove a few new lower bounds on the randomized competitive ratio for the k-server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987).
More concretely, we show: (1) There exist (k+1)-point metric spaces in which the randomized competitive ratio for the k-server problem is Ω(log2 k). This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at least k+1 points, the competitive ratio is Θ(logk). (2) Consequently, there exist n-point metric spaces in which the randomized competitive ratio for MTS is Ω(log2 n). This matches the upper bound that holds for all metrics. The previously best existential lower bound was Ω(logn) (which was known to be tight for some families of metrics). (3) For all k<n∈, for all n-point metric spaces the randomized k-server competitive ratio is at least Ω(logk), and consequently the randomized MTS competitive ratio is at least Ω(logn). These universal lower bounds are asymptotically tight. The previous bounds were Ω(logk/loglogk) and Ω(logn/loglogn), respectively. (4) The randomized competitive ratio for the w-set metrical service systems problem, and its equivalent width-w layered graph traversal problem, is Ω(w2). This slightly improves the previous lower bound and matches the recently discovered upper bound. (5) Our results imply improved lower bounds for other problems like k-taxi, distributed paging, and metric allocation.
These lower bounds share a common thread, and other than the third bound, also a common construction.

Publisher's Version
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
Wei-Kai Lin ORCID logo, Ethan Mook ORCID logo, and Daniel WichsORCID logo
(Northeastern University, USA; NTT Research, USA)
A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR), the database is first preprocessed, but the server can subsequently answer any client’s query in time that is sub-linear in the database size. Prior work gave a plausible candidate for a public-key variant of DEPIR, where a trusted party is needed to securely preprocess the database and generate a corresponding public key for the clients; security relied on a new non-standard code-based assumption and a heuristic use of ideal obfuscation. In this work we construct the stronger unkeyed notion of DEPIR, where the preprocessing is a deterministic procedure that the server can execute on its own. Moreover, we prove security under just the standard ring learning-with-errors (RingLWE) assumption. For a database of size N and any constant ε>0, the preprocessing run-time and size is O(N1+ε), while the run-time and communication-complexity of each PIR query is polylog(N). We also show how to update the preprocessed database in time O(Nε). Our approach is to first construct a standard PIR where the server’s computation consists of evaluating a multivariate polynomial; we then convert it to a DEPIR by preprocessing the polynomial to allow for fast evaluation, using the techniques of Kedlaya and Umans (STOC ’08).
Building on top of our DEPIR, we construct general fully homomorphic encryption for random-access machines (RAM-FHE), which allows a server to homomorphically evaluate an arbitrary RAM program P over a client’s encrypted input x and the server’s preprocessed plaintext input y to derive an encryption of the output P(x,y) in time that scales with the RAM run-time of the computation rather than its circuit size. Prior work only gave a heuristic candidate construction of a restricted notion of RAM-FHE. In this work, we construct RAM-FHE under the RingLWE assumption with circular security. For a RAM program P with worst-case run-time T, the homomorphic evaluation runs in time T1+ε · (|x| + |y|).

Publisher's Version

Session 4A

SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek ORCID logo, Venkatesan Guruswami ORCID logo, and Sai Sandeep ORCID logo
(Stanford University, USA; University of California at Berkeley, Berkeley, USA)
For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width, i.e., CSPs whose satisfiability can be checked by a simple local consistency algorithm (eg., 2-SAT or Horn-SAT in the Boolean case). While the exact satisfiability of a bounded width CSP can be checked by combinatorial algorithms, the robust algorithm is based on rounding a canonical Semi Definite Programming(SDP) relaxation.
In this work, we initiate the study of robust satisfaction algorithms for promise CSPs, which are a vast generalization of CSPs that have received much attention recently. The motivation is to extend the theory beyond CSPs, as well as to better understand the power of SDPs. We present robust SDP rounding algorithms under some general conditions, namely the existence of majority or alternating threshold polymorphisms. On the hardness front, we prove that the lack of such polymorphisms makes the PCSP hard for all pairs of symmetric Boolean predicates. Our method involves a novel method to argue SDP gaps via the absence of certain colorings of the sphere, with connections to sphere Ramsey theory.
We conjecture that PCSPs with robust satisfaction algorithms are precisely those for which the feasibility of the canonical SDP implies (exact) satisfiability. We also give a precise algebraic condition, known as a minion characterization, of which PCSPs have the latter property.

Publisher's Version
Approximate Graph Colouring and the Hollow Shadow
Lorenzo Ciardo ORCID logo and Stanislav Živný ORCID logo
(University of Oxford, UK)
We show that approximate graph colouring is not solved by constantly many levels of the lift-and-project hierarchy for the combined basic linear programming and affine integer programming relaxation. The proof involves a construction of tensors whose fixed-dimensional projections are equal up to reflection and satisfy a sparsity condition, which may be of independent interest.

Publisher's Version
On Approximability of Satisfiable k-CSPs: II
Amey Bhangale ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
Let Σ be an alphabet and µ be a distribution on Σk for some k ≥ 2. Let α > 0 be the minimum probability of a tuple in the support of µ (denoted supp(µ)). Here, the support of µ is the set of all tuples in Σk that have a positive probability mass under µ. We treat the parameters Σ, k, µ, α as fixed and constant.
We say that the distribution µ has a linear embedding if there exist an Abelian group G (with the identity element 0G) and mappings σi : Σ → G, 1 ≤ ik, such that at least one of the mappings is non-constant and for every (a1, a2, …, ak)∈ supp(µ), ∑i=1k σi(ai) = 0G.
Let fi: Σn→ [−1,1] be bounded functions, such that at least one of the functions fi essentially has degree at least d, meaning that the Fourier mass of fi on terms of degree less than d is negligible, say at most δ. In particular, |E[fi]| ≤ δ. The Fourier representation is w.r.t. the marginal of µ on the ith co-ordinate, denoted (Σ, µi). If µ has no linear embedding (over any Abelian group), then is it necessarily the case that
|E(x1, x2, …, xk)∼ µ⊗ n[f1(x1)f2(x2)⋯ fk(xk)]  = od, δ(1),
where the right hand side → 0 as the degree d → ∞ and δ → 0?
In this paper, we answer this analytical question fully and in the affirmative for k=3. We also show the following two applications of the result. The first application is related to hardness of approximation. We show that for every 3-ary predicate P3 → {0,1} such that P has no linear embedding, an SDP integrality gap instance of a P-CSP instance with gap (1,s) can be translated into a dictatorship test with completeness 1 and soundness s+o(1), under certain additional conditions on the instance. The second application is related to additive combinatorics. We show that if the distribution µ on Σ3 has no linear embedding, marginals of µ are uniform on Σ, and (a,a,a)∈ supp(µ) for every a∈ Σ, then every large enough subset of Σn contains a triple (x1, x2,x3) from µn (and in fact a significant density of such triples).

Publisher's Version
On Approximability of Satisfiable k-CSPs: III
Amey Bhangale ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property also holds for low-degree functions as low-degree functions become a constant function under a random restriction with a non-negligible probability. We show that this essentially is the only possible reason. More specifically, we show that the function must be correlated to a product of a linear function and a low-degree function. One of the main motivations of studying this question comes from the recent work of the authors towards understanding approximability of satisfiable Constraint Satisfaction Problems.
Towards proving our structural theorem, we analyze a 2-query direct product test for the table F: [n] qn → {0,1}qn where q∈ (0,1). We show that, for every constant ε>0, if the test passes with probability ε>0, then there is a global function g: [n]→ {0,1} such that for at least δ(ε) fraction of sets, the global function g agrees with the given table on all except α(ε) many locations. The novelty of this result lies in the fact that α(ε) is independent of the set sizes. Prior to our work, such a conclusion (in fact, a stronger conclusion with α = 0) was shown by Dinur, Filmus, and Harsha albeit when the test accepts with probability 1−ε for a small constant ε>0. The setting of parameters in our direct product tests is fundamentally different compared to the previous results and hence our analysis involves new techniques, including the use of the small-set expansion property of graphs defined on multi-slices.
As one application of our structural result, we give a 4-query linearity test under the p-biased distribution. More specifically, for any p∈ (1/3,2/3), we give a test that queries a given function f: {0,1}n → {0,1} at 4 locations, where the marginal distribution of each query is µpn. The test has perfect completeness and soundness 1/2+ε – in other words, for every constant ε>0, if the test passes with probability at least 1/2+ε, then the function f is correlated to a linear function under the µpn measure. This qualitatively improves the results on the linearity testing under the p-biased distribution from the previous work where the authors studied the test with soundness 1−ε, for ε close to 0.

Publisher's Version
An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games
David Ellis ORCID logo, Guy Kindler ORCID logo, and Noam Lifshitz ORCID logo
(University of Bristol, UK; Hebrew University of Jerusalem, Israel)
We prove an analogue of Bonami’s (hypercontractive) lemma for complex-valued functions on L (𝑉 ,𝑊 ), where 𝑉 and 𝑊 are vector spaces over a finite field. This inequality is useful for functions on L (𝑉 ,𝑊 ) whose ‘generalised influences’ are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness)

Publisher's Version
Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
Ronen Eldan ORCID logo, Dan Mikulincer ORCID logo, and Prasad RaghavendraORCID logo
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA)
We consider a variant of the classical notion of noise on the Boolean hypercube which gives rise to a new approach to inequalities regarding noise stability. We use this approach to give a new proof of the Majority is Stablest theorem by Mossel, O'Donnell, and Oleszkiewicz, improving the dependence of the bound on the maximal influence of the function from logarithmic to polynomial. We also show that a variant of the conjecture by Courtade and Kumar regarding the most informative Boolean function, where the classical noise is replaced by our notion, holds true. Our approach is based on a stochastic construction that we call the renormalized Brownian motion, which facilitates the use of inequalities in Gaussian space in the analysis of Boolean functions.

Publisher's Version

Session 4B

A Proof of the Nisan-Ronen Conjecture
George Christodoulou ORCID logo, Elias Koutsoupias ORCID logo, and Annamária Kovács ORCID logo
(Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany)
Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. This work validates the conjecture.

Publisher's Version
A Constant Factor Prophet Inequality for Online Combinatorial Auctions
José Correa ORCID logo and Andrés Cristi ORCID logo
(University of Chile, Chile)
In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents’ valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best known prophet inequality has an approximation guarantee of O(loglogm). In this paper, we prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.
Our prophet inequality is achieved by a novel, but elementary, sampling idea which we call the Mirror Lemma. This lemma is essentially concerned with understanding online algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani’s fixed point theorem. Finally, we note that our prophet inequality works against an almighty adversary and even can be implemented in an incentive compatible way.

Publisher's Version
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Xi ChenORCID logo and Binghui Peng ORCID logo
(Columbia University, USA)
We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We show that the problem is PPAD-complete even when the tie-breaking rule is trilateral (i.e., it specifies item allocations when no more than three bidders are in tie, and adopts the uniform tie-breaking rule otherwise). This is the first hardness result for equilibrium computation in first-price auctions with common priors. On the positive side, we give a PTAS for the problem under the uniform tie-breaking rule.

Publisher's Version
Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
Ioannis CaragiannisORCID logo and Zhile Jiang ORCID logo
(Aarhus University, Denmark)
Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate equilibria. We present a polynomial-time algorithm that computes 2.7371-approximate pure Nash equilibria in cut games. This is the first improvement to the previously best-known bound of 3, due to the work of Bhalgat, Chakraborty, and Khanna from EC 2010. Our algorithm is based on a general recipe proposed by Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on several potential games since then. The first novelty of our work is the introduction of a phase that can identify subsets of players who can simultaneously improve their utilities considerably. This is done via semidefinite programming and randomized rounding. In particular, a negative objective value to the semidefinite program guarantees that no such considerable improvement is possible for a given set of players. Otherwise, randomized rounding of the SDP solution is used to identify a set of players who can simultaneously improve their strategies considerably and allows the algorithm to make progress. The way rounding is performed is another important novelty of our work. Here, we exploit an idea that dates back to a paper by Feige and Goemans from 1995, but we take it to an extreme that has not been analyzed before.

Publisher's Version
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Matheus Venturyne Xavier FerreiraORCID logo and David C. Parkes ORCID logo
(Harvard University, USA)
Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S. ‍dollars. In the status quo, users broadcast transactions they wish to execute in the exchange and miners are responsible for composing a block of transactions and picking an execution ordering — the order in which transactions execute in the exchange. Due to the lack of a regulatory framework, it is common to observe miners exploiting their privileged position by front-running transactions and obtaining risk-fee profits. Indeed, the Flashbots service institutionalizes this exploit, with miners auctioning the right to front-run transactions. In this work, we propose to modify the interaction between miners and users and initiate the study of verifiable sequencing rules. As in the status quo, miners can determine the content of a block; however, they commit to respecting a sequencing rule that constrains the execution ordering and is verifiable (there is a polynomial time algorithm that can verify if the execution ordering satisfies such constraints). Thus in the event a miner deviates from the sequencing rule, anyone can generate a proof of non-compliance.
We ask if there are sequencing rules that limit price manipulation from miners in a two-token liquidity pool exchange. Our first result is an impossibility theorem: for any sequencing rule, there is an instance of user transactions where the miner can obtain non-zero risk-free profits. In light of this impossibility result, our main result is a verifiable sequencing rule that provides execution price guarantees for users. In particular, for any user transaction A, it ensures that either (1) the execution price of A is at least as good as if A was the only transaction in the block, or (2) the execution price of A is worse than this “standalone” price and the miner does not gain when including A in the block. Our framework does not require users to use countermeasures against predatory trading strategies, for example, set limit prices or split large transactions into smaller ones. This is likely to improve user experience relative to the status quo.

Publisher's Version
On the Optimal Fixed-Price Mechanism in Bilateral Trade
Yang Cai ORCID logo and Jinzhao Wu ORCID logo
(Yale University, USA)
We study the problem of social welfare maximization in bilateral trade, where two agents, a buyer and a seller, trade an indivisible item. The seminal result of Myerson and Satterthwaite shows that no incentive compatible and budget balanced (i.e., the mechanism does not run a deficit) mechanism can achieve the optimal social welfare in bilateral trade. Motivated by this impossibility result, we focus on approximating the optimal social welfare. We consider arguably the simplest form of mechanisms – the fixed-price mechanisms, where the designer offers trade at a fixed price to the seller and buyer. Besides the simple form, fixed-price mechanisms are also the only dominant strategy incentive compatible and budget balanced mechanisms in bilateral trade.
We obtain improved approximation ratios of fixed-price mechanisms in both (i) the setting where the designer has the full prior information, that is, the value distributions of both the seller and buyer; and (ii) the setting where the designer only has access to limited information of the prior. In the full prior information setting, we show that the optimal fixed-price mechanism can achieve at least 0.72 of the optimal welfare, and no fixed-price mechanism can achieve more than 0.7381 of the optimal welfare. Prior to our result the state of the art approximation ratio was 1 − 1/e + 0.0001≈ 0.632. Interestingly, we further show that the optimal approximation ratio achievable with full prior information is identical to the optimal approximation ratio obtainable with only one-sided prior information, i.e., the buyer’s or the seller’s value distribution. As a simple corollary, our upper and lower bounds in the full prior information setting also apply to the case when the designer only has access to one-sided prior information.
We further consider two limited information settings. In the first one, the designer is only given the mean of the buyer’s value (or the mean of the seller’s value). We show that with such minimal information, one can already design a fixed-price mechanism that achieves 2/3 of the optimal social welfare, which surpasses the previous state of the art ratio even when the designer has access to the full prior information. In the second limited information setting, we assume that the designer has access to finitely many samples from the value distributions.
Recent results show that one can already obtain a constant factor approximation to the optimal welfare using a single sample from the seller’s distribution. Our goal is to understand what approximation ratios are possible if the designer has more than one but still finitely many samples. This is usually a technically more challenging regime and requires tools different from the single-sample analysis. We propose a new family of sample-based fixed-price mechanisms that we refer to as the order statistic mechanisms and provide a complete characterization of their approximation ratios for any fixed number of samples. Using the characterization, we provide the optimal approximation ratios obtainable by order statistic mechanism for small sample sizes (no more than 10 samples) and observe that they significantly outperform the single sample mechanism.

Publisher's Version
Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
Zhengyang Liu ORCID logo, Zeyu Ren ORCID logo, and Zihe Wang ORCID logo
(Beijing Institute of Technology, China; Renmin University of China, China)
We continue the study of the performance for fixed-price mechanisms in the bilateral trade problem, and improve approximation ratios of welfare-optimal mechanisms in several settings. Specifically, in the case where only the buyer distribution is known, we prove that there exists a distribution over different fixed-price mechanisms, such that the approximation ratio lies within the interval of [0.71, 0.7381]. Furthermore, we show that the same approximation ratio holds for the optimal fixed-price mechanism, when both buyer and seller distributions are known. As a result, the previously best-known (1 − 1/e+0.0001)-approximation can be improved to 0.71. Additionally, we examine randomized fixed-price mechanisms when we receive just one single sample from the seller distribution, for both symmetric and asymmetric settings. Our findings reveal that posting the single sample as the price remains optimal among all randomized fixed-price mechanisms.

Publisher's Version

Session 4C

Improved and Deterministic Online Service with Deadlines or Delay
Noam Touitou ORCID logo
(Amazon, Israel)
We consider the problem of online service with delay on a general metric space, first presented by Azar, Ganesh, Ge and Panigrahi (STOC 2017). The best known randomized algorithm for this problem, by Azar and Touitou (FOCS 2019), is O(log2 n)-competitive, where n is the number of points in the metric space. This is also the best known result for the special case of online service with deadlines, which is of independent interest.
In this paper, we present O(logn)-competitive deterministic algorithms for online service with deadlines or delay, improving upon the results from FOCS 2019. Furthermore, our algorithms are the first deterministic algorithms for online service with deadlines or delay which apply to general metric spaces and have sub-polynomial competitiveness.

Publisher's Version
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy ORCID logo, Shi Li ORCID logo, and Varun Suriyanarayana ORCID logo
(Microsoft Research, India; University at Buffalo, USA; Cornell University, USA)
We consider the recourse version of the classical online load balancing problem on unrelated machines, where the algorithm is allowed to re-assign prior jobs. We give a (2+є)-competitive algorithm for the problem with Oє(logn) amortized recourse per job. This is the first O(1)-competitive algorithm for the problem with non-trivial recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an O(loglogn/logloglogn)-competitive algorithm for the problem with O(1) amortized recourse. The best-known bounds from prior work are O(loglogn)-competitive algorithms with O(1) amortized recourse due to Gupta et al., for the special case of the restricted assignment model.
Along the way, we design an algorithm for the recourse version of the online generalized network flow problem (also known as network flow problem with gains). We have a graph with costs and capacities on the edges, and sources arrive online. Upon arrival of a source, we need to send unit flow from the source. In contrast to standard network flow, every edge uv in the network has a gain parameter γuv > 0, meaning that θ-units of flow sent from u across uv becomes γuv θ units of flow when it reaches v. In the recourse version, the algorithm can undo prior flow sent on an edge by incurring a linear cost. We present an online algorithm for the problem with recourse at most O(1/є) times the offline optimum cost flow for the instance when edge capacities are scaled by a factor 1/1+є. This marks an improvement over prior work in two ways: the known algorithms only apply to standard network flow (i.e., unit gains), and secondly, the guarantees held against an offline flow when edge capacities are scaled by a factor of (2+є). As an immediate corollary of this, we also obtain an improved algorithm for the online b-matching problem with reassignment costs.

Publisher's Version
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Hu FuORCID logo, Jiawei Li ORCID logo, and Daogao LiuORCID logo
(Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA)
Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff. In various scenarios, the searching agent may select an option without making a costly inspection. The variant of the Pandora box problem with non-obligatory inspection has attracted interest from both economics and algorithms researchers. Various simple algorithms have proved suboptimal, with the best known 0.8-approximation algorithm due to Guha et al. (2008). No hardness result for the problem was known.
In this work, we show that it is NP-hard to compute an optimal policy for Pandora’s problem with nonobligatory inspection. We also give a polynomial-time approximation scheme (PTAS) that computes policies with an expected payoff at least (1 − є)-fraction of the optimal, for arbitrarily small є > 0. On the side, we show the decision version of the problem to be in NP.

Publisher's Version
Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Hedyeh Beyhaghi ORCID logo and Linda Cai ORCID logo
(Carnegie Mellon University, USA; Princeton University, USA)
Weitzman (1979) introduced Pandora’s box problem as a mathematical model of sequential search with inspection costs, in which a searcher is allowed to select a prize from one of n alternatives. Several decades later, Doval (2018) introduced a close version of the problem, where the searcher does not need to incur the inspection cost of an alternative, and can select it uninspected. Unlike the original problem, the optimal solution to the nonobligatory inspection variant is proved to need adaptivity by Doval (2018), and by recent work of Fu Li and Liu (2022), finding the optimal solution is NP-hard.
Our first main result is a structural characterization of the optimal policy: We show there exists an optimal policy that follows only two different pre-determined orders of inspection, and transitions from one to the other at most once. Our second main result is a polynomial time approximation scheme (PTAS). Our proof involves a novel reduction to a framework developed by Fu Li and Xu (2018), utilizing our optimal two-phase structure. Furthermore, we show Pandora’s problem with nonobligatory inspection belongs to class NP, which by using the hardness result of Fu Li and Liu (2022), settles the computational complexity class of the problem. Finally, we provide a tight 0.8 approximation and a novel proof for committing policies (informally, the set of nonadaptive policies) for general classes of distributions, which was previously shown only for discrete and finite distributions in Guha, Munagala and Sarka (2008).

Publisher's Version
Local and Global Expansion in Random Geometric Graphs
Siqi Liu ORCID logo, Sidhanth Mohanty ORCID logo, Tselil Schramm ORCID logo, and Elizabeth Yang ORCID logo
(University of California at Berkeley, Berkeley, USA; Stanford University, USA)
Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors u1,…,un uniformly at random on Sd−1; then, for each triple i,j,k ∈ [n], add {i,j,k} and all of its subsets to X if and only if ⟨ ui,uj ⟩ ≥ τ, ⟨ ui,uk ⟩ ≥ τ, and ⟨ uj, uk ⟩ ≥ τ. We prove that for every ε > 0, there exists a choice of d = Θ(logn) and τ = τ(ε,d) so that with high probability, X is a high-dimensional expander of average degree nε in which each 1-link has spectral gap bounded away from 1/2.
To our knowledge, this is the first demonstration of a natural distribution over 2-dimensional expanders of arbitrarily small polynomial average degree and spectral link expansion better than 1/2. All previously known constructions are algebraic. This distribution also furnishes an example of simplicial complexes for which the trickle-down theorem is nearly tight.
En route, we prove general bounds on the spectral expansion of random induced subgraphs of arbitrary vertex transitive graphs, which may be of independent interest. For example, one consequence is an almost-sharp bound on the second eigenvalue of random n-vertex geometric graphs on Sd−1, which was previously unknown for most n,d pairs.
The full version of this paper can be found here.

Publisher's Version Info
New High Dimensional Expanders from Covers
Yotam Dikstein ORCID logo
(Weizmann Institute of Science, Israel)
We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but unfortunately only few constructions are known which have arbitrarily small local spectral expansion.
We give a randomized algorithm that takes as input a high dimensional expander X (satisfying some mild assumptions). It outputs a sub-complex YX that is a high dimensional expander and has infinitely many simplicial covers. These covers form new families of bounded-degree high dimensional expanders. The sub-complex Y inherits X’s underlying graph and its links are sparsifications of the links of X. When the size of the links of X is O(log|X|), this algorithm can be made deterministic.
Our algorithm is based on the groups and generating sets discovered by Lubotzky, Samuels and Vishne (2005), that were used to construct the first discovered high dimensional expanders. We show these groups give rise to many more “randomized” high dimensional expanders.
In addition, our techniques also give a random sparsification algorithm for high dimensional expanders, that maintains its local spectral properties. This may be of independent interest.

Publisher's Version
Towards the Erdős-Gallai Cycle Decomposition Conjecture
Matija Bucić ORCID logo and Richard Montgomery ORCID logo
(Institute for Advanced Study, Princeton, USA; Princeton University, USA; University of Warwick, UK)
In the 1960’s, Erdős and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(n loglogn) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log n) cycles and edges, where logn is the iterated logarithm function. Our arguments make use and further develop the theory of robust sublinear expander graphs.

Publisher's Version Video

Session 5A

An Optimal “It Ain’t Over Till It’s Over” Theorem
Ronen Eldan ORCID logo, Avi Wigderson ORCID logo, and Pei Wu ORCID logo
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA)
We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let f be a Boolean function such that the variance of f is Ω(1) and all its individual influences are bounded by τ. We show that when restricting all but a ρ=Ω((log1/τ)−1) fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function =n/ClognClogn.
We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability 1−o(1). This gives a sharp version of the “it ain’t over till it’s over” theorem due to Mossel, O’Donnell, and Oleszkiewicz. Our proof is discrete, and avoids the use of the invariance principle.
We also show two consequences of our above result: (i) As a corollary, we prove that for a uniformly random input x, the block sensitivity of f at x is Ω(log1/τ) with probability 1−o(1). This should be compared with the implication of Kahn, Kalai and Linial’s result, which implies that the average block sensitivity of f is Ω(log1/τ). (ii) Combining our proof with a well-known result due to O’Donnell, Saks, Schramm and Servedio, one can also conclude that: Restricting all but a ρ=Ω(1/√log(1/τ) ) fraction of the coordinates of a monotone function f, then the restricted function has decision tree complexity Ω(τ−Θ(ρ)) with probability Ω(1).

Publisher's Version
Randomized versus Deterministic Decision Tree Size
Arkadev Chattopadhyay ORCID logo, Yogesh Dahiya ORCID logo, Nikhil S. Mande ORCID logo, Jaikumar Radhakrishnan ORCID logo, and Swagato Sanyal ORCID logo
(TIFR, Mumbai, India; IMSc, Chennai, India; QuSoft, Netherlands; CWI, Amsterdam, Netherlands; ICTS, Bengaluru, India; IIT Kharagpur, India)
A classic result of Nisan [SICOMP ’91] states that the deterministic decision tree *depth* complexity of every total Boolean function is at most the cube of its randomized decision tree *depth* complexity. The question whether randomness helps in significantly reducing the *size* of decision trees appears not to have been addressed. We show that the logarithm of the deterministic decision tree size complexity of every total Boolean function on n input variables is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, ignoring a polylogarithmic factor in the input size.
Our result has the following consequences: - The deterministic AND-OR query complexity of a total Boolean function is at most the fourth power of its randomized AND-OR query complexity, ignoring a polylog n factor. - The deterministic AND (OR) query complexity of a total Boolean function is at most the cube of its randomized AND (OR) query complexity, ignoring a polylog n factor. This answers a recent open question posed by Knop, Lovett, McGuire and Yuan [SIGACT News ’21]. - The notion of *rank* of a Boolean function was defined in a classic work of Ehrenfeucht and Haussler [Information and Computation’89] in the context of learning theory, and is characterized by the logarithm of decision tree size up to a logarithmic factor in the input size. Our results confirm a recent conjecture (ignoring a polylog n factor) of Cornelissen, Mande and Patro [FSTTCS ’22], that asserted the equivalence of randomized and deterministic analogs of rank, upto polynomial factors, for all total Boolean functions. - Combined with the above-mentioned work of Ehrenfeucht and Haussler, our result implies that the class of functions computable by randomized decision trees of polynomial size, is PAC-learnable in quasi-polynomial time.
To obtain our main result on decision tree size, we use as an intermediate measure the *block number* of a Boolean function, studied first by Kulkarni and Tal [CJTCS’16], which can be thought of as a counting analog of *block sensitivity* of a Boolean function that played a central role in Nisan’s result mentioned above.

Publisher's Version
Optimal Explicit Small-Depth Formulas for the Coin Problem
Srikanth Srinivasan ORCID logo and Utkarsh Tripathi ORCID logo
(Aarhus University, Denmark; IIT Bombay, India)
The δ-Coin Problem is the problem of distinguishing between a sequence of coin tosses that come up Heads with probability either 1+δ/2 or 1−δ/2. The computational complexity of this problem in various models has been studied in many previous works with various applications related to derandomization, hierarchy theorems, cryptography and meta-complexity.
In this paper, we construct improved small-depth explicit formulas for the coin problem. Specifically, we construct explicit formulas of optimal size exp(O(d(1/δ)d−1)) and information-theoretically optimal sample complexity O(1/δ2) (the sample complexity is the number of coin tosses supplied to the formulas) for this problem, as long as 1/δ ≥ dC· d for a large enough absolute constant C. Previous constructions of size-optimal AC0 formulas for the coin problem were either randomized (and hence non-explicit) or had a much worse sample complexity of (1/δ)Ω(d).
Our improved construction yields better Fixed-Depth Size Hierarchy theorems for uniform classes of small-depth circuits with AND, OR and ⊕ gates.
Our techniques deviate considerably from previous explicit constructions with non-trivial sample complexity due to Limaye, Sreenivasaiah, Venkitesh and the two authors (SICOMP 2021). While the approach there was to derandomize randomized formula constructions based on results of O’Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009), we instead look to derandomize a randomized circuit construction due to Rossman and Srinivasan (Theory of Computing 2019). This leads us to the problem of constructing certain pseudorandom graphs, which we do explicitly using ideas of Viola (Computational Complexity 2014) involving an iterative use of expander graphs. The constructions of these graphs, which are related to dispersers, may be independently interesting.

Publisher's Version
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
Pooya Hatami ORCID logo, William M. Hoza ORCID logo, Avishay Tal ORCID logo, and Roei Tell ORCID logo
(Ohio State University, USA; University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
For any n ∈ ℕ and d = o(loglog(n)), we prove that there is a Boolean function F on n bits and a value γ = 2−Θ(d) such that F can be computed by a uniform depth-(d + 1) AC0 circuit with O(n) wires, but F cannot be computed by any depth-d TC0 circuit with n1 + γ wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth d > 2, which were previously known only for functions outside AC0 such as the parity function. Furthermore, in our result, the AC0 circuit computing F is a monotone *read-once formula* (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage n−γ.
At a high level, our proof strategy combines two prominent approaches in circuit complexity from the last decade: The celebrated *random projections* method of Håstad, Rossman, Servedio, and Tan (J. ACM 2017), which was previously used to show a tight average-case depth hierarchy for AC0; and the line of works analyzing the effect of *random restrictions* on threshold circuits. We show that under a modified version of Håstad, Rossman, Servedio, and Tan’s projection procedure, any depth-d threshold circuit with n1 + γ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth d + 1 maintains structure.

Publisher's Version

Session 5B

Good Quantum LDPC Codes with Linear Time Decoders
Irit Dinur ORCID logo, Min-Hsiu Hsieh ORCID logo, Ting-Chun Lin ORCID logo, and Thomas Vidick ORCID logo
(Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA; California Institute of Technology, USA)
We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain (2m× m)V   →δ0  (2m)Eδ1  2F where V (X-checks) are the vertices, E (qubits) are the edges, and F (Z-checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes CA,CB:2m→2Δ where Δ is the regularity of the underlying Cayley graphs.
One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

Publisher's Version
An Efficient Decoder for a Linear Distance Quantum LDPC Code
Shouzhen Gu ORCID logo, Christopher A. Pattison ORCID logo, and Eugene Tang ORCID logo
(California Institute of Technology, USA; Massachusetts Institute of Technology, USA)
Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.

Publisher's Version
Certified Randomness from Quantum Supremacy
Scott Aaronson ORCID logo and Shih-Han Hung ORCID logo
(University of Texas at Austin, USA)
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits—thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼ 60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.

Publisher's Version
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Dorit Aharonov ORCID logo, Xun Gao ORCID logo, Zeph Landau ORCID logo, Yunchao Liu ORCID logo, and Umesh Vazirani ORCID logo
(Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. The algorithm is based on a quantum analog of noise induced low degree approximations of Boolean functions, which takes the form of the truncation of a Feynman path integral in the Pauli basis.

Publisher's Version

Session 5C

Nearly All 𝑘-SAT Functions Are Unate
József Balogh ORCID logo, Dingding Dong ORCID logo, Bernard Lidický ORCID logo, Nitya Mani ORCID logo, and Yufei Zhao ORCID logo
(University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA)
We prove that 1−o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n → ∞. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.
This paper is the second half of a two-part work solving the problem. The first part, by Dong, Mani, and Zhao, reduces the conjecture to a Turán problem on partially directed hypergraphs. In this paper we solve this Turán problem.

Publisher's Version Info
Kneser Graphs Are Hamiltonian
Arturo Merino ORCID logo, Torsten Mütze ORCID logo, and Namrata ORCID logo
(TU Berlin, Germany; University of Warwick, UK)
For integers ‍k≥ 1 and n≥ 2k+1, the Kneser graph ‍K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph ‍K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n=2k+1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph ‍J(n,k,s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly ‍s. Clearly, we have K(n,k)=J(n,k,0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from ‍1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

Publisher's Version
Random Walks on Rotating Expanders
Gil Cohen ORCID logo and Gal Maor ORCID logo
(Tel Aviv University, Israel)
Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost – the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As an example, when G is a d-regular Ramanujan graph, the power graph Gt has spectral expansion 2Ω(t)D, where D = dt is the regularity of Gt, thus, Gt is 2Ω(t) away from being Ramanujan. This exponential blowup manifests itself in many applications.
In this work we bypass this barrier by permuting the vertices of the given graph after each random step. We prove that there exists a sequence of permutations for which the spectral expansion deteriorates by only a linear factor in t. In the Ramanujan case this yields an expansion of O(tD). We stress that the permutations are tailor-made to the graph at hand and require no randomness to generate.
Our proof, which holds for all sufficiently high girth graphs, makes heavy use of the powerful framework of finite free probability and interlacing families that was developed in a seminal sequence of works by Marcus, Spielman and Srivastava.

Publisher's Version
Algorithmic Applications of Hypergraph and Partition Containers
Or Zamir ORCID logo
(Princeton University, USA)
We present a general method to convert algorithms into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum degree is larger than the average degree by at most a constant factor. This family of inputs vastly generalizes several families of inputs for which we commonly have improved algorithms, including bounded-degree inputs and random inputs. It also generalizes families of inputs for which we don’t usually have faster algorithms, including regular-inputs of arbitrarily high degree and very dense inputs. We apply our method to achieve breakthroughs in exact algorithms for several central NP-Complete problems including k-SAT, Graph Coloring, and Maximum Independent Set.
Our main tool is the first algorithmic application of the relatively new Hypergraph Container Method (Saxton and Thomason 2015, Balogh, Morris and Samotij 2015). This recent breakthrough, which generalizes an earlier version for graphs (Kleitman and Winston 1982, Sapozhenko 2001), has been used extensively in recent years in extremal combinatorics. An important component of our work is the generalization of (hyper-)graph containers to Partition Containers.

Publisher's Version

Session 6: Best Student Papers

Subsampling Suffices for Adaptive Data Analysis
Guy Blanc ORCID logo
(Stanford University, USA)
Ensuring that analyses performed on a dataset are representative of the entire population is one of the central problems in statistics. Most classical techniques assume that the dataset is independent of the analyst’s query and break down in the common setting where a dataset is reused for multiple, adaptively chosen, queries. This problem of adaptive data analysis was formalized in the seminal works of Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014).
We identify a remarkably simple set of assumptions under which the queries will continue to be representative even when chosen adaptively: The only requirements are that each query takes as input a random subsample and outputs few bits. This result shows that the noise inherent in subsampling is sufficient to guarantee that query responses generalize. The simplicity of this subsampling-based framework allows it to model a variety of real-world scenarios not covered by prior work.
In addition to its simplicity, we demonstrate the utility of this framework by designing mechanisms for two foundational tasks, statistical queries and median finding. In particular, our mechanism for answering the broadly applicable class of statistical queries is both extremely simple and state of the art in many parameter regimes.

Publisher's Version Info
The Power of Multi-step Vizing Chains
Aleksander Bjørn Grodt Christiansen ORCID logo
(DTU, Denmark)
Recent papers have addressed different variants of the (Δ + 1)-edge-colouring problem by concatenating or gluing together many Vizing chains to form what Bernshteyn coined multi-step Vizing chains. In this paper, we consider the most general definition of this term and apply different multi-step Vizing chain constructions to prove combinatorial properties of edge-colourings that lead to (improved) algorithms for computing edge-colouring across different models of computation. This approach seems especially powerful for constructing augmenting subgraphs which respect some notion of locality.
First, we construct strictly local multi-step Vizing chains and use them to show a local version of Vizing’s Theorem thus confirming a recent conjecture of Bonamy, Delcourt, Lang and Postle. That is, we show that there exists a proper edge-colouring of a graph such that every edge uv receives a colour from the list {1,2, …, max{d(u),d(v)}+1}. Our proof is constructive and also implies an O(n2 Δ) time algorithm for computing such a colouring.
Then, we show that for any uncoloured edge there exists an augmenting subgraph of size O7logn), answering an open problem of Bernshteyn. Chang, He, Li, Pettie and Uitto show a lower bound of Ω(Δ logn/Δ) for the size of augmenting subgraphs, so the upper bound is asymptotically tight up to Δ factors. These ideas also extend to give a faster deterministic LOCAL algorithm for (Δ + 1)-edge-colouring running in Õ((Δ)log6 n) rounds. These results improve the dependency on logn compared to the recent breakthrough result of Bernshteyn, who showed the existence of augmenting subgraphs of size O6log2 n), and used these to give the first (Δ + 1)-edge-colouring algorithm in the LOCAL model running in O((Δ, logn)) rounds.
Finally for dynamic graphs, we show how to maintain a(1+ε)Δ-edge-colouring fully adaptive to Δ in O−6 log9 n log6 Δ) worst-case update time w.h.p without any restrictions on Δ. This should be compared to the edge-colouring algorithm of Duan, He and Zhang that runs in O−4log8 n) amortised update time w.h.p under the condition that Δ = Ω(ε−2log2 n). Our algorithm avoids the use of O−1logn) copies of the graph, resulting in a smaller space consumption and an algorithm with provably low recourse.

Publisher's Version

Session 7A

Capturing One-Way Functions via NP-Hardness of Meta-Complexity
Shuichi Hirahara ORCID logo
(National Institute of Informatics, Japan)
A one-way function is a function that is easy to compute but hard to invert *on average*. We establish the first characterization of a one-way function by *worst-case* hardness assumptions, by introducing a natural meta-computational problem whose NP-hardness (and the worst-case hardness of NP) characterizes the existence of a one-way function. Specifically, we generalize the notion of time-bounded conditional Kolmogorov complexity to *distributional Kolmogorov complexity*, and prove that a one-way function exists if and only if it is NP-hard to approximate the distributional Kolmogorov complexity under randomized polynomial-time reductions and NP is hard in the worst case. We also propose the *Meta-Complexity Padding Conjecture*, which postulates that distributional Kolmogorov complexity is paddable by an approximation-preserving reduction. Under this conjecture, we prove that the worst-case hardness of an approximate version of the Minimum Circuit Size Problem characterizes the existence of a one-way function.
Our results extend the emerging paradigm of meta-complexity, which suggests that proving NP-hardness of meta-computational problems (i.e., problems that ask to compute complexity) is sufficient to exclude errorless Heuristica and error-prone Pessiland from Impagliazzo's five worlds. The key technical contribution is to conditionally close the gap between errorless and error-prone average-case complexities by combining Nanashima's proof techniques of showing "limits" of black-box reductions (ITCS'21) with non-black-box worst-case-to-average-case reductions of Hirahara (FOCS'18).

Publisher's Version
A Duality between One-Way Functions and Average-Case Symmetry of Information
Shuichi Hirahara ORCID logo, Rahul IlangoORCID logo, Zhenjian Lu ORCID logo, Mikito Nanashima ORCID logo, and Igor C. OliveiraORCID logo
(National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK)
Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds.
We show that one-way functions exist if and only if (probabilistic) time-bounded SoI fails on average, i.e., if there is a samplable distribution of pairs (x,y) of strings such that SoI for pKt complexity fails for many of these pairs. Our techniques rely on recent perspectives offered by probabilistic Kolmogorov complexity and meta-complexity, and reveal further equivalences between inverting one-way functions and the validity of key properties of Kolmogorov complexity in the time-bounded setting: (average-case) language compression and (average-case) conditional coding.
Motivated by these results, we investigate correspondences of this form for the worst-case hardness of (i.e., ‍NPBPP) and for the average-case hardness of (i.e., DistNPHeurBPP), respectively. Our results establish the existence of similar dualities between these computational assumptions and the failure of results from Kolmogorov complexity in the time-bounded setting. In particular, these characterizations offer a novel way to investigate the main hardness conjectures of complexity theory (and the relationships among them) through the lens of Kolmogorov complexity and its properties.

Publisher's Version
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Jiatu LiORCID logo and Igor C. OliveiraORCID logo
(Tsinghua University, China; University of Warwick, UK)
While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek’s theory APC1 (2007) and of higher levels of Buss’s hierarchy S2i (1986) has been a more elusive task. Even in the more restricted setting of Cook’s theory PV (1975), known results often rely on a less natural formalization that encodes a complexity statement using a collection of sentences instead of a single sentence. This is done to reduce the quantifier complexity of the resulting sentences so that standard witnessing results can be invoked.
In this work, we establish unprovability results for stronger theories and for sentences of higher quantifier complexity. In particular, we unconditionally show that APC1 cannot prove strong complexity lower bounds separating the third level of the polynomial hierarchy. In more detail, we consider non-uniform average-case separations, and establish that APC1 cannot prove a sentence stating that
* ∀ nn0 ∃ fn ∈ Π3-SIZE[nd] that is (1/n)-far from every Σ3-SIZE[2nδ] circuit.
This is a consequence of a much more general result showing that, for every i ≥ 1, strong separations for Πi-SIZE[poly(n)] versus Σi-SIZE[2nΩ(1)] cannot be proved in the theory TPVi consisting of all true ∀ Σi−1b-sentences in the language of Cook’s theory PV.
Our argument employs a convenient game-theoretic witnessing result that can be applied to sentences of arbitrary quantifier complexity. We combine it with extensions of a technique introduced by Krajicek (2011) that was recently employed by Pich and Santhanam (2021) to establish the unprovability of lower bounds in PV (i.e., the case i =1 above, but under a weaker formalization) and in a fragment of APC1.

Publisher's Version
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Yeyuan Chen ORCID logo, Yizhi Huang ORCID logo, Jiatu Li ORCID logo, and Hanlin RenORCID logo
(Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK)
The range avoidance problem, denoted as C-Avoid, asks to find a non-output of a given C-circuit C:0,1^n -> 0,1^l with stretch l>n. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit lower bounds, Ren, Santhanam, and Wang (FOCS’22) established a framework to design FP^NP algorithms for C-Avoid via slightly non-trivial data structures related to C. However, a major drawback of their approach is the lack of unconditional results even for C=AC^0.
In this work, we present the first unconditional FP^NP algorithm for ACC^0-Avoid. Indeed, we obtain FP^NP algorithms for the following stronger problems:
(ACC^0-RemotePoint). Given C:0,1^n -> 0,1^l for some l=quasipoly(n) such that each output bit of C is computed by a quasipoly(n)-size AC^0[m] circuit, we can find some y ∈0,1^l in FP^NP such that for every x ∈0, 1^n, the relative Hamming distance between y and C(x) is at least 1/2-1/poly(n). This problem is the ”average-case” analogue of ACC^0-Avoid.
(ACC^0-AvgPartialHard). Given x_1,…,x_l ∈0,1^n for some l=quasipoly(n), we can compute l bits y_1,…,y_l ∈0,1 in FP^NP such that for every 2^logc(n)-size ACC^0 circuit C, Pr_i[C(x_i)≠y_i]≥1/2-1/poly(n), where c=O(1). This problem generalises the strong average-case circuit lower bounds against ACC^0 in a different way.
Our algorithms can be seen as natural generalisations of the best known almost-everywhere average-case lower bounds against ACC^0 circuits by Chen, Lyu, and Williams (FOCS’20). Note that both problems above have been studied prior to our work, and no FP^NP algorithm was known even for weak circuit classes such as GF(2)-linear circuits and DNF formulas.
Our results follow from a strengthened algorithmic method: slightly non-trivial algorithms for the Satisfying-Pairs problem for C implies FP^NP algorithms for C-Avoid (as well as C-RemotePoint and C-AvgPartialHard). Here, given C-circuits C_i and inputs x_j, the C-Satisfying-Pairs problem asks to (approximately) count the number of pairs (i,j) such that C_i(x_j)=1.
A technical contribution of this work is a construction of a short, smooth, and rectangular PCP of Proximity that combines two previous PCP constructions, which may be of independent interest. It serves as a key tool that allows us to generalise the framework for Avoid to the average-case scenarios.

Publisher's Version
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Yizhi Huang ORCID logo, Rahul IlangoORCID logo, and Hanlin RenORCID logo
(Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK)
It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.
In this work, we prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Our key idea is to use cryptographic constructions in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present both conditional and unconditional hardness of approximation results as follows.
1. Assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity (Kt(x | y)) in the regime where t >> |y|. Previously, the best hardness of approximation known was a |x|1/ (loglog|x|) factor and only in the sublinear regime (t << |y|).
2. Unconditionally, we show that for any constant c > 1, the Minimum Oracle Circuit Size Problem (MOCSP) is NP-hard to approximate, where Yes instances have circuit complexity at most s, and No instances have circuit complexity at least sc. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC’13). Previously, it was unknown whether it is NP-hard to distinguish between oracle circuit complexity s versus 10slogN.
3. Finally, we define a “multi-valued” version of MCSP, called mvMCSP, and show that w.p. ‍1 over a random oracle O, it is NP-hard to approximate mvMCSPO under quasi-polynomial-time reductions with an O oracle. Intriguingly, this result follows almost directly from the security of Micali’s CS Proofs (Micali, SICOMP’00).
In conclusion, we give three results convincingly demonstrating the power of cryptographic techniques in proving NP-hardness of approximating meta-complexity.

Publisher's Version
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Rahul IlangoORCID logo, Jiatu LiORCID logo, and R. Ryan Williams ORCID logo
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit C:{0,1}n→{0,1}m, where m>n. Although at least half of the strings of length m are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS’21) and Ren, Wang, and Santhanam (FOCS’ 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e.g., Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist?
In this work, we prove under the existence of subexponentially secure indistinguishability obfuscation (iO) that polynomial-time deterministic algorithms for Avoid imply NP=coNP. Combining this with Jain, Lin, and Sahai’s recent breakthrough construction of iO from well-founded assumptions (STOC’21, EUROCRYPT’22), we provide the first plausible evidence that Avoid has no efficient deterministic algorithm. Moreover, we also prove the hardness of Avoid based on polynomially-secure iO and a weaker variant of the Nondeterministic Exponential Time Hypothesis (NETH).
Extending our techniques, we prove a surprising separation in bounded arithmetic, conditioned on similar assumptions. Assuming subexponentially secure iO and coNP is not infinitely often in , we show that Avoid has no deterministic polynomial-time algorithm even when we are allowed O(1) queries to an oracle that can invert the given input circuit on an arbitrarily chosen m-bit string. It follows that the dual Weak Pigeonhole Principle, the combinatorial principle underlying Avoid, is not provable in Cook’s theory PV1. This gives (under plausible assumptions) the first separation of Cook’s theory PV1 for polynomial-time reasoning and Jeřábek’s theory APV1 for probabilistic polynomial-time reasoning.

Publisher's Version

Session 7B

NLTS Hamiltonians from Good Quantum Codes
Anurag Anshu ORCID logo, Nikolas P. Breuckmann ORCID logo, and Chinmay Nirkhe ORCID logo
(Harvard University, USA; University of Bristol, UK; MIT-IBM Watson AI Lab, USA)
The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). We prove this conjecture by showing that a particular family of constant-rate and linear-distance qLDPC codes correspond to NLTS local Hamiltonians, although we believe this to be true for all current constructions of good qLDPC codes.

Publisher's Version
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Qipeng Liu ORCID logo, Ran Raz ORCID logo, and Wei Zhan ORCID logo
(Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA)
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω(n2) bits of classical memory or an exponential number (in ‍n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n2) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size c n (for some constant c>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix M: A × X → {−1,1} the following learning task. An unknown x is sampled uniformly at random from a concept class X, and a learning algorithm tries to uncover x by seeing streaming of random samples (ai, bi = M(ai, x)) where for every i, aiA is chosen uniformly at random. Assume that k,ℓ,r are integers such that any submatrix of M of at least 2k·|A| rows and at least 2−ℓ·|X| columns, has a bias of at most 2r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to M needs either (1) Ω(k · ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2Ω(r) random samples, to achieve a success probability at least 2O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on n bits), proving that security holds even in the presence of a quantum adversary with at most c n2 bits of classical memory and c n bits of quantum memory (for some constant c>0).

Publisher's Version
Quantum Depth in the Random Oracle Model
Atul Singh Arora ORCID logo, Andrea ColadangeloORCID logo, Matthew Coudron ORCID logo, Alexandru Gheorghiu ORCID logo, Uttam Singh ORCID logo, and Hendrik Waldner ORCID logo
(California Institute of Technology, USA; University of Washington, USA; National Institute of Standards and Technology, USA; University of Maryland, USA; Chalmers University of Technology, Sweden; ETH Zurich, Switzerland; Polish Academy of Sciences, Poland; IIIT Hyderabad, India; University of Maryland, College Park, USA; MPI-SP, Germany)
We give a comprehensive characterisation of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle:
(a) BPPQNCBPPBQP. This refutes Jozsa’s conjecture in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson’s ten semi-grand challenges in quantum computing.
(b) BPPQNCQNCBPP and QNCBPPBPPQNC. This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements. We also show that BPPQNC and BPPQNC are both strictly contained in BPPQNCBPP.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry.

Publisher's Version
Multidimensional Quantum Walks
Stacey Jeffery ORCID logo and Sebastian Zur ORCID logo
(CWI, Amsterdam, Netherlands; QuSoft, Netherlands)
While the quantum query complexity of k-distinctness is known to be O(n3/4 − 1/4(2k−1)) for any constant k≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was O(n1−1/k). We give a new upper bound of O(n3/4 − 1/4(2k−1)) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O(n) queries and O(n2) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.

Publisher's Version
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Alexander M. Dalzell ORCID logo, Nicola Pancotti ORCID logo, Earl T. Campbell ORCID logo, and Fernando G.S.L. Brandão ORCID logo
(AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK)
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), Ising spin glasses (p-spin model), and k-local constraint satisfaction problems (k-CSP). We show that either (a) the algorithm finds the optimal solution in time O*(2(0.5−c)n) for an n-independent constant c, a 2cn advantage over Grover’s algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a (1−η) approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of η. Additionally, we show that for a large fraction of random instances from the k-spin model and for any fully satisfiable or slightly frustrated k-CSP formula, statement (a) is the case. The algorithm and its analysis are largely inspired by Hastings’ short-path algorithm.

Publisher's Version
Approximating Binary Longest Common Subsequence in Almost-Linear Time
Xiaoyu He ORCID logo and Ray Li ORCID logo
(Princeton University, USA; University of California at Berkeley, Berkeley, USA)
The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programming algorithm gives an exact algorithm in quadratic time, and this is essentially best possible under plausible fine-grained complexity assumptions, so a natural problem is to find faster approximation algorithms. When the inputs are two binary strings, there is a simple 1/2-approximation in linear time: compute the longest common all-0s or all-1s subsequence. It has been open whether a better approximation is possible even in truly subquadratic time. Rubinstein and Song showed that the answer is yes under the assumption that the two input strings have equal lengths. We settle the question, generalizing their result to unequal length strings, proving that, for any ε>0, there exists δ>0 and a (1/2+δ)-approximation algorithm for binary LCS that runs in n1+ε time. As a consequence of our result and a result of Akmal and Vassilevska-Williams, for any ε>0, there exists a (1/q+δ)-approximation for LCS over q-ary strings in n1+ε time.
Our techniques build on the recent work of Guruswami, He, and Li who proved new bounds for error-correcting codes tolerating deletion errors. They prove a combinatorial “structure lemma” for strings which classifies them according to their oscillation patterns. We prove and use an algorithmic generalization of this structure lemma, which may be of independent interest.

Publisher's Version

Session 7C

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
Julia Chuzhoy ORCID logo and Ruimin Zhang ORCID logo
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n-vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter є, achieves approximation factor (loglogn)2O(1/є3), and has amortized update time O(nєlogL) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O(2O(1/є)· logn· loglogL), and query time for shortest-path query is O(|E(P)|+2O(1/є)· logn· loglogL), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Θ(m) amortized update time and better than Θ(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.
In order to obtain these results, we consider an intermediate problem, called Recursive Dynamic Neighborhood Cover (RecDynNC), that was formally introduced in [Chuzhoy, STOC ’21]. At a high level, given an undirected edge-weighted graph G undergoing an online sequence of edge deletions, together with a distance parameter D, the goal is to maintain a sparse D-neighborhood cover of G, with some additional technical requirements. Our main technical contribution is twofolds. First, we provide a black-box reduction from APSP in fully dynamic graphs to the RecDynNC problem. Second, we provide a new deterministic algorithm for the RecDynNC problem, that, for a given precision parameter є, achieves approximation factor (loglogm)2O(1/є2), with total update time O(m1+є), where m is the total number of edges ever present in G. This improves the previous algorithm of [Chuzhoy, STOC ’21], that achieved approximation factor (logm)2O(1/є) with similar total update time. Combining these two results immediately leads to the deterministic algorithm for fully-dynamic APSP with the guarantees stated above.

Publisher's Version
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster ORCID logo, Yasamin Nazari ORCID logo, and Maximilian Probst Gutenberg ORCID logo
(University of Salzburg, Austria; ETH Zurich, Switzerland)
We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in O(loglogn) time.
Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than no(1) update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.

Publisher's Version
Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon ORCID logo and Amitai Uzrad ORCID logo
(Tel Aviv University, Israel)
The minimum set cover (MSC) problem admits two classic algorithms: a greedy lnn-approximation and a primal-dual f-approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably — one cannot improve these approximations under hardness results by more than a factor of (1+є), for any constant є > 0.
In their pioneering work, Gupta et al. [STOC’17] showed that the greedy algorithm can be dynamized to achieve O(logn)-approximation with update time O(f logn). Building on this result, Hjuler et al. [STACS’18] dynamized the greedy minimum dominating set (MDS) algorithm, achieving a similar approximation with update time O(Δ logn) (the analog of O(f logn)), albeit for unweighted instances. The approximations of both algorithms, which are the state-of-the-art, exceed the static lnn-approximation by a rather large constant factor. In sharp contrast, the current best dynamic primal-dual MSC algorithms, by Bhattacharya et al. [SODA’21] and Assadi-Solomon [ESA’21], both with update time O(f2) — exceed the static f-approximation by a factor of (at most) 1+є, for any є > 0.
This paper aims to bridge the gap between the best approximation factor of the dynamic greedy MSC and MDS algorithms and the static lnn bound. We present dynamic algorithms for weighted greedy MSC and MDS with approximation (1+є)lnn for any є > 0, while achieving the same update time (ignoring dependencies on є) of the best previous algorithms (with approximation significantly larger than lnn). Moreover, we prove that the same algorithms achieve O(min{ logn, logC }) amortized recourse; the recourse measures the number of changes to the maintained structure per update step, and the cost of each set lies in the range [1/C,1].

Publisher's Version
Improved Dynamic Colouring of Sparse Graphs
Aleksander Bjørn Grodt Christiansen ORCID logo, Krzysztof Nowicki ORCID logo, and Eva Rotenberg ORCID logo
(DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland)
Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are computable upon query time. We give a deterministic algorithm that uses O2) colours for a dynamic graph of arboricity α, and a randomised algorithm that uses O(min{α logα, α logloglogn}) colours in the oblivious adversary model. Our deterministic algorithm has update- and query times polynomial in α and logn, and our randomised algorithm has amortised update- and query time that with high probability is polynomial in logn with no dependency on the arboricity.
Thus, we improve the number of colours exponentially compared to the state-of-the art for implicit colouring, namely from O(2α) colours, and we approach the theoretical lower bound of Ω(α) for this arboricity-parameterised approach. Simultaneously, our randomised algorithm improves the update- and query time to run in time solely polynomial in logn with no dependency on α. Our algorithms are fully adaptive to the current value of the dynamic arboricity at query or update time.

Publisher's Version
Dynamic Maxflow via Dynamic Interior Point Methods
Jan van den Brand ORCID logo, Yang P. LiuORCID logo, and Aaron Sidford ORCID logo
(Georgia Institute of Technology, USA; Stanford University, USA)
In this paper we provide an algorithm for maintaining a (1−є)-approximate maximum flow in a dynamic, capacitated graph undergoing edge insertions. Over a sequence of m insertions to an n-node graph where every edge has capacity O(poly(m)) our algorithm runs in time O(mn · є−1). To obtain this result we design dynamic data structures for the more general problem of detecting when the value of the minimum cost circulation in a dynamic graph undergoing edge insertions achieves value at most F (exactly) for a given threshold F. Over a sequence m insertions to an n-node graph where every edge has capacity O(poly(m)) and cost O(poly(m)) we solve this thresholded minimum cost flow problem in O(mn). Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method by [Chen et al. ‍FOCS 2022] used to obtain an almost linear time algorithm for minimum cost flow, and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.

Publisher's Version
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad ORCID logo, Sagnik Mukhopadhyay ORCID logo, Danupon NanongkaiORCID logo, and Ta-Wei Tu ORCID logo
(KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany)
We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a “unified” algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows.
Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with Õk(n+rr) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and Õk hides poly(k, log(n)). This implies the following consequences. (i) An improvement over the Õk(nr) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS’19] for matroid union in the traditional rank-query model. (ii) An Õk(|E|+|V|√|V|)-time algorithm for the k-disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the Õk(|V|√|E|) bounds of Gabow-Westermann [STOC’88] and Gabow [STOC’91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility.
Matroid intersection. We show a matroid intersection algorithm with Õ(nr) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP’85], graphic matroid intersection [Gabow-Xu FOCS’89], simple job scheduling matroid intersection [Xu-Gabow ISAAC’94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a “unified” algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously.
Lower bounds. We show simple super-linear (Ω(nlogn)) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log2(3)no(n) bound by Harvey [SODA’08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS’19].

Publisher's Version

Session 8A

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
Riddhi Ghosal ORCID logo, Yuval Ishai ORCID logo, Alexis Korb ORCID logo, Eyal Kushilevitz ORCID logo, Paul Lou ORCID logo, and Amit Sahai ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Technion, Israel)
The existence of “unstructured” hard languages in NP  ∩ coNP is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether P is separated from NPcoNP relative to a random oracle, a question that remained open ever since. While a hard language in NP  ∩ coNP can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.
We give the first evidence for the existence of unstructured hard languages in NP  ∩ coNP by showing that if UPRP, which follows from the existence of injective one-way functions, the answer to Bennett and Gill’s question is affirmative: with probability 1 over a random oracle O, we have that PONPOcoNPO. Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in NP  ∩ coNP from cryptographic hash functions.
The above conditional separation builds on a new construction of non-interactive zero-knowledge (NIZK) proofs, with a computationally unbounded prover, to convert a hard promise problem into a hard language. We obtain such NIZK proofs for NP, with a uniformly random reference string, from a special kind of hash function which is implied by (an unstructured) random oracle. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other structured primitives, as well as with (computationally sound) NIZK arguments in the random oracle model.

Publisher's Version
On the Consistency of Circuit Lower Bounds for Non-deterministic Time
Albert Atserias ORCID logo, Sam Buss ORCID logo, and Moritz Müller ORCID logo
(Universitat Politècnica de Catalunya, Spain; Centre de Recerca Matemàtica, Spain; University of California at San Diego, San Diego, USA; University of Passau, Germany)
We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory ‍V20 is consistent with the conjecture that ‍NEXP ‍⊈ ‍P/poly, i.e., some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds.

Publisher's Version
Shellability Is Hard Even for Balls
Pavel Paták ORCID logo and Martin Tancer ORCID logo
(Charles University, Prague, Czechia; Czech Technical University, Prague, Czechia)
The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary) as soon as d ≥ 3. This extends our earlier work with Goaoc, Patáková and Wagner on hardness of shellability of 2-complexes and answers some questions implicitly raised by Danaraj and Klee in 1978 and explicitly mentioned by Santamaría-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng and Walkington; and that shellability is NP-hard for 2-complexes embeddable in 3-space, answering another question of Santamaría-Galvis and Woodroofe (in a slightly stronger form than what is given by the main result).

Publisher's Version
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Jin-Yi Cai ORCID logo and Ashwin Maran ORCID logo
(University of Wisconsin-Madison, USA)
We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix H defining a graph homomorphism from all planar graphs GZH(G), we completely classify the computational complexity of this problem according to the matrix H. We show that for every H, the problem is either polynomial time computable or #P-hard. The P-time computable cases consist of precisely those that are P-time computable for general graphs (a complete classification is known) or computable by Valiant’s holographic algorithm via matchgates. We also prove several results about planar graph homomorphisms for general domain size q. The proof uses mainly analytic arguments.

Publisher's Version

Session 8B

Approximating Nash Social Welfare by Matching and Local Search
Jugal GargORCID logo, Edin HusićORCID logo, Wenzheng Li ORCID logo, László A. VéghORCID logo, and Jan Vondrák ORCID logo
(University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK)
For any >0, we give a simple, deterministic (4+)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an (ω + 2 + ) -approximation if the ratio between the largest weight and the average weight is at most ω.
We also show that the 12-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time which is both 12-EFX and a (8+)-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under 12-EFX was linear in the number of agents.

Publisher's Version
Multi-agent Contracts
Paul Dütting ORCID logo, Tomer Ezra ORCID logo, Michal Feldman ORCID logo, and Thomas Kesselheim ORCID logo
(Google Research, Switzerland; Sapienza University of Rome, Italy; Tel Aviv University, Israel; Microsoft Research, Israel; University of Bonn, Germany)
We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy.
Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of “prices” and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest.
Our second main result is an Ω(√n) impossibility for settings with n agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.

Publisher's Version
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich ORCID logo, Davis Issac ORCID logo, Nikhil Kumar ORCID logo, Nadym Mallek ORCID logo, and Ziena Zeif ORCID logo
(Hasso Plattner Institute, Potsdam, Germany)
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multicommodity flow of value f, and a multicut of capacity c such that fcO(ln(r+1)) · f. It is well known that the multiflow-multicut gap on an r-vertex (constant degree) expander graph can be Ω(lnr), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time O(ln(r+1))-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.

Publisher's Version
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster ORCID logo, Lars Rohwedder ORCID logo, and Andreas Wiese ORCID logo
(TU Munich, Germany; Maastricht University, Netherlands)
An important objective function in the scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs, where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. The currently best known polynomial time algorithm for the problem is a (2+є)-approximation by Rohwedder and Wiese [STOC 2021], which builds on the prior break-through result by Batra, Garg, and Kumar [FOCS 2018] who found the first pseudo-polynomial time constant factor approximation algorithm for the problem, and on the result by Feige, Kulkarni, and Li [SODA 2019] who turned the latter into a polynomial time algorithm. However, it remains open whether the problem admits a PTAS.
We answer this question in the affirmative and present a polynomial time (1+є)-approximation algorithm for weighted flow time on a single machine. We use a reduction of the problem to a geometric covering problem, which was introduced in the mentioned (2+є)-approximation algorithm and which loses only a factor of 1+є in the approximation ratio. However, unlike that algorithm, we solve the resulting instances of the covering problem exactly, rather than losing a factor 2+є. Key for this is to identify and exploit structural properties of instances of that problem covering problem which arise in the reduction from weighted flow time.

Publisher's Version

Session 8C

Random Graph Matching at Otter’s Threshold via Counting Chandeliers
Cheng MaoORCID logo, Yihong WuORCID logo, Jiaming XuORCID logo, and Sophie H. YuORCID logo
(Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA)
We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq→∞ and the edge correlation coefficient ρ satisfies ρ2>α ≈ 0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs.
The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees.

Publisher's Version
Uniformly Random Colourings of Sparse Graphs
Eoin Hurley ORCID logo and François Pirot ORCID logo
(Unaffiliated, Heidelberg, Germany; Université Paris-Saclay, France)
We analyse uniformly random proper k-colourings of sparse graphs with maximum degree Δ in the regime Δ < klnk . This regime corresponds to the lower side of the shattering threshold for random graph colouring, a paradigmatic example of the shattering threshold for random Constraint Satisfaction Problems. We prove a variety of results about the solution space geometry of colourings of fixed graphs, generalising work of Achlioptas and Coja-Oghlan, and Molloy on random graphs, and justifying the performance of stochastic local search algorithms in this regime. Our central proof relies only on elementary techniques, namely the first-moment method and a quantitative induction, yet it strengthens list-colouring results due to Vu, and more recently Davies, Kang, P., and Sereni, and generalises state-of-the-art bounds from Ramsey theory in the context of sparse graphs. It further yields an approximately tight lower bound on the number of colourings, also known as the partition function of the Potts model, with implications for efficient approximate counting.

Publisher's Version
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
Bernhard Haeupler ORCID logo, D. Ellis Hershkowitz ORCID logo, and Thatchaphol SaranurakORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA)
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow paths have length at most h. Many well-studied algorithmic primitives—such as maximal and maximum length-constrained disjoint paths—are special cases of h-length flows. Likewise the optimal h-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives.
In this work, we give the first efficient algorithms for computing (1 − є)-approximate h-length flows that are nearly “as integral as possible.” We give deterministic algorithms that take Õ(poly(h, 1/є)) parallel time and Õ(poly(h, 1/є) · 2O(√logn)) distributed CONGEST time. We also give a CONGEST algorithm that succeeds with high probability and only takes Õ(poly(h, 1/є)) time.
Using our h-length flow algorithms, we give the first efficient deterministic CONGEST algorithms for the maximal disjoint paths problem with length constraints—settling an open question of Chang and Saranurak (FOCS 2020)—as well as essentially-optimal parallel and distributed approximation algorithms for maximum length-constrained disjoint paths. The former greatly simplifies deterministic CONGEST algorithms for computing expander decompositions. We also use our techniques to give the first efficient and deterministic (1−є)-approximation algorithms for bipartite b-matching in CONGEST. Lastly, using our flow algorithms, we give the first algorithms to efficiently compute h-length cutmatches, an object at the heart of recent advances in length-constrained expander decompositions.

Publisher's Version
Tight Conditional Lower Bounds for Vertex Connectivity Problems
Zhiyi Huang ORCID logo, Yaowei Long ORCID logo, Thatchaphol SaranurakORCID logo, and Benyu Wang ORCID logo
(Tsinghua University, China; University of Michigan, USA)
We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in m1+o(1) time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in m1+o(1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too.
We show that this hope is impossible, assuming conjectures on finding 4-cliques. Moreover, we essentially settle the complexity landscape by giving tight bounds for combinatorial algorithms in dense graphs. There are three separate regimes:
(1) all-pairs and Steiner vertex connectivity have complexity Θ(n4),
(2) single-source vertex connectivity has complexity Θ(n3), and
(3) single-source-single-sink and global vertex connectivity have complexity Θ(n2).
For graphs with general density, we obtain tight bounds of Θ(m2), Θ(m1.5), Θ(m), respectively, assuming Gomory-Hu trees for element connectivity can be computed in almost-linear time.

Publisher's Version

Session 9A

Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò ORCID logo, Shiri Chechik ORCID logo, Keerti Choudhary ORCID logo, Sarel Cohen ORCID logo, Tobias Friedrich ORCID logo, Simon Krogmann ORCID logo, and Martin Schirneck ORCID logo
(University of L’Aquila, Italy; Tel Aviv University, Israel; IIT Delhi, India; Academic College of Tel Aviv-Yaffo, Israel; Hasso Plattner Institute, Potsdam, Germany; University of Vienna, Austria)
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 1 is a data structure that preprocesses a given undirected, unweighted graph G with n vertices and m edges, and a positive integer f. When queried with a pair of vertices s, t and a set F of at most f edges, it returns a σ-approximation of the s-t-distance in GF.
We study f-DSOs that take subquadratic space. Thorup and Zwick [JACM ‍2015] showed that this is only possible for σ ≥ 3. We present, for any constant f ≥ 1 and α ∈ (0, 1/2), and any ε > 0, an f-DSO with stretch 3 + that takes O(n2−α/f+1/ε) · O(logn/ε)f+1 space and has an O(nα2) query time.
We also give an improved construction for graphs with diameter at most D. For any constant k, we devise an f-DSO with stretch 2k−1 that takes O(Df+o(1) n1+1/k) space and has O(Do(1)) query time, with a preprocessing time of O(Df+o(1) mn1/k).
Chechik, Cohen, Fiat, and Kaplan [SODA 2017] presented an f-DSO with stretch 1+ and preprocessing time O(n5) · O(logn/ε)f, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to O(mn2) · O(logn/ε)f.

Publisher's Version
External Memory Fully Persistent Search Trees
Gerth Stølting Brodal ORCID logo, Casper Moldrup Rysgaard ORCID logo, and Rolf Svenning ORCID logo
(Aarhus University, Denmark)
We present the first fully-persistent external-memory search tree achieving amortized I/O bounds matching those of the classic (ephemeral) B-tree by Bayer and McCreight. The insertion and deletion of a value in any version requires amortized O(logB Nv) I/Os and a range reporting query in any version requires worst-case O(logB Nv + K/B) I/Os, where K is the number of values reported, Nv is the number of values in the version v of the tree queried or updated, and B is the external-memory block size. The data structure requires space linear in the total number of updates. Compared to the previous best bounds for fully persistent B-trees [Brodal, Sioutas, Tsakalidis, and Tsichlas, SODA 2012], this paper eliminates from the update bound an additive term of O(log2 B) I/Os. This result matches the previous best bounds for the restricted case of partial persistent B-trees [Arge, Danner and Teh, JEA 2003]. Central to our approach is to consider the problem as a dynamic set of two-dimensional rectangles that can be merged and split.

Publisher's Version
The Rate of Interactive Codes Is Bounded Away from 1
Klim Efremenko ORCID logo, Gillat Kol ORCID logo, Dmitry Paramonov ORCID logo, and Raghuvansh R. Saxena ORCID logo
(Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA)
Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability ‍є>0 independently, with only a 1+O(√(є)) blowup to the communication. In particular, this implies that the maximum rate of such interactive codes approaches 1 as є goes to ‍0, as is also the case for the maximum rate of classical error correcting codes. Over the past decade, followup works have strengthened and generalized this result to other noisy channels, stressing on how fast the rate approaches 1 as є goes to 0, but retaining the assumption that the noiseless protocol is alternating.
In this paper we consider the general case, where the noiseless protocols can have arbitrary orders of speaking. In contrast to Kol-Raz and to the followup results in this model, we show that the maximum rate of interactive codes that encode general protocols is upper bounded by a universal constant strictly smaller than 1. To put it differently, we show that there is an inherent blowup in communication when protocols with arbitrary orders of speaking are faced with any constant fraction of errors ‍є > 0. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS ‍2014].

Publisher's Version
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah ORCID logo, Venkatesan Guruswami ORCID logo, Pravesh K. Kothari ORCID logo, and Peter Manohar ORCID logo
(University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA)
A code C ∶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b ∈ {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength.
In this paper, we prove a near-cubic lower bound of n ≥ Ω(k3/log6(k)) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k. Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

Publisher's Version
Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel
Meghal Gupta ORCID logo and Rachel Yun Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
Given a noiseless protocol π0 computing a function f(x, y) of Alice and Bob’s private inputs x, y, the goal of interactive coding is to construct an error-resilient protocol π computing f such that even if some fraction of the communication is adversarially corrupted, both parties still learn f(x, y). Ideally, the resulting scheme π should be positive rate, computationally efficient, and achieve optimal error resilience.
While interactive coding over large alphabets is well understood, the situation over the binary alphabet has remained evasive. At the present moment, the known schemes over the binary alphabet that achieve a higher error resilience than a trivial adaptation of large alphabet schemes are either still suboptimally error resilient, or optimally error resilient with exponential communication complexity. In this work, we construct a scheme achieving optimality in all three parameters: our protocol is positive rate, computationally efficient, and resilient to the optimal 1/6 − є adversarial errors.
Our protocol employs a new type of code that we call a layered code, which may be of independent interest. Like a tree code, a layered code allows the coder to encode a message in an online fashion, but is defined on a graph instead of a tree.

Publisher's Version
A High Dimensional Goldreich-Levin Theorem
Parker Newton ORCID logo, Silas Richelson ORCID logo, and Chase Wilson ORCID logo
(University of California at Riverside, Riverside, USA; University of California at San Diego, San Diego, USA)
In this work we prove a high dimensional analogue of the beloved Goldreich-Levin Theorem (STOC 1989). We consider the following algorithmic problem: given oracle access to a function f:ℤqm→ℤqn such that Prx∼ℤqm[f(x)=Ax]≥ε for some A∈ℤqn× m and ε>0, recover A (or a list of all such matrices). We focus on the case ε≤ 1/q since when ε ≥ 1/q+δ, the problem is solved by the original Goldreich-Levin Theorem. As stated, this problem cannot be efficiently solved, since when ε ≤ 1/q the list of A with good agreement with f might be exponentially large. Our main theorem gives an algorithm which efficiently recovers a list of affine maps of size (1/ε ) which have good agreement with f, and such that every linear map which has good agreement with f, also has good agreement with some affine map in our list. Our proof makes novel use of Fourier analysis. Our main theorem has applications to effective property testing.

Publisher's Version
Binary Error-Correcting Codes with Minimal Noiseless Feedback
Meghal GuptaORCID logo, Venkatesan Guruswami ORCID logo, and Rachel Yun Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
In the setting of error-correcting codes with feedback, Alice wishes to communicate a k-bit message x to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if ≈ 1/3 of Alice’s bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding 1/4.
The original feedback setting assumes that after transmitting each bit, Alice knows (via feedback) what bit Bob received. In this work, our focus in on the limited feedback model, where Bob is only allowed to send a few bits at a small number of pre-designated points in the protocol. For any desired є > 0, we construct a coding scheme that tolerates a fraction 1/3−є of bit flips relying only on Oє(logk) bits of feedback from Bob sent in a fixed Oє(1) number of rounds. We complement this with a matching lower bound showing that Ω(logk) bits of feedback are necessary to recover from an error fraction exceeding 1/4 (the threshold without any feedback), and for schemes resilient to a fraction 1/3−є of bit flips, the number of rounds must grow as є → 0.
We also study (and resolve) the question for the simpler model of erasures. We show that Oє(logk) bits of feedback spread over Oє(1) rounds suffice to tolerate a fraction (1−є) of erasures. Likewise, our Ω(logk) lower bound applies for erasure fractions exceeding 1/2, and an increasing number of rounds are required as the erasure fraction approaches 1.

Publisher's Version
Generic Reed-Solomon Codes Achieve List-Decoding Capacity
Joshua Brakensiek ORCID logo, Sivakanth Gopi ORCID logo, and Visu Makam ORCID logo
(Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands)
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-ℓ MDS code, denoted by MDS(ℓ), has the property that any ℓ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent.
We also show that generic Reed-Solomon codes are MDS(ℓ) for all ℓ, relying crucially on the GM-MDS theorem which shows that generator matrices of generic Reed-Solomon codes achieve any possible zero pattern. As a corollary, this implies that generic Reed-Solomon codes achieve list decoding capacity. More concretely, we show that, with high probability, a random Reed-Solomon code of rate R over an exponentially large field is list decodable from radius 1−R−є with list size at most (1−R−є)/є, resolving a conjecture of Shangguan and Tamo.

Publisher's Version
Optimal Bounds for Noisy Sorting
Yuzhou Gu ORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that (1± o(1)) nlog2 n comparisons are both necessary and sufficient to sort a list of n elements. In this paper, we study the Noisy Sorting problem, where each comparison result is flipped independently with probability p for some fixed p∈ (0, 1/2). As our main result, we show that (1± o(1)) ( 1/I(p) + 1/(1−2p) log2 (1−p/p) ) nlog2 n noisy comparisons are both necessary and sufficient to sort n elements with error probability o(1) using noisy comparisons, where I(p)=1 + plog2 p+(1−p)log2 (1−p) is capacity of BSC channel with crossover probability p. This simultaneously improves the previous best lower and upper bounds (Wang, Ghaddar and Wang, ISIT 2022) for this problem.
For the related Noisy Binary Search problem, we show that (1± o(1)) ((1−δ)log2(n)/I(p) + 2 log2 (1/δ)/(1−2p)log2(1−p/p)) noisy comparisons are both necessary and sufficient to find the predecessor of an element among n sorted elements with error probability δ. This extends the previous bounds of (Burnashev and Zigangirov, 1974), which are only tight for δ = 1/no(1).

Publisher's Version
Lattice Problems beyond Polynomial Time
Divesh Aggarwal ORCID logo, Huck Bennett ORCID logo, Zvika Brakerski ORCID logo, Alexander Golovnev ORCID logo, Rajendra Kumar ORCID logo, Zeyong Li ORCID logo, Spencer Peters ORCID logo, Noah Stephens-Davidowitz ORCID logo, and Vinod Vaikuntanathan ORCID logo
(National University of Singapore, Singapore; Oregon State University, USA; Weizmann Institute of Science, Israel; Georgetown University, USA; Cornell University, USA; Massachusetts Institute of Technology, USA)
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time. Specifically, we revisit four foundational results in this context—two protocols and two worst-case to average-case reductions. We show how to improve the approximation factor in each result by a factor of roughly √n/logn when running the protocol or reduction in 2є n time instead of polynomial time, and we show a novel protocol with no polynomial-time analog. Our results are as follows.
(1) We show a worst-case to average-case reduction proving that secret-key cryptography (specifically, collision-resistant hash functions) exists if the (decision version of the) Shortest Vector Problem (SVP) cannot be approximated to within a factor of Õ(√n) in 2є n time. This extends to our setting Ajtai’s celebrated polynomial-time reduction for the Short Integer Solutions (SIS) problem (1996),which showed (after improvements by Micciancio and Regev (2004, 2007)) that secret-key cryptography exists if SVP cannot be approximated to within a factor of Õ(n) in polynomial time.
(2) We show another worst-case to average-case reduction proving that public-key cryptography exists if SVP cannot be approximated to within a factor of Õ(n) in 2є n time. This extends Regev’s celebrated polynomial-time reduction for the Learning with Errors (LWE) problem (2005, 2009), which achieved an approximation factor of Õ(n1.5). In fact, Regev’s reduction is quantum, but we prove our result under a classical reduction, generalizing Peikert’s polynomial-time classical reduction (2009), which achieved an approximation factor of Õ(n2).
(3) We show that the (decision version of the) Closest Vector Problem (CVP) with a constant approximation factor has a coAM protocol with a 2є n-time verifier. We prove this via a (very simple) generalization of the celebrated polynomial-time protocol due to Goldreich and Goldwasser (1998, 2000). It follows that the recent series of 2є n-time and even 2(1−є)n-time hardness results for CVP cannot be extended to large constant approximation factors γ unless AMETH is false. We also rule out 2(1−є)n-time lower bounds for any constant approximation factor γ > √2, under plausible complexity-theoretic assumptions. (These results also extend to arbitrary norms, with different constants.)
(4) We show that O(√logn)-approximate SVP has a coNTIME protocol with a 2є n-time verifier. Here, the analogous (also celebrated!) polynomial-time result is due to Aharonov and Regev (2005), who showed a polynomial-time protocol achieving an approximation factor of √n (for both SVP and CVP, while we only achieve this result for CVP). This result implies similar barriers to hardness, with a larger approximation factor under a weaker complexity-theoretic conjectures (as does the next result).
(5) Finally, we give a novel coMA protocol for constant-factor-approximate CVP with a 2є n-time verifier. Unlike our other results, this protocol has no known analog in the polynomial-time regime.
All of the results described above are special cases of more general theorems that achieve time-approximation factor tradeoffs. In particular, the tradeoffs for the first four results smoothly interpolate from the polynomial-time results in prior work to our new results in the exponential-time world.

Publisher's Version

Session 9B

The Round Complexity of Statistical MPC with Optimal Resiliency
Benny Applebaum ORCID logo, Eliran Kachlon ORCID logo, and Arpita Patra ORCID logo
(Tel Aviv University, Israel; IISc Bangalore, India)
In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model.
Our main result shows that every functionality can be realized in only four rounds of interaction which is known to be optimal. This completely settles the round complexity of statistical actively-secure optimally-resilient MPC, resolving a long line of research.
Along the way, we construct the first round-optimal statistically-secure verifiable secret sharing protocol (Chor, Goldwasser, Micali, and Awerbuch; STOC 1985), show that every single-input functionality (e.g., multi-verifier zero-knowledge) can be realized in 3 rounds, and prove that the latter bound is optimal. The complexity of all our protocols is exponential in the number of parties, and the question of deriving polynomially-efficient protocols is left for future research.
Our main technical contribution is a construction of a new type of statistically-secure signature scheme whose existence was open even for smaller resiliency thresholds. We also describe a new statistical compiler that lifts up passively-secure protocols to actively-secure protocols in a round-efficient way via the aid of protocols for single-input functionalities. This compiler can be viewed as a statistical variant of the GMW compiler (Goldreich, Micali, Wigderson; STOC, 1987) that originally employed zero-knowledge proofs and public-key encryption.

Publisher's Version
Constant-Round Arguments from One-Way Functions
Noga Amit ORCID logo and Guy N. RothblumORCID logo
(Weizmann Institute of Science, Israel; Apple, USA)
We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of P, such as depth-bounded computations. Kilian’s celebrated work [STOC 1992] provides such 4-message arguments for P (actually, for NP) using collision-resistant hash functions. We show that one-way functions suffice for obtaining constant-round arguments of almost-linear verification time for languages in P that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian’s) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time. Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear verification complexity are not known even for NC (indeed, even for AC1).

Publisher's Version
Boosting Batch Arguments and RAM Delegation
Yael KalaiORCID logo, Alex LombardiORCID logo, Vinod VaikuntanathanORCID logo, and Daniel WichsORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA; Northeastern University, USA; NTT Research, USA)
We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument (BARG) systems. In particular, we show (under a mild additional assumption) how to convert a BARG that generates proofs of length poly (mk1−є, where m is the length of a single instance and k is the number of instances being batched, into one that generates proofs of length poly (m, logk), which is the gold standard for succinctness of BARGs. By prior work, such BARGs imply the existence of SNARGs for deterministic time T computation with succinctness poly(logT).
Our result reduces the long-standing challenge of building publicly-verifiable delegation schemes to a much easier problem: building a batch argument system that beats the trivial construction. It also immediately implies new constructions of BARGs and SNARGs with polylogarithmic succinctness based on either bilinear maps or a combination of the DDH and QR assumptions.
Along the way, we prove an equivalence between BARGs and a new notion of SNARGs for (deterministic) RAM computations that we call “flexible RAM SNARGs with partial input soundness.” This is the first demonstration that SNARGs for deterministic computation (of any kind) imply BARGs. Our RAM SNARG notion is of independent interest and has already been used in a recent work on constructing rate-1 BARGs (Devadas et. ‍al. FOCS 2022).

Publisher's Version
Succinct Computational Secret Sharing
Benny Applebaum ORCID logo, Amos Beimel ORCID logo, Yuval Ishai ORCID logo, Eyal Kushilevitz ORCID logo, Tianren Liu ORCID logo, and Vinod VaikuntanathanORCID logo
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel; Technion, Israel; Peking University, China; Massachusetts Institute of Technology, USA)
A secret-sharing scheme enables a dealer to share a secret s among n parties such that only authorized subsets of parties, specified by a monotone access structure f:{0,1}n→{0,1}, can reconstruct s from their shares. Other subsets of parties learn nothing about s.
The question of minimizing the (largest) share size for a given f has been the subject of a large body of work. However, in most existing constructions for general access structures f, the share size is not much smaller than the size of some natural computational representation of the access structure f, a fact that has often been referred to as the “representation size barrier” in secret sharing.
In this work, we initiate a systematic study of succinct computational secret sharing (SCSS), where the secrecy requirement is computational and the goal is to substantially beat the representation size barrier. We obtain the following main results.
First, we introduce the notion of a projective PRG, a pseudorandom generator for which any subset of the output bits can be revealed while keeping the other output bits hidden, using a short projective seed. We construct projective PRGs with different levels of succinctness under a variety of computational assumptions, and apply them towards constructing SCSS for graph access structures, monotone CNF formulas, and (less succinctly) useful subclasses of monotone circuits and branching programs. Most notably, under the sub-exponential RSA assumption, we obtain a SCSS scheme that, given an arbitrary access structure f, represented by a truth table of size N=2n, produces shares of size polylog(N)=poly(n) in time Õ(N). For comparison, the share size of the best known information-theoretic schemes is O(N0.58).
Secondly, under the (minimal) assumption that one-way functions exist, we obtain a near-quadratic separation between the total share size of computational and information-theoretic secret sharing. This is the strongest separation one can hope for, given the state of the art in secret sharing lower bounds. We also construct SCSS schemes from one-way functions for useful classes of access structures, including forbidden graphs and monotone DNF formulas. This leads to constructions of fully-decomposable conditional disclosure of secrets (also known as privacy-free garbled circuits) for general functions, represented by a truth table of size N=2n, with share size polylog(N) and computation time Õ(N), assuming sub-exponentially secure one-way functions.

Publisher's Version
Obfuscation of Pseudo-Deterministic Quantum Circuits
James Bartusek ORCID logo, Fuyuki Kitagawa ORCID logo, Ryo Nishimaki ORCID logo, and Takashi Yamakawa ORCID logo
(University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan)
We show how to obfuscate pseudo-deterministic quantum circuits, assuming the quantum hardness of learning with errors (QLWE) and post-quantum virtual black-box (VBB) obfuscation for classical circuits. Given the classical description of a quantum circuit Q, our obfuscator outputs a quantum state Q that can be used to evaluate Q repeatedly on arbitrary inputs.
Instantiating the VBB obfuscator for classical circuits with any candidate post-quantum indistinguishability obfuscator gives us the first candidate construction of indistinguishability obfuscation for all polynomial-size pseudo-deterministic quantum circuits. In particular, our scheme is the first candidate obfuscator for a class of circuits that is powerful enough to implement Shor’s algorithm (SICOMP 1997).
Our approach follows Bartusek and Malavolta (ITCS 2022), who obfuscate null quantum circuits by obfuscating the verifier of an appropriate classical verification of quantum computation (CVQC) scheme. We go beyond null circuits by constructing a publicly-verifiable CVQC scheme for quantum partitioning circuits, which can be used to verify the evaluation procedure of Mahadev’s quantum fully-homomorphic encryption scheme (FOCS 2018). We achieve this by upgrading the one-time secure scheme of Bartusek (TCC 2021) to a fully reusable scheme, via a publicly-decodable Pauli functional commitment, which we formally define and construct in this work. This commitment scheme, which satisfies a notion of binding against committers that can access the receiver’s standard and Hadamard basis decoding functionalities, is constructed by building on techniques of Amos, Georgiou, Kiayias, and Zhandry (STOC 2020) introduced in the context of equivocal but collision-resistant hash functions.

Publisher's Version
Commitments to Quantum States
Sam Gunn ORCID logo, Nathan Ju ORCID logo, Fermi Ma ORCID logo, and Mark Zhandry ORCID logo
(University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA)
What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions.
Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.

Publisher's Version
Quantum Cryptography in Algorithmica
William Kretschmer ORCID logo, Luowen Qian ORCID logo, Makrand Sinha ORCID logo, and Avishay Tal ORCID logo
(University of Texas at Austin, USA; Boston University, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
We construct a classical oracle relative to which P = NP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo’s five worlds, this is a construction of pseudorandom states in ”Algorithmica,” and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of P vs. NP in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states.
We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which P = NP but BQPQCMA, based on hardness of the OR ∘ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against AC0 circuits. This variant may be of independent interest.

Publisher's Version
Quantum Free Games
Anand Natarajan ORCID logo and Tina Zhang ORCID logo
(Massachusetts Institute of Technology, USA)
The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC’14). In the quantum world, there are two complexity classes that can be considered quantum analogues of classical free games: (1) AM*, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. (1) We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker (2010) and also shows, conditional on ETH, that the algorithm of Brandão, Christandl and Yard (STOC’11) for optimizing over separable states is tight up to logarithmic factors. (2) We show that AM* with nprovers = 2, question length O(1), and answer-length log(n) is equal to RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. (In contrast, Aaronson, Impagliazzo and Moshkovitz show that classical free games are much weaker than general classical games.) We show this using a question “hyper-compression” theorem that iteratively applies the introspection technique of Ji et al. (2020). Our result is a significant improvement over the headline result of Ji et al., whose MIP* protocol for the halting problem has (n)-sized questions and answers. (3) By the same techniques, we obtain a zero-gap AM* protocol for a Π2 complete language with constant-size questions and almost logarithmically (O(logn · log* n)) large answers, improving on the headline result of Mousavi, Nezhadi and Yuen (STOC’22). (4) Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires Ω(logn) bits of communication. It follows that our results in item 3 are optimal up to an O(log* n) factor, and that the gapless compression theorems of Mousavi, Nezhadi and Yuen are asymptotically optimal. We conjecture that these bounds can be saturated in the gapped case as well.

Publisher's Version
Quantum Advantage from Any Non-local Game
Yael KalaiORCID logo, Alex LombardiORCID logo, Vinod VaikuntanathanORCID logo, and Lisa Yang ORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
We show a general method of compiling any k-prover non-local game into a single-prover (computationally sound) interactive game maintaining the same quantum completeness and classical soundness guarantees, up to a negligible additive factor in a security parameter. Our compiler uses any quantum homomorphic encryption scheme (Mahadev, FOCS 2018; Brakerski, CRYPTO 2018) satisfying a natural form of correctness with respect to auxiliary quantum input. The homomorphic encryption scheme is used as a cryptographic mechanism to simulate the effect of spatial separation, and is required to evaluate k−1 prover strategies out of k on encrypted queries.
In conjunction with the rich literature on (entangled) multi-prover non-local games starting from the celebrated CHSH game (Clauser, Horne, Shimony and Holt, Physical Review Letters 1969), our compiler gives a broad and rich framework for constructing protocols that classically verify quantum advantage.

Publisher's Version
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Fernando Granha Jeronimo ORCID logo and Pei Wu ORCID logo
(Institute for Advanced Study, Princeton, USA)
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.
In this work, we study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote QMA+(2). In this setting, we are able to design proof verification protocols for (increasingly) hard problems both using logarithmic size quantum proofs and having a constant probability gap in distinguishing yes from no instances. In particular, we design global protocols for small set expansion (SSE), unique games (UG), and PCP verification. As a consequence, we obtain NP ⊆ QMAlog+(2) with a constant gap. By virtue of the new constant gap, we are able to “scale up” this result to QMA+(2), obtaining the full characterization QMA+(2)=NEXP by establishing stronger explicitness properties of the for . We believe that our protocols are interesting examples of proof verification and property testing in their own right. Moreover, each of our protocols has a single isolated property testing task relying on non-negative amplitudes which if generalized would allow transferring our results to QMA(2).
One key novelty of these protocols is the manipulation of quantum proofs in a global and coherent way yielding constant gaps. Previous protocols (only available for general amplitudes) are either local having vanishingly small gaps or treating the quantum proofs as classical probability distributions requiring polynomially many proofs. In both cases, these known protocols do not imply non-trivial bounds on QMA(2).

Publisher's Version

Session 9C

Testing Distributional Assumptions of Learning Algorithms
Ronitt Rubinfeld ORCID logo and Arsen Vasilyan ORCID logo
(Massachusetts Institute of Technology, USA)
There are many important high dimensional function classes that have fast agnostic learning algorithms when strong assumptions on the distribution of examples can be made, such as Gaussianity or uniformity over the domain. But how can one be sufficiently confident that the data indeed satisfies the distributional assumption, so that one can trust in the output quality of the agnostic learning algorithm? We propose a model by which to systematically study the design of tester-learner pairs (A,T), such that if the distribution on examples in the data passes the tester T then one can safely trust the output of the agnostic learner A on the data.
To demonstrate the power of the model, we apply it to the classical problem of agnostically learning halfspaces under the standard Gaussian distribution and present a tester-learner pair with a combined run-time of nÕ(1/є4). This qualitatively matches that of the best known ordinary agnostic learning algorithms for this task. In contrast, finite sample Gaussian distribution testers do not exist for the L1 and EMD distance measures. Previously it was known that half-spaces are well-approximated with low-degree polynomials relative to the Gaussian distribution. A key step in our analysis is showing that this is the case even relative to distributions whose low-degree moments approximately match those of a Gaussian.
We also go beyond spherically-symmetric distributions, and give a tester-learner pair for halfspaces under the uniform distribution on {0,1}n with combined run-time of nÕ(1/є4). This is achieved using polynomial approximation theory and critical index machinery of [Diakonikolas, Gopalan, Jaiswal, Servedio, and Viola 2009].
Can one design agnostic learning algorithms under distributional assumptions and count on future technical work to produce, as a matter of course, tester-learner pairs with similar run-time? Our answer is a resounding no, as we show there exist some well-studied settings for which 2Õ(√n) run-time agnostic learning algorithms are available, yet the combined run-times of tester-learner pairs must be as high as 2Ω(n). On that account, the design of tester-learner pairs is a research direction in its own right independent of standard agnostic learning. To be specific, our lower bounds apply to the problems of agnostically learning convex sets under the Gaussian distribution and for monotone Boolean functions under the uniform distribution over {0,1}n.

Publisher's Version Info
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota ORCID logo, Adam R. Klivans ORCID logo, and Pravesh K. Kothari ORCID logo
(University of Texas at Austin, USA; Carnegie Mellon University, USA)
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of testable learning, where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians.
In this paper we give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric distances in probability. We obtain efficient testable learners for any concept class that admits low-degree sandwiching polynomials, capturing most important examples for which we have ordinary agnostic learners. We recover the results of Rubinfeld and Vasilyan as a corollary of our techniques while achieving improved, near-optimal sample complexity bounds for a broad range of concept classes and distributions.
Surprisingly, we show that the information-theoretic sample complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class, one of the most well-studied measures in statistical learning theory. In particular, uniform convergence is necessary and sufficient for testable learning. This leads to a fundamental separation from (ordinary) distribution-specific agnostic learning, where uniform convergence is sufficient but not necessary.

Publisher's Version
Learning Polynomial Transformations via Generalized Tensor Decompositions
Sitan Chen ORCID logo, Jerry Li ORCID logo, Yuanzhi Li ORCID logo, and Anru R. Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Carnegie Mellon University, USA; Duke University, USA)
We consider the problem of learning high dimensional polynomial transformations of Gaussians. Given samples of the form f(x), where xN(0,Ir) is hidden and f: ℝr → ℝd is a function where every output coordinate is a low-degree polynomial, the goal is to learn the distribution over f(x). One can think of this as a simple model for learning deep generative models, namely pushforwards of Gaussians under two-layer neural networks with polynomial activations, though the learning problem is mathematically natural in its own right.
Our first main result is a polynomial-time algorithm for learning quadratic transformations of Gaussians in a smoothed setting. Our second main result is a polynomial-time algorithm for learning constant-degree polynomial transformations of Gaussian in a smoothed setting, when the rank of the associated tensors is small. In fact our results extend to any rotation-invariant input distribution, not just Gaussian. These are the first end-to-end guarantees for learning a pushforward under a neural network with more than one layer.
While our work aims to take an initial step towards understanding why generative models perform so well in practice, the algorithmic problems that we solve along the way are also of independent interest. We give the first provably efficient algorithms for tensor ring decomposition, a popular non-commutative generalization of tensor decomposition that is used in practice to implicitly store large tensors, as well as for a new variant of matrix factorization where the factors arise from low-rank tensors.

Publisher's Version
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein ORCID logo
(University of California at Davis, Davis, USA)
Suppose we are given an n-dimensional order-3 symmetric tensor T ∈ (ℝn)⊗ 3 that is the sum of r random rank-1 terms. The problem of recovering the rank-1 components is possible in principle when rn2 but polynomial-time algorithms are only known in the regime rn3/2. Similar “statistical-computational gaps” occur in many high-dimensional inference tasks, and in recent years there has been a flurry of work on explaining the apparent computational hardness in these problems by proving lower bounds against restricted (yet powerful) models of computation such as statistical queries (SQ), sum-of-squares (SoS), and low-degree polynomials (LDP). However, no such prior work exists for tensor decomposition, largely because its hardness does not appear to be explained by a “planted versus null” testing problem.
We consider a model for random order-3 tensor decomposition where one component is slightly larger in norm than the rest (to break symmetry), and the components are drawn uniformly from the hypercube. We resolve the computational complexity in the LDP model: O(logn)-degree polynomial functions of the tensor entries can accurately estimate the largest component when rn3/2 but fail to do so when rn3/2. This provides rigorous evidence suggesting that the best known algorithms for tensor decomposition cannot be improved, at least by known approaches. A natural extension of the result holds for tensors of any fixed order k ≥ 3, in which case the LDP threshold is rnk/2.

Publisher's Version
What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
Yeshwanth Cherapanamjeri ORCID logo, Constantinos Daskalakis ORCID logo, Andrew IlyasORCID logo, and Manolis Zampetakis ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
In the classical setting of self-selection, the goal is to learn k models simultaneously, from observations (x(i), y(i)) where y(i) is the output of one of k underlying models on input x(i). In contrast to mixture models, where we observe the output of a randomly selected model (and therefore the selection of which model is observed is exogenous), in self-selection models the observed model depends on the realized outputs of the underlying models themselves, as determined by some known selection criterion (e.g., we might observe the highest output, the smallest output, or the median output of the k models), and is thus endogenous. In known-index self-selection, the identity of the observed model output is observable; in unknown-index self-selection, it is not. Self-selection has a long history in Econometrics (going back to the works of Roy, Gronau, Lewis, Heckman, and others) and many applications in various theoretical and applied fields, including treatment effect estimation, imitation learning, learning from strategically reported data, and learning from markets at disequilibrium.
In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear. In the known-index case, we require poly(1/ε, k, d) sample and time complexity to estimate all model parameters to accuracy ε in d dimensions, and can accommodate quite general selection criteria. In the more challenging unknown-index case, even the identifiability of the linear models (from infinitely many samples) was not known. We show three results in this case for the commonly studied max self-selection criterion: (1) we show that the linear models are indeed identifiable, (2) for general k we provide an algorithm with poly(d)· exp(poly(k)) sample and time complexity to estimate the regression parameters up to error 1/poly(k), and (3) for k = 2 we provide an algorithm for any error ε and poly(d, 1/ε) sample and time complexity.

Publisher's Version
A Characterization of List Learnability
Moses Charikar ORCID logo and Chirag Pabbaraju ORCID logo
(Stanford University, USA)
A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz.
In this work we consider list PAC learning where the goal is to output a list of k predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to k-list learn a hypothesis class?
We completely characterize k-list learnability in terms of a generalization of DS dimension that we call the k-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is k-list learnable if and only if the k-DS dimension is finite.

Publisher's Version
A Unifying Theory of Distance from Calibration
Jarosław Błasiok ORCID logo, Parikshit Gopalan ORCID logo, Lunjia Hu ORCID logo, and Preetum Nakkiran ORCID logo
(Columbia University, USA; Apple, USA; Stanford University, USA)
We study the fundamental question of how to define and measure the distance from calibration for probabilistic predictors. While the notion of perfect calibration is well-understood, there is no consensus on how to quantify the distance from perfect calibration. Numerous calibration measures have been proposed in the literature, but it is unclear how they compare to each other, and many popular measures such as Expected Calibration Error (ECE) fail to satisfy basic properties like continuity.
We present a rigorous framework for analyzing calibration measures, inspired by the literature on property testing. We propose a ground-truth notion of distance from calibration: the ℓ1 distance to the nearest perfectly calibrated predictor. We define a consistent calibration measure as one that is polynomially related to this distance. Applying our framework, we identify three calibration measures that are consistent and can be estimated efficiently: smooth calibration, interval calibration, and Laplace kernel calibration. The former two give quadratic approximations to the ground truth distance, which we show is information-theoretically optimal in a natural model for measuring calibration which we term the prediction-only access model. Our work thus establishes fundamental lower and upper bounds on measuring the distance to calibration, and also provides theoretical justification for preferring certain metrics (like Laplace kernel calibration) in practice.

Publisher's Version
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
Ilias Diakonikolas ORCID logo, Christos Tzamos ORCID logo, and Daniel M. Kane ORCID logo
(University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA)
The Forster transform is a method of regularizing a dataset by placing it in radial isotropic position while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given weakly polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first strongly polynomial time algorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm for distribution-free PAC learning of halfspaces. This learning result is surprising because proper PAC learning of halfspaces is equivalent to linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.

Publisher's Version
Lifting Uniform Learners via Distributional Decomposition
Guy Blanc ORCID logo, Jane Lange ORCID logo, Ali Malik ORCID logo, and Li-Yang Tan ORCID logo
(Stanford University, USA; Massachusetts Institute of Technology, USA)
We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution ‍D. The efficiency of our transformation scales with the inherent complexity of ‍D, running in (n, (md)d) time for distributions over n whose pmfs are computed by depth-d decision trees, where m is the sample complexity of the original algorithm. For monotone distributions our transformation uses only samples from ‍D, and for general ones it uses subcube conditioning samples.
A key technical ingredient is an algorithm which, given the aforementioned access to D, produces an optimal decision tree decomposition of D: an approximation of D as a mixture of uniform distributions over disjoint subcubes. With this decomposition in hand, we run the uniform-distribution learner on each subcube and combine the hypotheses using the decision tree. This algorithmic decomposition lemma also yields new algorithms for learning decision tree distributions with runtimes that exponentially improve on the prior state of the art—results of independent interest in distribution learning.

Publisher's Version Info
Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis
André Lieutier ORCID logo and Mathijs Wintraecken ORCID logo
(No affiliation, France; Université Côte d’Azur, France; Inria, France; IST Austria, Austria)
In this paper we introduce a pruning of the medial axis called the (λ,α)-medial axis (axλα). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if K and K′ are close in the Hausdorff (dH) sense then the (λ,α)-medial axes of K and K′ are close as metric spaces, that is the Gromov-Hausdorff distance (dGH) between the two is 1/4-Hölder in the sense that dGH (axλα(K),axλα(K′)) ≲ dH(K,K′)1/4. The Hausdorff distance between the two medial axes is also bounded, by dH (axλα(K),λα(K′)) ≲ dH(K,K′)1/2. These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis.

Publisher's Version

Session 10A

Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari ORCID logo and Christoph Grunau ORCID logo
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)
We present an Õ(log2 n) round deterministic distributed algorithm for the maximal independent set problem. By known reductions, this round complexity extends also to maximal matching, Δ+1 vertex coloring, and 2Δ−1 edge coloring. These four problems are among the most central problems in distributed graph algorithms and have been studied extensively for the past four decades. This improved round complexity comes closer to the Ω(logn) lower bound of maximal independent set and maximal matching [Balliu et al. FOCS ’19]. The previous best known deterministic complexity for all of these problems was Θ(log3 n). Via the shattering technique, the improvement permeates also to the corresponding randomized complexities, e.g., the new randomized complexity of Δ+1 vertex coloring is now Õ(log2logn) rounds.
Our approach is a novel combination of the previously known (and seemingly orthogonal) two methods for developing fast deterministic algorithms for these problems, namely global derandomization via network decomposition (see e.g., [Rozhon, Ghaffari STOC’20; Ghaffari, Grunau, Rozhon SODA’21; Ghaffari et al. SODA’23]) and local rounding of fractional solutions (see e.g., [Fischer DISC’17; Harris FOCS’19; Fischer, Ghaffari, Kuhn FOCS’17; Ghaffari, Kuhn FOCS’21; Faour et al. SODA’23]). We consider a relaxation of the classic network decomposition concept, where instead of requiring the clusters in the same block to be non-adjacent, we allow each node to have a small number of neighboring clusters. We also show a deterministic algorithm that computes this relaxed decomposition faster than standard decompositions. We then use this relaxed decomposition to significantly improve the integrality of certain fractional solutions, before handing them to the local rounding procedure that now has to do fewer rounding steps.

Publisher's Version
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang ORCID logo and Sagnik Mukhopadhyay ORCID logo
(MPI-INF, Germany; Saarland University, Germany; University of Sheffield, UK)
We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer κ, our algorithm can, with high probability, either find κ vertices whose removal disconnects the network or return that such κ vertices do not exist. Our algorithm takes κ3· Õ(D+√n) rounds, where n is the number of vertices in the network and D denotes the network’s diameter. This implies Õ(D+√n) round complexity whenever κ=polylog(n).
Prior to our result, a bound of Õ(D) is known only when κ=1,2 [Parter, Petruschka DISC’22]. For κ≥ 3, this bound can be obtained only by an O(logn)-approximation algorithm [Censor-Hillel, Ghaffari, Kuhn PODC’14], and the only known exact algorithm takes O((κΔ D)O(κ)) rounds, where Δ is the maximum degree [Parter DISC’19]. Our result answers an open problem by Nanongkai, Saranurak, and Yingchareonthawornchai [STOC’19].

Publisher's Version
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff ORCID logo and Taisuke Yasuda ORCID logo
(Carnegie Mellon University, USA)
Subset selection for the rank k approximation of an n× d matrix A offers improvements in the interpretability of matrices, as well as a variety of computational savings. This problem is well-understood when the error measure is the Frobenius norm, with various tight algorithms known even in challenging models such as the online model, where an algorithm must select the column subset irrevocably when the columns arrive one by one. In sharp contrast, when the error measure is replaced by other matrix losses, optimal trade-offs between the subset size and approximation quality have not been settled, even in the standard offline setting. We give a number of results towards closing these gaps.
In the offline setting, we achieve nearly optimal bicriteria algorithms in two settings. First, we remove a √k factor from a prior result of Song–Woodruff–Zhong when the loss function is any entrywise loss with an approximate triangle inequality and at least linear growth, which includes, e.g., the Huber loss. Our result is tight when applied to the ℓ1 loss. We give a similar improvement for the entrywise ℓp loss for p>2, improving a previous distortion of Õ(k1−1/p) to O(k1/2−1/p). We show this is tight for p = ∞, while for 2<p<∞, we give the first bicriteria algorithms for (1+ε)-approximate entrywise ℓp low rank approximation. Our results come from a general technique which improves distortions by replacing the use of a well-conditioned basis with a slightly larger spanning set for which any vector can be expressed as a linear combination with small Euclidean norm. This idea may be of independent interest and we show, for example, that it also gives the first oblivious ℓp subspace embeddings for 1≤ p < 2 with Õ(d1/p) distortion, which is nearly optimal and improves the previously best known Õ(d) and closes a long line of work.
In the online setting, we give the first online subset selection algorithm for ℓp subspace approximation and entrywise ℓp low rank approximation by showing how to implement the classical sensitivity sampling algorithm online, which is challenging due to the sequential nature of sensitivity sampling. Our main technique is an online algorithm for detecting when an approximately optimal subspace changes substantially. We also give new related results for the online setting, including online coresets for Euclidean (k,p) clustering as well as an online active regression algorithm making Θ(dp/2p−1) queries, answering open questions of Musco–Musco–Woodruff–Yasuda and Chen–Li–Sun.

Publisher's Version
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
Nikhil Bansal ORCID logo, Haotian Jiang ORCID logo, and Raghu Meka ORCID logo
(University of Michigan, Ann Arbor, USA; Microsoft Research, USA; University of California at Los Angeles, Los Angeles, USA)
We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric d × d matrices A1,…,An each with ||Ai||op ≤ 1 and rank at most n/log3 n, one can efficiently find ± 1 signs x1,…,xn such that their signed sum has spectral norm ||∑i=1n xi Ai||op = O(√n). This result also implies a logn − Ω( loglogn) qubit lower bound for quantum random access codes encoding n classical bits with advantage ≫ 1/√n.
Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2021] for random matrices with correlated Gaussian entries.

Publisher's Version

Session 10B

A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
Vera Traub ORCID logo and Rico Zenklusen ORCID logo
(University of Bonn, Germany; ETH Zurich, Switzerland)
Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural 2-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation factors below 2 can be achieved. One of the most basic examples thereof is the Weighted Connectivity Augmentation Problem (WCAP). In WCAP, one is given an undirected graph together with a set of additional weighted candidate edges, and the task is to find a cheapest set of candidate edges whose addition to the graph increases its edge-connectivity. We present a (1.5+ε)-approximation algorithm for WCAP, showing for the first time that factors below 2 are achievable.
On a high level, we design a well-chosen local search algorithm, inspired by recent advances for Weighted Tree Augmentation. To measure progress, we consider a directed weakening of WCAP and show that it has highly structured planar solutions. Interpreting a solution of the original problem as one of this directed weakening allows us to describe local exchange steps in a clean and algorithmically amenable way. Leveraging these insights, we show that we can efficiently search for good exchange steps within a component class of link sets that is closely related to bounded treewidth subgraphs of circle graphs. Moreover, we prove that an optimum solution can be decomposed into smaller components, at least one of which leads to a good local search step as long as we did not yet achieve the claimed approximation guarantee.

Publisher's Version
Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
Lap Chi Lau ORCID logo, Kam Chuen Tung ORCID logo, and Robert Wang ORCID logo
(University of Waterloo, Canada)
We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs. The goal is to develop a new spectral theory for directed graphs and an alternative spectral theory for hypergraphs.
The first main result is a Cheeger inequality relating the vertex expansion of a directed graph to the vertex-capacitated maximum reweighted second eigenvalue. This provides a combinatorial characterization of the fastest mixing time of a directed graph by vertex expansion, and builds a new connection between reweighted eigenvalued, vertex expansion, and fastest mixing time for directed graphs.
The second main result is a stronger Cheeger inequality relating the edge conductance of a directed graph to the edge-capacitated maximum reweighted second eigenvalue. This provides a certificate for a directed graph to be an expander and a spectral algorithm to find a sparse cut in a directed graph, playing a similar role as Cheeger's inequality in certifying graph expansion and in the spectral partitioning algorithm for undirected graphs.
We also use this reweighted eigenvalue approach to derive the improved Cheeger inequality for directed graphs, and furthermore to derive several Cheeger inequalities for hypergraphs that match and improve the existing results. These are supporting results that this provides a unifying approach to lift the spectral theory for undirected graphs to more general settings.

Publisher's Version
An Improved Approximation Guarantee for Prize-Collecting TSP
Jannis Blauth ORCID logo and Martin Nägele ORCID logo
(University of Bonn, Germany)
We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may choose to not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of 1.774 with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of 1.915. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours.

Publisher's Version
Better Trees for Santa Claus
Étienne Bamas ORCID logo and Lars Rohwedder ORCID logo
(EPFL, Switzerland; Maastricht University, Netherlands)
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC’09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem we are given a directed graph with sources and sinks and our goal is to find vertex disjoint arborescences rooted in the sources such that at each non-sink vertex of an arborescence the out-degree is at least k, where k is to be maximized. This problem is of particular interest, since it appears to capture much of the difficulty of the Santa Claus problem: (1) like in the Santa Claus problem the configuration LP has a large integrality gap in this case and (2) previous progress by Bateni et al. was quickly generalized to the Santa Claus problem (Chakrabarty et al. [FOCS’09]). These results remain the state-of-the-art both for the Santa Claus problem and for max-min degree arborescence and they yield a polylogarithmic approximation in quasi-polynomial time. We present an exponential improvement to this, a poly(loglogn)-approximation in quasi-polynomial time for the max-min degree arborescence problem. To the best of our knowledge, this is the first example of breaking the logarithmic barrier for a special case of the Santa Claus problem, where the configuration LP cannot be utilized. The main technical novelty of our result are locally good solutions: informally, we show that it suffices to find a poly(logn)-approximation that locally has stronger guarantees. We use a lift-and-project type of LP and randomized rounding, which were also used by Bateni et al., but unlike previous work we integrate careful pruning steps in the rounding. In the proof we extensively apply Lovász Local Lemma and a local search technique, both of which were previously used only in the context of the configuration LP.

Publisher's Version

Session 10C

Interior Point Methods with a Gradient Oracle
Adrian Vladu ORCID logo
(CNRS, France; IRIF, France; Université Paris Cité, France)
We provide an interior point method based on quasi-Newton iterations, which only requires first-order access to a strongly self-concordant barrier function. To achieve this, we extend the techniques of Dunagan-Harvey [STOC ’07] to maintain a preconditioner, while using only first-order information. We measure the quality of this preconditioner in terms of its relative excentricity to the unknown Hessian matrix, and we generalize these techniques to convex functions with a slowly-changing Hessian. We combine this with an interior point method to show that, given first-order access to an appropriate barrier function for a convex set K, we can solve well-conditioned linear optimization problems over K to ε precision in time O((T+n2)√nνlog(1/ε)), where ν is the self-concordance parameter of the barrier function, and T is the time required to make a gradient query.
As a consequence we show that:
Linear optimization over n-dimensional convex sets can be solved in time O((Tn+n3)log(1/ε)). This parallels the running time achieved by state of the art algorithms for cutting plane methods, when replacing separation oracles with first-order oracles for an appropriate barrier function. We can solve semidefinite programs involving mn matrices in ℝn× n in time O(mn4+m1.25n3.5log(1/ε)), improving over the state of the art algorithms, in the case where m=Ω(n3.5/ω−1.25).
Along the way we develop a host of tools allowing us to control the evolution of our potential functions, using techniques from matrix analysis and Schur convexity.

Publisher's Version
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ ORCID logo and Mihalis Yannakakis ORCID logo
(Columbia University, USA)
We show subexponential lower bounds (i.e., 2Ω (nc)) on the smoothed complexity of the classical Howard’s Policy Iteration algorithm for Markov Decision Processes. The bounds hold for the total reward and the average reward criteria. The constructions are robust in the sense that the subexponential bound holds not only on the average for independent random perturbations of the MDP parameters (transition probabilities and rewards), but for all arbitrary perturbations within an inverse polynomial range. We show also an exponential lower bound on the worst-case complexity for the simple reachability objective.

Publisher's Version
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts ORCID logo, Yin Tat Lee ORCID logo, and Xinzhi Zhang ORCID logo
(Columbia University, USA; Microsoft Research, USA; University of Washington, USA)
The simplex method for linear programming is known to be highly efficient in practice, and understanding its performance from a theoretical perspective is an active research topic. The framework of smoothed analysis, first introduced by Spielman and Teng (JACM ’04) for this purpose, defines the smoothed complexity of solving a linear program with d variables and n constraints as the expected running time when Gaussian noise of variance σ2 is added to the LP data. We prove that the smoothed complexity of the simplex method is O−3/2 d13/4log7/4 n), improving the dependence on 1/σ compared to the previous bound of O−2 d2√logn). We accomplish this through a new analysis of the shadow bound, key to earlier analyses as well. Illustrating the power of our new method, we use our method to prove a nearly tight upper bound on the smoothed complexity of two-dimensional polygons.

Publisher's Version
Algorithms Approaching the Threshold for Semi-random Planted Clique
Rares-Darius Buhai ORCID logo, Pravesh K. Kothari ORCID logo, and David Steurer ORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n1/2 — the information-theoretic threshold in the semi-random model and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt.
To generate a graph in the semi-random planted-clique model, we first 1) plant a clique of size k in an n-vertex –graph with edge probability 1/2 and then adversarially add or delete an arbitrary number edges not touching the planted clique and delete any subset of edges going out of the planted clique. For every є>0, we give an nO(1/є)-time algorithm that recovers a clique of size k in this model whenever kn1/2+є. In fact, our algorithm computes, with high probability, a list of about n/k cliques of size k that contains the planted clique. Our algorithms also extend to arbitrary edge probabilities p and improve on the previous best guarantee whenever p ≤ 1−n−0.001.
Our algorithms rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite –random graphs into algorithms for semi-random planted clique. Analogous to the (conjecturally) optimal algorithms for the fully-random model, the previous best guarantees for semi-random planted clique correspond to spectral relaxations of biclique numbers based on eigenvalues of adjacency matrices. We construct an SDP lower bound that shows that the n2/3 threshold in prior works is an inherent limitation of these spectral relaxations. We go beyond this limitation by using higher-order sum-of-squares relaxations for biclique numbers.
We also provide some evidence that the information-computation trade-off of our current algorithms may be inherent by proving an average-case lower bound for unbalanced bicliques in the low-degree polynomial model.

Publisher's Version

proc time: 39.96