FOCS 2024 Accepted Papers with Abstracts
Please see below a searchable list of the accepted papers with titles, abstracts and author names:
O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
===========================================================================================
Abstract
——–
The random walk $d$-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk $d$-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every $d\ge 3$ hashes, let $c_d^*$ be the sharp threshold for the load factor at which a valid assignment of $cm$ objects to a hash table of size $m$ likely exists. We show that for any $d\ge 4$ hashes and load factor $c<c_d^*$, the expectation of the random walk insertion time is $O(1)$, that is, a constant depending only on $d$ and $c$ but not $m$.
Authors
——-
Topics
——
* algorithms and data structures
* randomized algorithms
A stronger bound for linear 3-LCC
=================================================
Abstract
——–
A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the cases that $C$ is linear.
In a breakthrough result Kothari and Manohar (STOC 2024) showed that for linear 3-LCC $n = 2^{\Omega(k^{1/8})}$. In this work we prove that $n = 2^{\Omega(k^{1/4})}$. As Reed-Muller codes yield 3-LCC with $n = 2^{O(k^{1/2})}$, this brings us closer to closing the gap. Moreover, in the special case of design-LCC (into which Reed-Muller fall) the bound we get is $n = 2^{\Omega(k^{1/3})}$.
Author
——
Topics
——
* algorithmic coding theory
* computational complexity
Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
========================================================================================
Abstract
——–
Gabidulin codes constitute an important class of maximum rank distance (MRD) codes, which may be viewed as the rank-metric counterpart of Reed–Solomon codes. However, unlike the fruitful positive results about the list decoding of Reed–Solomon codes, results concerning the list decodability of Gabidulin codes are all negative so far. For example, Raviv and Wachter-Zeh (IEEE TIT, 2016 and 2017) constructed a class of Gabidulin codes with poor combinatorial list decodability. Even the problem of proving the existence of Gabidulin codes with good combinatorial list decodability remained a long-standing open problem.
In this paper, we resolve the aforementioned open problem by showing that, with high probability, random Gabidulin codes over sufficiently large alphabets attain the optimal generalized Singleton bound for list decoding in the rank metric. In particular, they achieve the list decoding capacity in the rank metric.
Our work is significantly influenced by the recent breakthroughs in the combinatorial list decodability of Reed–Solomon codes, especially the work by Brakensiek, Gopi, and Makam (STOC 2023). Our major technical contributions, which may hold independent interest, consist of the following: (1) A novel unified theory of “higher order MRD codes,” which runs parallel to the theory of “higher order MDS codes” developed by Brakensiek, Gopi, and Makam. (2) A natural analog of the GM-MDS theorem, proven by Lovett (FOCS 2018) and Yildiz and Hassibi (IEEE TIT 2019), which we call the GM-MRD theorem.
Authors
——-
Topics
——
* algorithmic coding theory
* combinatorics
Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
=============================================================================================
Abstract
——–
For every $n >0$, we show the existence of a CNF tautology over $O(n^2)$ variables of width $O(\log n)$ such that it has a Polynomial Calculus Resolution refutation over $\{0,1\}$ variables of size $O(n^3\polylog(n))$ but any Polynomial Calculus refutation over $\{+1,-1\}$ variables requires size $2^{\Omega(n)}$. This shows that Polynomial Calculus sizes over the $\{0,1\}$ and $\{+1,-1\}$ bases are incomparable (since Tseitin tautologies show a separation in the other direction) and answers an open problem posed by Sokolov \cite{sok20} and Razborov \cite{razbopen}
Author
——
Topic
—–
* computational complexity
Capacity Threshold for the Ising Perceptron
===========================================================
Abstract
——–
We show that the capacity of the Ising perceptron is with high probability upper bounded by the constant $\alpha_\star \approx 0.833$ conjectured by Krauth and Mézard, under the condition that an explicit two-variable function $\mathscr{S}_\star(\lambda_1,\lambda_2)$ is maximized at $(1,0)$. The earlier work of Ding and Sun proves the matching lower bound subject to a similar numerical condition, and together these results give a conditional proof of the conjecture of Krauth and Mézard.
Author
——
Topics
——
* combinatorial optimization
* combinatorics
Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
================================================================================================
Abstract
——–
In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem — the generalisation of the well-known excluded grid theorem to directed graphs — confirming a conjecture by Reed, Johnson, Robertson, Seymour, and Thomas (1996) from the mid-nineties.
The theorem states the existence of a function $f$ such that every digraph of directed tree-width $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor, but the given function grows non-elementarily with the size of the grid minor.
More precisely, it contains a tower whose height depends on the size of the grid.
In this paper we present an alternative proof of the directed grid theorem which is conceptually much simpler, more modular in its composition and also improves the upper bound for the function \(f\) a power tower of height 22.
Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy (2016), who proved a polynomial bound for the excluded grid theorem for undirected graphs.
We translate a key concept of their proof to directed graphs by introducing \emph{cycles of well-linked sets (CWS)}, and show that any digraph of high directed tree-width contains a large CWS, which in turn contains a large cylindrical grid, improving the result due to Kawarabayashi and Kreutzer from an non-elementary to an elementary function.
An immediate application of our result is that we can improve the bound for Younger’s conjecture—the directed Erd\H{o}s-Pósa property—proved by Reed, Robertson, Seymour and Thomas 1996 from a non-elementary to an elementary function.
The same improvement applies to other types of Erd\H{o}s-Pósa style problems on directed graphs.
To the best of our knowledge this is the first significant improvement on the bound for Younger’s conjecture since it was proved in 1996.
Since its publication in STOC 2015, the Directed Grid Theorem has found numerous applications (see for example Campos, Lopes, Maia, and Sau (2019), Giannopoulou, Kawarabayashi, Kreutzer and Kwon (2020), Jacob, Wlodarczyk and Zehavi (2023), Giannopoulou, Kreutzer and Wiederrecht (2024), and Hatzel, Rabinovich and Wiederrecht (2019), all of which directly benefit from our main result.
Finally, we believe that the theoretical tools developed in this work may find applications beyond the directed grid theorem, in a similar way as the path-of-sets-system framework due to Chekuri and Chuzhoy 2016 did for undirected graphs (see for example Hatzel, Komosa, Pilipczuk and Sorge (2022), Chekuri and Chuzhoy (2015) and Chuzhoy and Nimavat (2019)).
Authors
——-
1. Marcelo Garlet Milani <
[email protected]> (National Institute of Informatics, Tokyo, Japan)
4. Meike Hatzel <
[email protected]> (National Institute of Informatics, Tokyo, Japan)
Topics
——
* algorithmic graph theory
* combinatorics
On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
=============================================================================================
Abstract
——–
We study connections between the problem of fully dynamic $(1-\epsilon)$-approximate maximum bipartite matching, and the dual $(1+\epsilon)$-approximate vertex cover problem, with the online matrix-vector ($\mathsf{OMv}$) conjecture which has recently been used in several fine-grained hardness reductions. We prove that there is an \emph{online} algorithm that maintains a $(1+\epsilon)$-approximate vertex cover in amortized $n^{1-c}\epsilon^{-C}$ time for constants $c, C > 0$ for fully dynamic updates \emph{if and only if} the $\mathsf{OMv}$ conjecture is false. Similarly, we prove that there is an online algorithm that maintains a $(1-\epsilon)$-approximate maximum matching in amortized $n^{1-c}\epsilon^{-C}$ time if and only if there is a nontrivial algorithm for another dynamic problem, which we call dynamic approximate $\mathsf{OMv}$, that has seemingly no matching structure. This provides some evidence against achieving amortized sublinear update times for approximate fully dynamic matching and vertex cover.
Leveraging these connections, we obtain faster \emph{algorithms} for approximate fully dynamic matching in both the online and offline settings.
1. We give a randomized algorithm that with high probability maintains a $(1-\epsilon)$-approximate bipartite matching and $(1+\epsilon)$-approximate vertex cover in fully dynamic graphs, in amortized $O(\epsilon^{-O(1)} \frac{n}{2^{\Omega(\sqrt{\log n})}})$ update time. This improves over the previous fastest runtimes of $O(n/(\log^* n)^{\Omega(1)})$ due to Assadi-Behnezhad-Khanna-Li [STOC 2023], and $O_{\epsilon}(n^{1-\Omega_{\epsilon}(1)})$ due to Bhattacharya-Kiss-Saranurak [FOCS 2023] for small $\epsilon$. Our algorithm leverages fast algorithms for $\mathsf{OMv}$ due to Larsen and Williams [SODA 2017].
2. We give a randomized offline algorithm for $(1-\epsilon)$-approximate maximum matching with amortized runtime $O(n^{.58}\epsilon^{-O(1)})$ by using fast matrix multiplication, significantly improving over the runtimes achieved via online algorithms mentioned above. This mirrors the situation with $\mathsf{OMv}$, where an offline algorithm exactly corresponds to fast matrix multiplication. We also give an offline algorithm that maintains a $(1+\epsilon)$-approximate vertex cover in amortized $O(n^{.723}\epsilon^{-O(1)})$ time.
Author
——
Topics
——
* algorithmic graph theory
* algorithms and data structures
Online Combinatorial Allocations and Auctions with Few Samples
==============================================================================
Abstract
——–
In online combinatorial allocations/auctions, $n$ bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over subsets of $m$ indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total \emph{welfare}, defined as the sum of bidder valuations.
A long line of work has studied this problem when the bidder valuations come from known distributions. In particular, for submodular/XOS valuations, we know $2$-competitive algorithms/mechanisms that set a fixed price for each item and the arriving bidders take their favorite subset of the remaining items given these prices. However, these algorithms traditionally presume the availability of the underlying distributions as part of the input to the algorithm.
Contrary to this assumption, practical scenarios often require the learning of distributions, a task complicated by limited sample availability. This paper investigates the feasibility of achieving $O(1)$-competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions.
Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an $O(1)$-competitive algorithm for submodular/XOS valuations. This result leverages a novel extension of the secretary-style analysis, employing the sample to have the algorithm compete against itself. Although online, this first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield a $(2+\epsilon)$-competitive online truthful mechanism for submodular/XOS valuations and any constant $\epsilon>0$. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.
Authors
——-
Topics
——
* algorithmic game theory
* online algorithms
Efficient approximate unitary designs from random Pauli rotations
=================================================================================
Abstract
——–
We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order $t$. Specifically, a step of the walk on the unitary or orthognoal group of dimension $2^{\mathsf n}$ is a random Pauli rotation $e^{\mathrm i \theta P /2}$. The spectral gap of this random walk is shown to be $\Omega(1/t)$, which coincides with the best previously known bound for a random walk on the permutation group on $\{0,1\}^{\mathsf n}$. This implies that the walk gives an $\varepsilon$-approximate unitary $t$-design in depth $\mathcal O(\mathsf n t^2 + t \log 1/\varepsilon)d$ where $d=\mathcal{O}(\log \mathsf n)$ is the circuit depth to implement $e^{\mathrm i \theta P /2}$. Our simple proof uses quadratic Casimir operators of Lie algebras.
Authors
——-
Topics
——
* pseudorandomness and derandomization
* quantum computing
* spectral methods
Verifying Groups in Linear Time
===============================================
Abstract
——–
Consider the following problem: Given an $n \times n$ multiplication table, decide whether it is a Cayley multiplication table of a group.
Among deterministic algorithms for this problem, the best known algorithm is implied by F.\ W.\ Light’s associativity test (1949) and has running time of $O(n^2 \log n)$. Allowing randomization, the best known algorithm has running time of $O(n^2 \log (1/\delta))$, where $\delta>0$ is the error probability of the algorithm (Rajagopalan and Schulman, FOCS 1996, SICOMP 2000).
In this work, we improve upon both of the above known algorithms. Specifically, we present a deterministic algorithm for the above problem whose running time is $O(n^2)$. This performance is optimal up to constants.
A central tool we develop is an efficient algorithm for finding a subset $A$ of a group $G$ satisfying $A^2=G$ while $|A| = O(\sqrt{|G|})$.
Authors
——-
Topics
——
* algorithms and data structures
* computational complexity
Fast list decoding of univariate multiplicity and folded Reed-Solomon codes
===========================================================================================
Abstract
——–
We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in $\tilde{O}(n)$ time.
Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every $\epsilon >0$, and rate $r \in (0,1)$, there exist explicit families of these codes that have rate $r$ and can be list decoded from a $(1-r-\epsilon)$ fraction of errors with constant list size in polynomial time (Guruswami \& Wang (\emph{IEEE Trans.\ Inform.\ Theory} 2013) and Kopparty, Ron-Zewi, Saraf \& Wootters (\emph{SIAM J. Comput.} 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in $\tilde{O}(n)$, where $n$ is the block-length of the code.
Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (\emph{IEEE Trans. Inf. Theory} 2005), who designed a $\tilde{O}(n)$ time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design $\tilde{O}(n)$ time algorithms for two natural algebraic problems: given a $(m+2)$-variate polynomial $Q(x,y_0,\dots,y_m) = \tilde{Q}(x) + \sum_{i = 0}^m Q_i(x)\cdot y_i$ the first algorithm solves order-$m$ linear differential equations of the form $Q\left(x, f(x), \frac{df}{dx}, \dots,\frac{d^m f}{dx^m}\right) \equiv 0$ while the second solves functional equations of the form $Q\left(x, f(x), f(\gamma x), \dots,f(\gamma^m x)\right) \equiv 0$, where $m$ is an arbitrary constant and $\gamma$ is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical $\tilde{O}(n)$ time algorithms of Sieveking (\emph{Computing} 1972) and Kung (\emph{Numer.\ Math.} 1974) for computing the modular inverse of a power series, and might be of independent interest.
Authors
——-
Topics
——
* algebraic computation
* algorithmic coding theory
* algorithms and data structures
First-Order Model Checking on Monadically Stable Graph Classes
==============================================================================
Abstract
——–
A graph class $\cal C$ is called \emph{monadically stable} if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from $\cal C$. We prove that the model checking problem for first-order logic is fixed-parameter tractable on every monadically stable graph class. This extends the results of [Grohe, Kreutzer, and Siebertz; J. ACM ’17] for nowhere dense classes and of [Dreier, Mählmann, and Siebertz; STOC ’23] for structurally nowhere dense classes to all monadically stable classes.
This result is complemented by a hardness result showing that monadic stability is precisely the dividing line between tractability and intractability of first-order model checking on hereditary classes that are \emph{edge-stable}: exclude some half-graph as a semi-induced subgraph. Precisely, we prove that for every hereditary graph class $\cal C$ that is edge-stable but not monadically stable, first-order model checking is $\mathrm{AW}[*]$-hard on $\cal C$, and $\mathrm{W}[1]$-hard when restricted to existential sentences. This confirms, in the special case of edge-stable classes, an on-going conjecture that the notion of \emph{monadic dependence} delimits the tractability of first-order model checking on hereditary classes of graphs.
For our tractability result, we first prove that monadically stable graph classes have almost linear neighborhood complexity, by combining tools from stability theory and from sparsity theory.
We then use this result to construct sparse neighborhood covers for monadically stable graph classes, which provides the missing ingredient for the algorithm of [Dreier, Mählmann, and Siebertz; STOC 2023]. The key component of this construction is the usage of orders with low crossing number [Welzl; SoCG ’88], a tool from the area of range queries.
For our hardness result, we first prove a new characterization of monadically stable graph classes in terms of forbidden induced subgraphs. We then use this characterization to show that in hereditary classes that are edge-stable but not monadically stable, one can efficiently interpret the class of all graphs using only existential formulas.
Authors
——-
Topics
——
* combinatorics
* parametrized algorithms
Proofs of Space with Maximal Hardness
=====================================================
Abstract
——–
In a proof of space, a prover performs a complex computation with a large output. A verifier periodically checks that the prover still holds the output. The security goal for a proof of space construction is to ensure that a prover who erases even a portion of the output has to redo a large portion of the complex computation in order to satisfy the verifier.
In existing constructions of proofs of space, the computation that a cheating prover is forced to redo is a small fraction (vanishing or small constant) of the original complex computation. The only exception is a construction of Pietrzak (ITCS 2019) that requires extremely depth-robust graphs, which result in impractically high complexity of the initialization process.
We present the first proof of space of reasonable complexity that ensures that the prover has to redo almost the entire computation (fraction arbitrarily close to 1) when trying to save even an arbitrarily small constant fraction of the space.
Technically, our construction can be viewed as amplifying predecessor-robust graphs. These are directed acyclic graphs in which every subgraph of sufficient relative size $\pi$ contains a large single-sink connected component of relative size $\alpha_\pi$. We take a predecessor-robust graph with constant parameters $(\pi, \alpha_\pi)$, and build a bigger predecessor-robust graph with a near-optimal set of parameters and additional guarantees on sink placement, while increasing the degree only by a small additive constant.
Author
——
Topic
—–
* cryptography
A Dense Model Theorem for the Boolean Slice
===========================================================
Abstract
——–
The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $\eps>0$ and $f$ be a function on the middle slice on the Boolean cube, such that when choosing a uniformly random quadruple $(x,y,z ,x\oplus y\oplus z)$ of vectors of $2n$ bits with exactly $n$ ones, the probability that $f(x\oplus y \oplus z) = f(x) \oplus f(y) \oplus f(z)$ is at least $1/2+\eps$. The linearity testing problem, posed by~\cite{DBLP:journals/siamcomp/DavidDGKS17}, asks whether there must be an actual linear function that agrees with $f$ on $1/2+\eps’$ fraction of the inputs,
where $\eps’ = \eps'(\eps)>0$.
We solve this problem, showing that $f$ must indeed be correlated with a linear function. To do so, we prove a dense model theorem for the
middle slice of the Boolean hypercube
for Gowers uniformity norms. Specifically,
we show that for every $k\in\mathbb{N}$,
the normalized indicator function of the middle slice of the Boolean hypercube
$\{0,1\}^{2n}$ is close in Gowers norm to
the normalized indicator function of
the union of all slices with weight
$t = n\pmod{2^{k-1}}$. Using our techniques we also give a more general `low degree test’ and a biased
rank theorem for the slice.
Authors
——-
Topics
——
* analysis of Boolean functions
* computational complexity
* sublinear algorithms
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More
via Duality
================================================================================================
Abstract
——–
We give the first almost-linear total time algorithm for deciding if a flow of cost at most $F$ still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, or cost increases.
This implies almost-linear time algorithms for approximating the minimum-cost flow value and $s$-$t$ distance on such \emph{decremental} graphs.
Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically.
These algorithms also improve over the current best known runtimes for \emph{statically} computing minimum-cost flow, in both the randomized and deterministic settings.
We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms.
More precisely, our algorithm computes the flow via a sequence of $m^{1+o(1)}$ dynamic \emph{min-ratio cut} problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized $m^{o(1)}$ time by maintaining a \emph{tree-cut sparsifier}. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [Goranci-Räcke-Saranurak-Tan, SODA 2021] that also works in \emph{capacitated} graphs. All our algorithms are deterministc, though they can be sped up further using randomized techniques while still working against an adaptive adversary.
Authors
——-
Topic
—–
* algorithms and data structures
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the
$\sqrt{n}$ Dimension Threshold
================================================================================================
Abstract
——–
We consider the task of certifying that a random $d$-dimensional subspace $X$ in $\R^n$ is well-spread – every vector $x \in X$ satisfies $c\sqrt{n} \|x\|_2 \leq \|x\|_1 \leq \sqrt{n}\|x\|_2$. In a seminal work, Barak et. al. showed a polynomial-time certification algorithm when $d \leq O(\sqrt{n})$. On the other hand, when $d \gg \sqrt{n}$, the certification task is information-theoretically possible but there is evidence that it is computationally hard, a phenomenon known as the information-computation gap.
In this paper, we give subexponential-time certification algorithms in the $d \gg \sqrt{n}$ regime. Our algorithm runs in time $\exp(\tilde{O}(n^{\epsilon}))$ when $d \leq \tilde{O}(n^{\frac{1+\epsilon}{2}})$, establishing a smooth trade-off between runtime and the dimension.
Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task.
Authors
——-
Topics
——
* average-case algorithms and complexity
* spectral methods
Power Series Composition in Near-Linear Time
=============================================================
Abstract
——–
We present an algebraic algorithm that computes the composition of two power series in $\tilde{\mathrm{O}}(n)$ time complexity.
The previous best algorithms are $\mathrm{O}(n^{1+o(1)})$ by Kedlaya and Umans (FOCS 2008) and an $\mathrm{O}(n^{1.43})$ algebraic algorithm by Neiger, Salvy, Schost and Villard (JACM 2023).
Our algorithm builds upon the recent Graeffe iteration approach to manipulate rational power series introduced by Bostan and Mori (SOSA 2021).
Authors
——-
Topic
—–
* algebraic computation
The ESPRIT algorithm under high noise: Optimal error scaling and noisy
super-resolution
================================================================================================
Abstract
——–
Subspace-based signal processing techniques, such as the Estimation of Signal Parameters via Rotational Invariant Techniques (ESPRIT) algorithm, are popular methods for spectral estimation.
These algorithms can achieve the so-called super-resolution scaling under low noise conditions, surpassing the well-known Nyquist limit. However, the performance of these algorithms under high-noise conditions is not as well understood. Existing state-of-the-art analysis indicates that ESPRIT and related algorithms can be resilient even for signals where each observation is corrupted by statistically independent, mean-zero noise of size $\mathcal{O}(1)$, but these analyses only show that the error $\epsilon$ decays at a slow rate $\epsilon=\mathcal{\tilde{O}}(n^{-1/2})$ with respect to the cutoff frequency $n$. In this work, we prove that under certain assumptions of bias and high noise, the ESPRIT algorithm can attain a significantly improved error scaling $\epsilon = \mathcal{\tilde{O}}(n^{-3/2})$, exhibiting noisy super-resolution scaling beyond the Nyquist limit. We further establish a theoretical lower bound and show that this scaling is optimal. Our analysis introduces novel matrix perturbation results, which could be of independent interest.
Authors
——-
Topics
——
* approximation algorithms
* spectral methods
Obstructions to Erdős-Pósa Dualities for Minors
==================================================================
Abstract
——–
Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graph classes.
We say that the pair $(\mathcal{H},\mathcal{G})$ is an Erdős-Pósa pair (EP-pair) if there exists a function $f$ such that for every $k$ and every graph $G\in \mathcal{G},$ either $G$ has $k$ pairwise vertex-disjoint subgraphs which do not belong to $\mathcal{H},$ or there exists a set $S\subseteq V(G)$ of size at most $f(k)$ for which $G – S \in \mathcal{H}.$
The classic result of Erdős and Pósa says that if $\mathcal{F}$ is the class of forests, then $(\mathcal{F},\mathcal{G})$ is an EP-pair for all graph classes $\mathcal{G}.$
A minor-closed graph class $\mathcal{G}$ is an EP-counterexample for $\mathcal{H}$ if $\mathcal{G}$ is minimal with the property that $(\mathcal{H},\mathcal{G})$ is not an EP-pair.
In this paper, we prove that for every minor-closed graph class $\mathcal{H}$ the set $\mathfrak{C}_{\mathcal{H}}$ of all EP-counterexamples for $\mathcal{H}$ is finite.
In particular, we provide a complete characterization of $\mathfrak{C}_{\mathcal{H}}$ for every $\mathcal{H}$ and give a constructive upper bound on its size.
We show that each class $\mathcal{G}$ in $\mathfrak{C}_{\mathcal{H}}$ can be described as the set of all minors of some, suitably defined, sequence of grid-like graphs $\langle \mathscr{W}_{k} \rangle_{k\in \mathbb{N}}.$
Moreover, each $\mathscr{W}_{k}$ admits a half-integral packing, i.e., $k$ copies of some $H \not\in \mathcal{H}$ where no vertex is used more than twice.
This implies a complete delineation of the half-integrality threshold of the Erdős-Pósa property for minors and as a corollary, we obtain a constructive proof of Thomas’ conjecture on the half-integral Erdős-Pósa property for minors which was recently confirmed by Liu.
Our results are algorithmic.
Let $h=h(\mathcal{H})$ denote the maximum size of an obstruction to $\mathcal{H}$.
For every minor-closed graph class $\mathcal{H},$ there exists a constructive algorithm that, given a graph $G$ and an integer $k,$ either outputs a half-integral packing of $k$ copies of some $H \not\in \mathcal{H}$ or outputs a set of at most ${2^{k^{\mathcal{O}_h(1)}}}$ vertices whose deletion creates a graph in $\mathcal{H}$ in time $2^{2^{{k^{\mathcal{O}_h(1)}}}}|G|^4\log |G|.$
Moreover, as a consequence of our results, for every minor-closed class $\mathcal{H},$ we obtain min-max-dualities, which may be seen as analogues of the celebrated Grid Theorem of Robertson and Seymour, for the recently introduced parameters $\mathcal{H}$-treewidth and elimination distance to $\mathcal{H}$.
Authors
——-
3. Dimitrios M. Thilikos <
[email protected]> (LIRMM, Univ. Montpellier, CNRS, France)
South Korea)
Topics
——
* algorithmic graph theory
* combinatorics
Optimal Bounds for Open Addressing Without Reordering
======================================================================
Abstract
——–
In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper \emph{“Uniform Hashing is Optimal”}.
Authors
——-
Topics
——
* algorithms and data structures
* online algorithms
* randomized algorithms
Tight Analyses of Ordered and Unordered Linear Probing
=======================================================================
Abstract
——–
Linear-probing hash tables have been classically believed to support insertions in time $\Theta(x^2)$, where $1 – 1/x$ is the load factor of the hash table. Recent work by Bender, Kuszmaul, and Kuszmaul (FOCS’21), however, has added a new twist to this story: in some versions of linear probing, if the \emph{maximum} load factor is at most $1 – 1/x$, then the \emph{amortized} expected time per insertion will never exceed $x \polylog x$ (even in workloads that operate continuously at a load factor of $1 – 1/x$). Determining the exact asymptotic value for the amortized insertion time remains open.
In this paper, we settle the amortized complexity with matching upper and lower bounds of $\Theta(x \log^{1.5} x)$. Along the way, we also obtain tight bounds for the so-called path surplus problem, a problem in combinatorial geometry that has been shown to be closely related to linear probing. We also show how to extend Bender et al.’s bounds to say something not just about \emph{ordered} linear probing (the version they study) but also about classical linear probing, in the form that is most widely implemented in practice.
Authors
——-
Topics
——
* algorithms and data structures
* combinatorics
* randomized algorithms
Tight Bounds for Classical Open Addressing
===========================================================
Abstract
——–
We introduce a classical open-addressed hash table, called \emph{rainbow hashing}, that supports a load factor of up to $1 – \epsilon$, while also supporting $O(1)$ expected-time queries, and $O(\log \log \epsilon^{-1})$ expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor $1 – \epsilon$ must incur $\Omega(\log \log \epsilon^{-1})$ expected time per operation.
Finally, we extend rainbow hashing to the setting where the hash table is \emph{dynamically resized} over time. Surprisingly, the addition of dynamic resizing does not come at any time cost—even while maintaining a load factor of $\ge 1 – \epsilon$ at all times, we can support $O(1)$ queries and $O(\log \log \epsilon^{-1})$ updates.
Prior to our work, achieving any time bounds of the form $o(\epsilon^{-1})$ for all of insertions, deletions, and queries simultaneously remained an open question.
Authors
——-
Topics
——
* algorithms and data structures
* online algorithms
* randomized algorithms
Deterministic Algorithm and Faster Algorithm for Submodular Maximization
subject to a Matroid Constraint
================================================================================================
Abstract
——–
We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a \textbf{deterministic} non-oblivious local search algorithm that has an approximation guarantee of $1 – 1/e – \varepsilon$ (for any $\varepsilon> 0$) and query complexity of $\tilde{O}_\varepsilon(nr)$, where $n$ is the size of the ground set and $r$ is the rank of the matroid. Our algorithm vastly improves over the previous state-of-the-art $0.5008$-approximation deterministic algorithm, and in fact, shows that there is no separation between the approximation guarantees that can be obtained by deterministic and randomized algorithms for the problem considered. The query complexity of our algorithm can be improved to $\tilde{O}_\varepsilon(n + r\sqrt{n})$ using randomization, which is nearly-linear for $r = O(\sqrt{n})$, and is always at least as good as the previous state-of-the-art algorithms.
Authors
——-
Topics
——
* algorithms and data structures
* approximation algorithms
* combinatorial optimization
* pseudorandomness and derandomization
* randomized algorithms
Communication Separations for Truthful Auctions: Breaking the Two-Player
Barrier
================================================================================================
Abstract
——–
We study the communication complexity of truthful combinatorial auctions, and in particular the case where valuations are either subadditive or single-minded, which we denote with $\mathsf{SubAdd} \cup \mathsf{SingleM}$. We show that for three bidders with valuations in $\mathsf{SubAdd} \cup \mathsf{SingleM}$, any deterministic truthful mechanism for $\mathsf{SubAdd} \cup \mathsf{SingleM}$ which achieves at least a $0.366$-approximation requires $\exp(m)$ communication. In contrast, a natural extension of [Feige09] yields a non-truthful $\mathrm{poly}(m)$-communication protocol that achieves a $\frac{1}{2}$-approximation, demonstrating a gap between the power of truthful mechanisms and non-truthful protocols for this problem.
Our approach follows the taxation complexity framework laid out in [Dobzinski16], but applies this framework in a setting not encompassed by the techniques used in past work. In particular, the only successful prior application of this framework uses a reduction to simultaneous protocols which only applies for \emph{two} bidders [AKSW20], whereas our three-player lower bounds are stronger than what can possibly arise from a two-player construction (since a trivial truthful auction guarantees a $\frac{1}{2}$-approximation for two players).
Authors
——-
Topics
——
* communication complexity
* economics and computation
High-Temperature Gibbs States are Unentangled and Efficiently Preparable
=========================================================================================
Abstract
——–
We show that thermal states of local Hamiltonians are separable above a constant temperature. Specifically, for a local Hamiltonian $H$ on a graph with degree $\mathfrak{d}$, its Gibbs state at inverse temperature $\beta$, denoted by $\rho =e^{-\beta H}/ \operatorname{tr}(e^{-\beta H})$, is a classical distribution over product states for all $\beta < 1/(c\mathfrak{d})$, where $c$ is a constant. This \emph{sudden death of thermal entanglement} upends conventional wisdom about the presence of short-range quantum correlations in Gibbs states.
Moreover, we show that we can efficiently sample from the distribution over product states.
In particular, for any $\beta < 1/(c \mathfrak{d}^3)$, we can prepare a state $\varepsilon$-close to $\rho$ in trace distance with a depth-one quantum circuit and $\operatorname{poly}(n) \log(1/\varepsilon)$ classical overhead.
Authors
——-
Topics
——
* Markov chains
* quantum computing
Structure learning of Hamiltonians from real-time evolution
============================================================================
Abstract
——–
We initiate the study of Hamiltonian structure learning from real-time evolution: given the ability to apply $e^{-iHt}$ for an unknown local Hamiltonian $H = \sum_{a = 1}^m \lambda_a E_a$ on $n$ qubits, the goal is to recover $H$. This problem is already well-studied under the assumption that the interaction terms, $E_a$, are given, and only the interaction strengths $\lambda_a$’s are unknown. But is it possible to learn a local Hamiltonian without prior knowledge of its interaction structure?
We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian to $\epsilon$ error with an evolution time scaling with $1/\epsilon$, and has the following appealing properties:
1. It does not need to know the Hamiltonian terms;
2. It works beyond the short-range setting, extending to any Hamiltonian $H$ where the sum of terms interacting with a qubit has bounded norm;
3. It evolves according to $H$ in constant time $t$ increments, thus achieving constant time resolution;
To our knowledge, no prior algorithm with Heisenberg-limited scaling existed with even one of these properties. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy $\epsilon$ with total evolution time beating the standard limit of $1/\epsilon^2$.
Authors
——-
Topic
—–
* quantum computing
Gaussian Approximation of Convex Sets by Intersections of Halfspaces
=====================================================================================
Abstract
——–
We study the approximability of general convex sets in $\R^n$ by intersections of halfspaces, where the approximation quality is measured with respect to the *standard Gaussian distribution* $N(0,I_n)$ and the complexity of an approximation is the number of halfspaces used.
While a large body of research has considered the approximation of convex sets by intersections of halfspaces under distance metrics such as the Lebesgue measure and Hausdorff distance, prior to our work there has not been a systematic study of convex approximation under the Gaussian distribution.
We establish a range of upper and lower bounds, both for general convex sets and for specific natural convex sets that are of particular interest.
Our results demonstrate that the landscape of approximation is intriguingly different under the Gaussian distribution versus previously studied distance measures.
Our results are proved using techniques from many different areas. These include classical results on convex polyhedral approximation, Cramér-type bounds on large deviations from probability theory, and—perhaps surprisingly—a range of topics from computational complexity, including computational learning theory, unconditional pseudorandomness, and the study of influences and noise sensitivity in the analysis of Boolean functions.
Authors
——-
Topics
——
* analysis of Boolean functions
* computational complexity
Constant Degree Direct Product Testers with Small Soundness
============================================================================
Abstract
——–
Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich and Safra~\cite{GoldreichSafra}
introduced the problem of direct product testing, which asks whether one can test if $F\colon X(k)\to \{0,1\}^k$ is correlated with a direct product function by querying $F$ on only $2$ inputs. Dinur and Kaufman~\cite{DinurK17} conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all $\delta>0$, there exists a family of high-dimensional expanders with degree $O_{\delta}(1)$ and a $2$-query direct product tester with soundness $\delta$.
We use the characterization given by~\cite{BafnaMinzer} and independently by~\cite{DiksteinD-agreement}, who showed that some form of non-Abelian coboundary expansion (which they called “Unique-Games coboundary expansion”) is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by~\cite{ChapmanL} satisfy the conditions of~\cite{BafnaMinzer}, thus admitting a 2-query direct product tester with small soundness.
Authors
——-
Topics
——
* combinatorics
* computational complexity
* pseudorandomness and derandomization
On Approximating Cutwidth and Pathwidth
========================================================
Abstract
——–
We study graph ordering problems with a min-max objective.
A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized.
We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS’88).
Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest.
We also use this to show other results, including an improved $ \log^{1+o(1)}(n)$ approximation for computing the pathwidth of a graph.
Improving the bounds for cutwidth and pathwidth were both long-standing questions in the area of graph partitioning.
Authors
——-
Topics
——
* algorithmic graph theory
* approximation algorithms
* combinatorial optimization
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
=============================================================================
Abstract
——–
This paper proves that Dijkstra’s shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure.
Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology. We give the first application of this notion to any sequential algorithm.
We design a new heap data structure with a working-set property guaranteeing that the heap takes advantage of locality in heap operations. Our heap matches the optimal (worst-case) bounds of Fibonacci heaps but also provides the beyond-worst-case guarantee that the cost of extracting the minimum element is merely logarithmic in the number of elements inserted after it instead of logarithmic in the number of all elements in the heap. This makes the extraction of recently added elements cheaper.
We prove that our working-set property is sufficient to guarantee universal optimality, specifically, for the problem of ordering vertices by their distance from the source vertex: The locality in the sequence of heap operations generated by any run of Dijkstra’s algorithm on a fixed topology is strong enough that one can couple the number of comparisons performed by any heap with our working-set property to the minimum number of comparisons required to solve the distance ordering problem on this topology.
Authors
——-
Topics
——
* algorithmic graph theory
* algorithms and data structures
Gapped Clique Homology is QMA1-hard and contained in QMA
=========================================================================
Abstract
——–
We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space X and an integer k, decide if X contains a k-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics [Wit82].
We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every k+1-clique in the graph to be a k-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is QMA1-hard and contained in QMA.
Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory [For94]. Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work [CK22].
Our result provides some suggestion that the quantum TDA algorithm [LGZ16] cannot be dequantized. More broadly, we hope that our results will open up new possibilities for quantum advantage in topological data analysis.
Authors
——-
Topics
——
* computational complexity
* quantum computing
Boosting uniformity in quasirandom groups: faster and simpler
==============================================================================
Abstract
——–
We study the communication complexity of multiplying $k\times t$
elements from the group $H=\text{SL(}2,q)$ in the number-on-forehead
model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$.
This is an exponential improvement over previous work, and matches
the state-of-the-art in the area.
Related, we show that the convolution of $k^{c}$ independent copies
of a 3-uniform distribution over $H^{m}$ is close to a $k$-uniform
distribution. This is again an exponential improvement over previous
work which needed $c^{k}$ copies.
The proofs are remarkably simple; the results extend to other quasirandom
groups.
We also show that for any group $H$, any distribution over $H^{m}$
whose weight-$k$ Fourier coefficients are small is close to a $k$-uniform
distribution. This generalizes previous work in the abelian setting;
and the proof is simpler.
Authors
——-
Topics
——
* analysis of Boolean functions
* combinatorics
* communication complexity
* pseudorandomness and derandomization
The sample complexity of smooth boosting and the tightness of the hardcore
theorem
================================================================================================
Abstract
——–
\emph{Smooth} boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, reproducibility, and quantum learning theory. In this work we study and settle the sample complexity of smooth boosting: we exhibit a class that can be weak learned to $\gamma$-advantage over smooth distributions with $m$ samples, for which strong learning over the uniform distribution requires $\tilde{\Omega}(1/\gamma^2)\cdot m$ samples. This essentially matches the overhead of existing smooth boosters and provides the first separation from the setting of distribution-independent boosting for which the corresponding overhead is $O(1/\gamma)$.
Our work also carries implications for Impagliazzo’s hardcore theorem from complexity theory, all known proofs of which can be cast in the framework of smooth boosting. For a function $f$ that is mildly hard against size-$s$ circuits, the hardcore theorem says that there is a set of inputs on which $f$ is extremely hard against size-$s’$ circuits. A downside of this important result is that $s’ \ll s$. We show that this size loss is necessary, and in fact, the parameters achieved by known proofs are the best possible.
Authors
——-
Topics
——
* computational complexity
* computational learning theory
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via
Rainbow Cycles
================================================================================================
Abstract
——–
We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a $3$-query locally correctable code (LCC) with dimension $\Theta(\log^2 n)$. Our result improves, for the binary field case, the $O_{\delta}(\log^8 n)$ bound obtained in the recent breakthrough of [KM23] (and the more recent improvement to $O_{\delta}(\log^4 n)$ for binary linear codes announced in [Yan24]).
Previous bounds for $3$-query linear LCCs proceed by constructing a $2$-query locally decodable code (LDC) from the $3$-query linear LCC/LDC and applying the strong bounds known for the former. Our approach is more direct and proceeds by bounding the covering radius of the dual code, borrowing inspiration from [IS20]. That is, we show that if $x \mapsto (v_1 \cdot x, v_2 \cdot x, \ldots, v_n \cdot x)$ is an arbitrary encoding map $\mathbb{F}_2^k \to \mathbb{F}_2^n$ for the $3$-query LCC, then all vectors in $\mathbb{F}_2^k$ can be written as a $\widetilde{O}_{\delta}(\log n)$-sparse linear combination of the $v_i$’s, which immediately implies $k \le \widetilde{O}_{\delta}((\log n)^2)$. The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least $\widetilde{\Omega}_{\delta}(\log n)$ of the $v_i$’s. We achieve this using the recent breakthrough result of [ABSZZ23] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.
Authors
——-
Topics
——
* algorithmic coding theory
* combinatorics
Reverse Mathematics of Complexity Lower Bounds
===============================================================
Abstract
——–
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are \emph{necessary} to prove a given theorem. In this work, we systematically explore the reverse mathematics of \emph{complexity lower bounds}. We explore \emph{reversals} in the setting of bounded arithmetic, with Cook’s theory $\mathsf{PV}_1$ as the base theory, and show that several natural lower bound statements about communication complexity, error correcting codes, and Turing machines are \emph{equivalent} to widely investigated combinatorial principles such as the weak pigeonhole principle for polynomial-time functions and its variants. As a consequence, complexity lower bounds can be formally seen as fundamental mathematical axioms with far-reaching implications.
The proof-theoretic equivalence between complexity lower bound statements and combinatorial principles yields several new implications for the (un)provability of lower bounds. Among other results, we derive the following consequences:
1. Under a plausible cryptographic assumption, the classical single-tape Turing machine $\Omega(n^2)$-time lower bound for Palindrome is unprovable in Jeřábek’s theory $\mathsf{APC}_1$. The conditional unprovability of this simple lower bound goes against the intuition shared by some researchers that most complexity lower bounds could be established
in $\mathsf{APC}_1$.
2. While $\mathsf{APC}_1$ proves one-way communication lower bounds for Set Disjointness, it does not prove one-way communication lower bounds for Equality, under a plausible cryptographic assumption.
3. An amplification phenomenon connected to the (un)provability of some lower bounds, under which a quantitatively weak $n^{1 + \varepsilon}$ lower bound is provable if and only if a stronger (and often tight) $n^c$ lower bound is provable.
4. Feasibly definable randomized algorithms can be feasibly defined deterministically ($\mathsf{APC}_1$ is $\forall\Sigma^b_1$-conservative over $\mathsf{PV}_1$) if and only if one-way communication complexity lower bound for Set Disjointness are provable in $\mathsf{PV}_1$.
Authors
——-
Topics
——
* circuit complexity
* computational complexity
Agnostically Learning Multi-index Models with Queries
======================================================================
Abstract
——–
We study the power of query access for the fundamental task of
agnostic learning under the Gaussian distribution.
In the agnostic model, no assumptions are
made on the labels of the examples and the goal is to compute a hypothesis
that is competitive with the {\em best-fit} function in a known class, i.e.,
it achieves error $\mathrm{opt}+\epsilon$, where $\mathrm{opt}$
is the error of the best function in the class.
We focus on a general family of Multi-Index Models (MIMs),
which are $d$-variate functions that depend only on few relevant directions,
i.e., have the form $g(\vec W \x)$ for an
unknown link function $g$ and a $k \times d$ matrix $\vec W$.
Multi-index models cover a wide range of commonly studied function classes,
including real-valued function classes
such as constant-depth neural networks with ReLU activations,
and Boolean concept classes such as intersections of halfspaces.
Our main result shows that query access gives significant runtime improvements
over random examples for agnostically learning
both real-valued and Boolean-valued MIMs.
Under standard regularity assumptions for the link function
(namely, bounded variation or surface area),
we give an agnostic query learner for MIMs
with running time $O(k)^{\mathrm{poly}(1/\epsilon)} \; \mathrm{poly}(d) $.
In contrast, algorithms that rely only on random labeled examples
inherently require $d^{\mathrm{poly}(1/\epsilon)}$ samples and runtime,
even for the basic problem of agnostically
learning a single ReLU or a halfspace.
As special cases of our general approach,
we obtain the following results:
\begin{itemize}[leftmargin=*]
\item For the class of depth-$\ell$, width-$S$ ReLU networks on
$\R^d$, our agnostic query learner runs in time $\mathrm{poly}(d) 2^{\mathrm{poly}(\ell S/\epsilon)}$.
This bound qualitatively matches the runtime of an algorithm by~\cite{CKM22}
for the realizable PAC setting with random examples.
\item For the class of arbitrary intersections of $k$ halfspaces on $\R^d$,
our agnostic query learner runs in time $\mathrm{poly}(d) \, 2^{\mathrm{poly}(\log (k)/\epsilon)}$.
Prior to our work, no improvement over the agnostic PAC model complexity
(without queries) was known, even for the case of a single halfspace.
\end{itemize}
In both these settings, we provide evidence
that the $2^{\mathrm{poly}(1/\epsilon)}$ runtime dependence is required
for proper query learners, even for agnostically learning a single ReLU or halfspace.
Our algorithmic result establishes a strong computational
separation between
the agnostic PAC and the agnostic PAC+Query models under the Gaussian distribution for a range of natural function classes.
Prior to our work, no such separation was known for any natural concept class —
even for the case of
a single halfspace,
for which it was an open problem posed by Feldman~\cite{Feldman08}.
Our results are enabled by a general dimension-reduction technique
that leverages query access to estimate gradients of (a smoothed version of)
the underlying label function.
Authors
——-
Topic
—–
* foundations of machine learning
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
========================================================================================
Abstract
——–
Suppose we have a memory storing $0$s and $1$s and we want to estimate the frequency of $1$s by sampling.
We want to do this I/O-efficiently, exploiting that each read
gives a block of $B$ bits at unit cost; not just one bit. If the
input consists of uniform blocks: either all 1s or all 0s, then
sampling a whole block at a time does not reduce the number of
samples needed for estimation. On the other hand, if bits are randomly
permuted, then getting a block of $B$ bits is as good as getting $B$
indendent bit samples. However, we do not want to make any such assumptions on the
input.
Instead, our goal is to have an algorithm with instance-dependent performance guarantees which stops sampling blocks as soon as we know that we
have a probabilistically reliable estimate. We prove our algorithms to be
instance-optimal among algorithms oblivious to the order of the blocks,
which we argue is the strongest form of instance optimality we can hope for.
We also present similar results for I/O-efficiently estimating mean with both additive and multiplicative error, estimating histograms, quantiles, as well as the empirical cumulative distribution function.
We obtain our above results on I/O-efficient sampling by reducing to corresponding
problems in the so-called sequential estimation. In this setting, one samples from an unknown
distribution until one can provide an estimate with some desired error
probability.
Sequential estimation has been considered
extensively in statistics over the past century. However, the focus
has been mostly on parametric estimation, making stringent assumptions on the distribution of
the input, and thus not useful for our reduction. In this paper, we manage to make no assumptions on the input distribution (apart from
its support being a bounded set) by investigating sequential estimation from the perspective of and using
the techniques of theoretical computer science. Namely, we provide
non-parametric instance-optimal results for several fundamental problems: mean and
quantile estimation, as well as learning mixture distributions with
respect to $\ell_\infty$ and the so-called Kolmogorov-Smirnov
distance.
All our algorithms are simple, natural, and practical, and some are
even known from other contexts, e.g., from statistics in the
parameterized setting. The main technical difficulty is in analyzing them and proving that
they are instance optimal.
Authors
——-
Topics
——
* algorithms and data structures
* randomized algorithms
Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
============================================================================================
Abstract
——–
Vizing’s theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be edge colored using at most $\Delta + 1$ different colors [Diskret. Analiz, ’64]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in $\tilde{O}(mn)$ time. This was subsequently improved to $\tilde O(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al. [1985].
In this paper we present an algorithm that computes such an edge coloring in $\tilde O(mn^{1/3})$ time, giving the first polynomial improvement for this fundamental problem in over 40 years.
Authors
——-
Topics
——
* algorithmic graph theory
* algorithms and data structures
Improved Distance (Sensitivity) Oracles with Subquadratic Space
================================================================================
Abstract
——–
A \emph{distance oracle} (DO) for a graph $G$ is a data structure that, when queried with two vertices $s$ and $t$, returns an estimate $\widehat{d}(s,t)$ of their distance $d(s,t)$ in $G$. The oracle has stretch $(\alpha, \beta)$ if the estimate satisfies
$d(s,t) \le \widehat{d}(s,t) \le \alpha \cdot d(s,t) + \beta$. An $f$-\emph{edge fault-tolerant distance sensitivity oracle} ($f$-DSO) can additionally be queried with a set $F$ of at most $f$ edges and reports an estimate of the $s$-$t$-distance in the graph $G{-}F$.
Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch $\beta > 0$ allows one to make the multiplicative stretch $\alpha$ arbitrarily small.
This sidesteps a known lower bound of $\alpha \ge 3$ (for $\beta = 0$ and subquadratic space) [Thorup \& Zwick, JACM 2005]. We present a DO for graphs with edge weights in $[0,W]$ that, for any positive integer $t$ and any $c \in (0, t/2]$, has stretch $(1{+}\frac{1}{t}, 2W)$, space $\widetilde{O}(n^{2-\frac{c}{t}})$, and query time $O(n^c)$.
These are the first subquadratic-space DOs with $(1+\epsilon, O(1))$-stretch generalizing Agarwal and Godfrey’s results for sparse graphs [SODA 2013] to general undirected graphs. We also construct alternative DOs with even smaller space at the cost of a higher additive stretch. For any integer $k \ge 1$, the DOs have a stretch $(2k{-}1{+}\frac{1}{t},4kW)$, space $O(n^{1+\frac{1}{k}(1- \frac{c}{8t})})$, and query time $O(n^{c})$.
Our second contribution is a framework that turns any $(\alpha,\beta)$-stretch DO for unweighted graphs into an $(\alpha (1{+}\varepsilon),\beta)$-stretch \(f\)-DSO
that for sensitivity $f = o(\log(n)/\log\log n)$ retains subquadratic space.
This generalizes a recent result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [STOC 2023] for the special case of stretch $(3,0)$ and $f = O(1)$. Our techniques also allow us to derandomize the entire construction. We combine the framework with our new distance oracle to obtain an \(f\)-DSO that, for any $\gamma \in (0, (t{+}1)/2]$, has stretch $((1{+}\frac{1}{t}) (1{+}\varepsilon), 2)$, space $n^{ 2- \frac{\gamma}{(t+1)(f+1)} + o(1)}/\varepsilon^{f+2}$, and query time $\widetilde{O}(n^{\gamma} /{\varepsilon}^2)$. This is the first deterministic $f$-DSO with subquadratic space, near-additive stretch, and sublinear query time.
Authors
——-
Topic
—–
* algorithms and data structures
An Improved Line-Point Low-Degree Test
=======================================================
Abstract
——–
We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function $f\colon \F_q^m \to \F_q$ from the space of degree-$d$ polynomials, i.e., the expected agreement of the function from univariate degree-$d$ polynomials over a randomly chosen line in $\F_q^m$, and prove that if this local agreement is $\epsilon \geq \Omega((\nicefrac{d}{q})^\tau))$ for some fixed $\tau > 0$, then there is a global degree-$d$ polynomial $Q\colon\F_q^m \to \F_q$ with agreement nearly $\epsilon$ with $f$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$-query robust test in the “high-error” regime (i.e., when $\epsilon < \nicefrac{1}{2}$). The previous results in this space either required $\epsilon > \nicefrac{1}{2}$ (Polishchuk \& Spielman, STOC 1994), or $q = \Omega(d^4)$ (Arora \& Sudan, Combinatorica 2003), or needed to measure local distance on $2$-dimensional “planes” rather than one-dimensional lines leading to $\Omega(d^2)$-query complexity (Raz \& Safra, STOC 1997).
Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case ($m = O(1)$) and then “bootstrapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora \& Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $m$, where previous works needed to work with $m = 3$ or $m = 4$ — arguably this bootstrapping is significantly simpler than those in prior works.
Authors
——-
3. Ramprasad Saptharishi <
[email protected]> (Tata Institute of Fundamental Research)
Topics
——
* algebraic computation
* algorithmic coding theory
* sublinear algorithms
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
================================================================================================
Abstract
——–
We study revenue maximization in the unit-demand single-buyer setting. Our main result is
that Uniform-Ironed-Virtual-Value Item Pricing guarantees a tight 3-approximation to the Duality
Relaxation Benchmark [Chawla-Malec-Sivan, EC’10/GEB’15; Cai-Devanur-Weinberg, STOC’16/
SICOMP’21], breaking the barrier of 4 since [Chawla-Hartline-Malec-Sivan, STOC’10; Chawla-
Malec-Sivan, EC’10/GEB’15]. To our knowledge, this is the first benchmark-tight revenue guarantee of any simple multi-item mechanism.
Technically, all previous works employ Myerson Auction as an intermediary. The barrier of 4
follows as Uniform-Ironed-Virtual-Value Item Pricing achieves a tight 2-approximation to Myerson
Auction, which then achieves a tight 2-approximation to Duality Relaxation Benchmark. Instead,
our new approach avoids Myerson Auction, thus enabling the improvement. Central to our work
are a benchmark-based 3-competitive prophet inequality and its fully constructive proof. Such
variant prophet inequalities shall find future applications, e.g., to Multi-Item Mechanism Design
where optimal revenues are relaxed to various more accessible benchmarks.
We complement our benchmark-tight ratio with an impossibility result. All previous works
and ours follow the single-dimensional representative approach introduced by [Chawla-Hartline-
Kleinberg, EC’07]. Against Duality Relaxation Benchmark, it turns out that this approach cannot
beat our bound of 3 for a large class of Item Pricing’s.
Authors
——-
Topics
——
* algorithmic game theory
* economics and computation
An Improved Pseudopolynomial Time Algorithm for Subset Sum
===========================================================================
Abstract
——–
We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set $X$ of $n$ positive integers and a target $t$, Subset Sum asks whether some subset of $X$ sums to $t$. Bringmann proposes an $\widetilde{O}(n + t)$-time algorithm [Bringmann SODA’17], and an open question has naturally arisen: can Subset Sum be solved in $O(n + w)$ time? Here $w$ is the maximum integer in $X$. We make a progress towards resolving the open question by proposing an $\widetilde{O}(n + \sqrt{wt})$-time algorithm.
Authors
——-
Topics
——
* algorithms and data structures
* combinatorial optimization
* parametrized algorithms
* randomized algorithms
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
====================================================================================
Abstract
——–
In the dynamic metric $k$-median problem, we wish to maintain a set of $k$ centers $S \subseteq V$ in an input metric space $(V, d)$ that gets updated via point insertions/deletions, so as to minimize the objective $\sum_{x \in V} \min_{y \in S} d(x, y)$. The quality of a dynamic algorithm is measured in terms of its approximation ratio, “recourse” (the number of changes in $S$ per update) and “update time” (the time it takes to handle an update). The ultimate goal in this line of research is to obtain a dynamic $O(1)$ approximation algorithm with $\tilde{O}(1)$ recourse and $\tilde{O}(k)$ update time.
Dynamic $k$-median is a canonical example of a class of problems known as dynamic $k$-clustering, that has received significant attention in recent years [Fichtenberger et al, SODA’21], [Bateni et al, SODA’23], [Lacki et al, SODA’24]. To the best of our knowledge, however, all these previous papers either attempt to minimize the algorithm’s recourse while ignoring its update time, or minimize the algorithm’s update time while ignoring its recourse. For dynamic $k$-median in particular, the state-of-the-art results get $\tilde{O}(k^2)$ update time and $O(k)$ recourse~[Cohen-Addad et al, ICML’19], [Henzinger and Kale, ESA’20], [Bhattacharya et al, NeurIPS’23]. But, this recourse bound of $O(k)$ can be trivially obtained by recomputing an optimal solution from scratch after every update, provided we ignore the update time. In addition, the update time of $\tilde{O}(k^2)$ is polynomially far away from the desired bound of $\tilde{O}(k)$. We come {\em arbitrarily close} to resolving the main open question on this topic, with the following results.
(I) We develop a new framework of {\em randomized local search} that is suitable for adaptation in a dynamic setting. For every $\epsilon > 0$, this gives us a dynamic $k$-median algorithm with $O(1/\epsilon)$ approximation ratio, $\tilde{O}(k^{\epsilon})$ recourse and $\tilde{O}(k^{1+\epsilon})$ update time. This framework also generalizes to dynamic $k$ clustering with $\ell^p$-norm objectives. As a corollary, we obtain similar bounds for the dynamic $k$-means problem, and a new trade-off between approximation ratio, recourse and update time for the dynamic $k$-center problem.
(II) If it suffices to maintain only an estimate of the {\em value} of the optimal $k$-median objective, then we obtain a $O(1)$ approximation algorithm with $\tilde{O}(k)$ update time. We achieve this result via adapting the Lagrangian Relaxation framework of [Jain and Vazirani, JACM’01], and a facility location algorithm of [Mettu and Plaxton, FOCS’00] in the dynamic setting.
Authors
——-
Topics
——
* algorithms and data structures
* approximation algorithms
* combinatorial optimization
* foundations of machine learning
* online algorithms
* randomized algorithms
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
===============================================================================
Abstract
——–
We design polynomial size, constant depth (namely, $\mathsf{AC}^0$) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any number of polynomials. Previously, the best known arithmetic formulae for these problems required super-polynomial size, regardless of depth.
These results are based on new algorithmic techniques to compute various symmetric functions in the roots of polynomials, as well as manipulate the multiplicities of these roots, without having access to them. These techniques allow $\mathsf{AC}^0$ computation of a large class of linear and polynomial algebra problems, which include the above as special cases.
We extend these techniques to problems whose inputs are multivariate polynomials, which are represented by $\mathsf{AC}^0$ arithmetic circuits. Here too we solve problems such as computing the GCD and squarefree decomposition in $\mathsf{AC}^0$.
Authors
——-
Topics
——
* algebraic computation
* parallel and distributed algorithms
Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$
Worst-Case Update Time
================================================================================================
Abstract
——–
We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph $G=(V,E)$ with $n$ vertices undergoing both edge insertions and deletions, and an arbitrary parameter $\epsilon$ where $1/\log^{c} n<\epsilon<1$ and $c>0$ is a small constant, we can deterministically maintain a data structure with $O(n^{\epsilon})$ worst-case update time that, given any pair of vertices $(u,v)$, returns a $2^{{\rm poly}(1/\epsilon)}$-approximate distance between $u$ and $v$ in ${\rm poly}(1/\epsilon)\log\log n$ query time.
Our algorithm significantly advances the state-of-the-art in two aspects, both for fully dynamic algorithms and even decremental algorithms.
First, no existing algorithm with \emph{worst-case update time} guarantees a $o(n)$-approximation while also achieving an $n^{2-\Omega(1)}$ update and $n^{o(1)}$ query time, while our algorithm offers a constant $O_{\epsilon}(1)$-approximation with $O(n^\epsilon)$ update time and $O_{\epsilon}(\log \log n)$ query time.
Second, even if amortized update time is allowed, it is the first \emph{deterministic} constant-approximation algorithm with $n^{1-\Omega(1)}$ update and query time. The best result in this direction is the recent deterministic distance oracle by Chuzhoy and Zhang [STOC 2023] which achieves an approximation of $(\log\log n)^{2^{O(1/\epsilon^{3})}}$ with amortized update time of $O(n^{\epsilon})$ and query time of $2^{{\rm poly}(1/\epsilon)}\log n\log\log n$.
We obtain the result by dynamizing tools related to length-constrained expanders [Haeupler-Räcke-Ghaffari, STOC 2022; Haeupler-Hershkowitz-Tan, 2023; Haeupler-Huebotter-Ghaffari, 2022]. Our technique completely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.
Authors
——-
Topic
—–
* algorithms and data structures
Lempel-Ziv (LZ77) Factorization in Sublinear Time
==================================================================
Abstract
——–
Lempel-Ziv (LZ77) factorization is a fundamental problem in string
processing: Greedily partition a given string $T$ from left to right
into blocks (called \emph{phrases}) so that each phrase is either the
leftmost occurrence of a single letter or the longest prefix of the
unprocessed suffix that has another occurrence earlier in the text.
This simple routine has numerous applications. Most importantly, the
LZ77 factorization is the central component and the computational
bottleneck of most existing compression algorithms (utilized in
formats like ${\tt zip}$, ${\tt pdf}$, and ${\tt png}$). LZ77 is also
a widely used algorithmic tool for the detection of repetitions and
periodicities in strings, and the centerpiece of many powerful
compressed indexes that enable computation directly over compressed
data. LZ77 factorization is one of the most studied problems in
string processing. In the 47 years since its inception, numerous
efficient algorithms were developed for different models of
computation, including parallel, GPU, external-memory, and
quantum. Remarkably, however, the complexity of the most basic problem
is still not settled: All existing algorithms in the RAM model run in
$\Omega(n)$ time, which is a $\Theta(\log n)$ factor away from the
lower bound of $\Omega(n / \log n)$ (following simply from the
necessity to read the entire input, which takes $\Theta(n / \log n)$
space for any $T \in \{{\tt 0}, {\tt 1}\}^{n}$). Sublinear-time
algorithms are known for nearly all other fundamental problems on
strings, but LZ77 seems resistant to all currently known techniques.
We present the first $o(n)$-time algorithm for construction the LZ77
factorization, breaking the linear-time barrier present for nearly 50
years. More precisely, we show that, in the standard RAM model, it is
possible to compute the LZ77 factorization of a given length-$n$
string $T \in \{{\tt 0}, {\tt 1}\}^{n}$ in $\mathcal{O}(n / \sqrt{\log
n}) = o(n)$ time and using the optimal $\mathcal{O}(n / \log n)$
working space. Our algorithm generalizes to larger alphabets $\Sigma =
[0 .. \sigma)$, where $\sigma = n^{\mathcal{O}(1)}$. The runtime and
working space then become $\mathcal{O}((n \log \sigma) / \sqrt{\log
n})$ and $\mathcal{O}(n / \log_{\sigma} n)$, respectively. To achieve
this sublinear-time LZ77 algorithm, we prove a more general result: We
show that, for any constant $\epsilon \in (0, 1)$ and string $T \in [0
.. \sigma)^{n}$, in $\mathcal{O}((n \log \sigma) / \sqrt{\log n})$
time and using $\mathcal{O}(n / \log_{\sigma} n)$ working space, we
can construct an index of optimal size $\mathcal{O}(n / \log_{\sigma}
n)$ that, given any substring $P = T[j .. j + \ell)$ specified with a
pair $(j,\ell)$, computes the leftmost occurrence of $P$ in $T$ in
$\mathcal{O}(\log^{\epsilon} n)$ time. In other words, we solve the
indexing/online variant of the LZ77 problem, where we can efficiently
query the phrase length starting at any position. Our solution is
based on a new type of queries that we call \emph{prefix range minimum
queries} or \emph{prefix RMQ}. After developing an efficient solution
for these queries, we provide a general reduction showing that any new
tradeoff for the prefix RMQ implies a new tradeoff for an index
finding leftmost occurrences (and hence a new LZ77 factorization
algorithm).
Authors
——-
Topic
—–
* algorithms and data structures
The Tractability Border of Reachability in Simple Vector Addition Systems with
States
================================================================================================
Abstract
——–
Vector Addition Systems with States (VASS), equivalent to Petri nets, are a well-established model of concurrency.
A d-VASS can be seen as directed graph whose edges are labelled by d-dimensional integer vectors.
While following a path, the values of d nonnegative integer counters are updated according to the integer labels.
The central algorithmic challenge in VASS is the reachability problem: is there a run from a given starting node and counter values to a given target node and counter values?
When the input is encoded in binary, reachability is computationally intractable: even in dimension one, it is NP-hard.
In this paper, we comprehensively characterise the tractability border of the problem when the input is encoded in unary.
For our main result, we prove that reachability is NP-hard in unary encoded 3-VASS, even when structure is heavily restricted to be a simple linear-path scheme.
This improves upon a recent result of Czerwiński and Orlikowski [LICS 2022], in both the number of counters and expressiveness of the considered model, as well as answers open questions of Englert, Lazić, and Totzke [LICS 2016] and Leroux [PETRI NETS 2021].
The underlying graph structure of a simple linear path scheme (SLPS) is just a path with self-loops at each node.
We also study the exceedingly weak model of computation that is SPLS with counter updates in {-1, 0, +1}.
Here, we show that reachability is NP-hard when the dimension is bounded by O(α(k)), where α is the inverse Ackermann function and k bounds the size of the SLPS.
We complement our result by presenting a polynomial-time algorithm that decides reachability in 2-SLPS when the initial and target configurations are specified in binary.
To achieve this, we show that reachability in such instances is well-structured: all loops, except perhaps for a constant number, are taken either polynomially many times or almost maximally.
This extends the main result of Englert, Lazić, and Totzke [LICS 2016] who showed the problem is in NL when the initial and target configurations are specified in unary.
Authors
——-
Applications (DIMAP) & Department of Computer Science, University of Warwick, Coventry, UK)
its Applications (DIMAP) & Department of Computer Science, University of Warwick, Coventry,
UK)
for Informatics, Saarbrucken, Germany)
Topic
—–
* computational complexity
Semi-Bandit Learning for Monotone Stochastic Optimization
==========================================================================
Abstract
——–
Stochastic optimization is a widely used approach for optimization under uncertainty, where uncertain input parameters are modeled by random variables. Exact or approximation algorithms have been obtained for several fundamental problems in this area. However, a significant limitation of this approach is that it requires full knowledge of the underlying probability distributions. {\em Can we still get good (approximation) algorithms if these distributions are unknown, and the algorithm needs to learn them through repeated interactions?} In this paper, we resolve this question for a large class of “monotone” stochastic problems, by providing a generic online learning algorithm with $\sqrt{T \log T}$ regret relative to the best approximation algorithm (under known distributions). Importantly, our online algorithm works in a semi-bandit setting, where in each period, the algorithm only observes samples from the random variables that were actually probed. Our framework applies to several fundamental problems in stochastic optimization such as prophet inequality, Pandora’s box, stochastic knapsack, stochastic matchings and stochastic submodular optimization.
Authors
——-
Topics
——
* approximation algorithms
* computational learning theory
Sparse graph counting and Kelley–Meka bounds for binary systems
==================================================================================
Abstract
——–
In a major breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. In this work, we extend their result establishing similar bounds for all linear patterns defined by translation-invariant binary systems of linear forms, where “binary” indicates that every linear form depends on exactly two variables.
A key ingredient in our proof is a \emph{graph counting lemma}. The classical graph counting lemma, developed by Thomason (Random Graphs 1985) and Chung, Graham, and Wilson (Combinatorica 1989), is a fundamental tool in combinatorics. For a fixed graph $H$, it states that the number of copies of $H$ in a pseudorandom graph $G$ is similar to the number of copies of $H$ in a purely random graph with the same edge density as $G$. However, this lemma is only non-trivial when $G$ is a dense graph. In this work, we prove a graph counting lemma that is also effective when $G$ is sparse. Moreover, our lemma is well-suited for density increment arguments in additive number theory. These results hinge on the recent technology developed by Kelley and Meka and the follow-up work by Kelley, Lovett, and Meka (STOC 2024).
As a sample application, we obtain a strong bound for the Tur\’an problem in Abelian Cayley graphs: we prove that an Abelian Cayley graph on $N$ vertices that does not contain a clique of size $r$ as a subgraph, must have at most $2^{-\Omega_r(\log^{1/16}N)}\cdot N$ edges.
Authors
——-
Topics
——
* combinatorics
* pseudorandomness and derandomization
Replicability in High Dimensional Statistics
=============================================================
Abstract
——–
The replicability crisis is a major issue across nearly all areas of empirical science, calling for the formal study of replicability in statistics. Motivated in this context, [Impagliazzo, Lei, Pitassi, and Sorrell STOC 2022] introduced the notion of replicable learning algorithms, and gave basic procedures for $1$-dimensional tasks including statistical queries. In this work, we study the computational and statistical cost of replicability for several fundamental \emph{high dimensional} statistical tasks, including multi-hypothesis testing and mean estimation.
Our main contribution establishes a computational and statistical equivalence between optimal replicable algorithms and high dimensional isoperimetric tilings.
As a consequence, we obtain matching sample complexity upper and lower bounds for replicable mean estimation of distributions with bounded covariance, resolving an open problem of [Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, and Sorrell, STOC2023] and for the $N$-Coin Problem, resolving a problem of [Karbasi, Velegkas, Yang, and Zhou, NeurIPS2023] up to log factors.
While our equivalence is computational, allowing us to shave log factors from the best known efficient algorithms, efficient isoperimetric tilings are not known. To circumvent this, we introduce several relaxed paradigms that do allow for sample and computationally efficient algorithms, including allowing pre-processing, adaptivity, and approximate replicability. In these cases we give efficient algorithms matching or beating the best known sample complexity for mean estimation and the coin problem, including a generic procedure that reduces the standard quadratic overhead of replicability to linear in expectation.
Authors
——-
Topics
——
* computational learning theory
* foundations of machine learning
* high-dimensional algorithms
Efficient Unitary Designs from Random Sums and Permutations
============================================================================
Abstract
——–
A unitary $k$-design is an ensemble of unitaries that matches the first $k$ moments of the Haar measure. In this work, we provide two efficient constructions of $k$-designs on $n$-qubits using new random matrix theory techniques.
Our first construction is based on exponentiating sums of random i.i.d. random Hermitian matrices and uses $\tilde{O}(k^2 n^2)$-many gates. In the spirit of central limit theorems, we show this random sum approximates the Gaussian Unitary Ensemble (GUE). We then show that the product of just two exponentiated GUE matrices is already approximately Haar random. Our second construction is based on products of exponentiated sums of random permutations and uses $\tilde{O}(k poly(n))$ many gates. The $k$-dependence is optimal (up to polylogarithmic factors) and is inherited from the efficiency of existing $k$-wise independent permutations. Meanwhile, replacing random permutations with quantum-secure pseudorandom permutations (PRPs), we also obtain a pseudorandom unitary (PRU) ensemble that is secure under nonadaptive queries.
A central feature of both proofs is a new connection between the polynomial method in quantum query complexity and the large-dimension ($N$) expansion in random matrix theory. In particular, the first construction uses the polynomial method to control high moments of certain random matrix ensembles without requiring delicate Weingarten calculations. In doing so, we define and solve a moment problem on the unit circle, asking whether a finite number of equally weighted points can reproduce a given set of moments. In our second construction, the key step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$.
Authors
——-
Topics
——
* cryptography
* pseudorandomness and derandomization
* quantum computing
Commitments are equivalent to one-way state generators
=======================================================================
Abstract
——–
One-way state generators (OWSG) are natural quantum analogs to classical one-way functions. We show that $O\left(\frac{n}{\log(n)}\right)$-copy OWSGs ($n$ represents the input length) are equivalent to $poly(n)$-copy OWSG and to quantum commitments. Since known results show that $o\left(\frac{n}{\log(n)}\right)$-copy OWSG cannot imply commitments, this shows that $O\left(\frac{n}{\log(n)}\right)$-copy OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography).
Our construction follows along the lines of H\r{a}stad, Impagliazzo, Levin and Luby [HILL], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [HILL]. Since we do not argue conditioned on the output of the one-way function, our construction and analysis are arguably simpler and may be of independent interest.
Authors
——-
Topics
——
* cryptography
* pseudorandomness and derandomization
* quantum computing
On the Existence of Seedless Condensers: Exploring the Terrain
===============================================================================
Abstract
——–
While the existence of randomness extractors, both seeded and seedless, has been studied for many sources of randomness, currently, not much is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, one-sided NOSF (oNOSF) sources (originally defined as SHELA sources in [AORSV, EUROCRYPT’20]), and almost Chor-Goldreich (CG) sources as defined in [DMOZ, STOC’23]. Here, we will think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\mathbf{X}_\ell$ on $\ell$ symbols where at least $g$ out of these $\ell$ symbols are “good” (i.e., have some min-entropy requirement), denoted as a $(g,\ell)$-source, and the remaining “bad” $\ell-g$ symbols may adversarially depend on these $g$ good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions.
Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [DMOZ, STOC’23], where they explicitly construct a seedless condenser for a restricted subset of $(g,\ell)$-adversarial CG sources.
The following are our main results concerning seedless condensers for each of these three sources.
* oNOSF sources
– When $g\leq\ell/2$, we prove that condensing with error 0.99 above rate $\frac{1}{\lfloor \ell/g \rfloor}$ is impossible. In fact, we show that this is tight.
– Quite surprisingly, for $g> \ell/2$, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy. Our results are based on a new type of two-source extractors, called \emph{output-light two-source extractors}, that we introduce and prove the existence of.
* Adversarial CG sources
– We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results.
– We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate $1/2$.
* NOSF sources
– We show that condensing with constant error above rate $\frac{g}{\ell}$ is impossible for uniform NOSF sources for any $g$ and $\ell$, thus ruling out the possibility of any non-trivial condensing. This shows an interesting distinction between NOSF sources and oNOSF sources.
Authors
——-
Topics
——
* combinatorics
* pseudorandomness and derandomization
Computing Approximate Centerpoints in Polynomial Time
======================================================================
Abstract
——–
The centerpoint is arguably the most natural generalization of the median to higher dimensions. Intuitively, a centerpoint of a point set is such that any hyperplane passing through the point results in a an approximately balanced partition of the point set. Helly’s theorem guarantees the existence of a point with depth $\Omega (1 / d)$ which is also known to be the best possible. On the other hand, polynomial time algorithms for approximating centerpoints only guarantee a point with depth $\Omega (1 / d^2)$, established nearly three decades ago. Unfortunately, even the simpler problem of testing whether a candidate point is a centerpoint is hard.
In this paper, we present a novel notion of approximation along with a new algorithm approach that enables efficient computation of a $\Omega(1 / d)$-depth point. Our main result is a randomized algorithm that computes an $\eps$-approximate centerpoint of depth $\Omega (1 / d)$; that is, the point returned by the algorithm is at most $\epsilon$ away the halfspaces characterizing points of depth at least $\Omega (1 / d)$ along any direction. Furthermore, the runtime of our algorithm is polynomial in $n, d, 1 / \epsilon, \log (1 / \delta)$ where $\delta$ denotes the failure probability of the algorithm.
Our approach is based on a reduction to the smoothed setting where each point is is given an independent Gaussian perturbation of scale $\epsilon$. In contrast to prior work, our algorithm is based on techniques from continuous optimization and leverages a novel connection between the problem of testing an approximate centerpoint and the Radial Isotropic Transformation, a central tool with diverse applications in mathematics and computer science. We show that the solution to this testing problem yields an approximate separation oracle for the set of large depth points, enabling its use in a gradient-descent style approach to compute centerpoints.
Author
——
Topics
——
* algorithms and data structures
* approximation algorithms
* average-case algorithms and complexity
* computational geometry
* computational learning theory
* continuous optimization
* high-dimensional algorithms
* randomized algorithms
* spectral methods
Fast decision tree learning solves hard coding-theoretic problems
==================================================================================
Abstract
——–
We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem ($k$-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is $O(n/\log n)$ (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections.
We show that \emph{any} improvement of Ehrenfeucht and Haussler’s algorithm will yield $O(\log n)$-approximation algorithms for $k$-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for $k$-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler’s algorithm. Furthermore, our reduction along with existing inapproximability results for $k$-NCP already rule out \emph{polynomial-time} algorithms for properly learning decision trees. A notable aspect of our results is that they hold even in the setting of \emph{weak} learning, whereas prior results were limited to the setting of strong learning.
Authors
——-
Topics
——
* computational complexity
* computational learning theory
* parametrized algorithms
Nearly Optimal List Labeling
=============================================
Abstract
——–
The list-labeling problem captures the basic task of storing a dynamically changing set of up to $n$ elements in sorted order in an array of size $m = (1 + \Theta(1))n$. The goal is to support insertions and deletions while moving around elements within the array as little as possible.
Until recently, the best known upper bound stood at $O(\log^2 n)$ amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized $O(\log^{3/2} n)$ expected-cost algorithm was discovered. The best randomized lower bound for this problem remains $\Omega(\log n)$, and closing this gap is considered to be a major open problem in data structures.
In this paper, we present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of $O(\log n \polyloglog n)$ amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.
Authors
——-
Topics
——
* algorithms and data structures
* online algorithms
* randomized algorithms
Quantum eigenvalue processing
==============================================
Abstract
——–
Many problems in linear algebra are solved by processing eigenvalues of the input matrices. As eigenvalues are not singular values for non-normal operators, these problems are out of reach on quantum computers by the well-known Quantum Singular Value Transformation (QSVT) algorithm and its descendants.
We present the algorithms Quantum EigenValue Estimation (QEVE) and Quantum EigenValue Transformation (QEVT) for high-dimensional matrices accessed through block-encoding oracles. We focus on inputs with real spectra and Jordan forms—a broad class of operators that can describe non-Hermitian physics and transcorrelated quantum chemistry. However, QEVT also efficiently handles general non-normal matrices with complex eigenvalues and ill-conditioned Jordan bases. Our approach is based on a conceptually simple reduction to the optimal scaling quantum linear system algorithm, and has performance comparable to QSVT for the special case of Hermitian inputs, where eigenvalues coincide with singular values in magnitude. Our results thus provide a unifying framework for processing eigenvalues on a quantum computer.
QEVE achieves Heisenberg scaling in estimating an eigenvalue of general matrices with real spectra and has optimal performance matching prior work when these matrices are Hermitian. QEVE queries the block-encoding and state preparation unitary $\mathbf{O}\left(\frac{\alpha\kappa}{\epsilon}\log(1/p)\right)$ times with error $\epsilon$, failure probability $p$, normalization factor $\alpha$ of the block encoding, and condition number $\kappa$ of its basis transformation. In contrast, prior work based on reductions to suboptimal differential equation solvers have a multiplicative polylogarithmic overhead.
QEVT transforms eigenvalues using Faber polynomials, which generalize Chebyshev polynomials from the real unit interval to complex domains. As Faber expansions provide a close-to-best uniform polynomial approximation of complex analytic functions over complex domains, the query complexity of QEVT is also close-to-optimal. We apply QEVT to solve linear differential equations and obtain strictly linear scaling in the evolution time $t$ for average-case diagonalizable inputs with imaginary spectra. In contrast, prior art has a $\mathrm{polylog}(t)$ overhead. We also develop a QEVT-based algorithm for preparing the ground state of matrices with real spectra, which generalizes prior nearly optimal result for Hermitian Hamiltonians.
Underlying both QEVE and QEVT is an efficient quantum algorithm for preparing a Faber history state—a superposition of Faber polynomials of general non-normal matrices. In prior art, efficient methods were only available for Chebyshev polynomials of Hermitian inputs. Also of independent interest are our techniques to generate $n$ Fourier coefficients using $\mathbf{O}(\mathrm{polylog}(n))$ gates, whereas prior approaches have a cost of $\mathbf{\Theta}(n)$.
Authors
——-
Topic
—–
* quantum computing
Quantum computational advantage with constant-temperature Gibbs sampling
=========================================================================================
Abstract
——–
A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state. This thermalization process defines a natural, physics-inspired model of quantum computation. However, whether quantum computational advantage can be achieved within this realistic physical setup has remained open, due to the challenge of finding systems that thermalize quickly, but are hard to classically simulate. Here we consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures, and prove that this task demonstrates quantum computational advantage. We design a family of commuting almost-local Hamiltonians (parent Hamiltonians of shallow quantum circuits) and prove that they rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). On the other hand, we show that no polynomial time classical algorithm can sample from the measurement outcome distribution by reducing to the classical hardness of sampling from noiseless shallow quantum circuits. The key step in the reduction is constructing a fault-tolerance scheme for shallow IQP circuits against input noise.
Authors
——-
Topic
—–
* quantum computing
Towards Instance-Optimal Euclidean Spanners
============================================================
Abstract
——–
Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic “compactness” measures of a Euclidean spanner $E$ are the size (number of edges) $|E|$ and the weight (sum of edge weights) $\|E\|$. The state-of-the-art constructions of Euclidean $(1+\epsilon)$-spanners in $\mathbb{R}^d$ have $O_d(n\cdot \epsilon^{-d+1})$ edges (or \emph{sparsity} $O_d(\epsilon^{-d+1})$) and weight $O_d(\epsilon^{-d}\log\epsilon^{-1}) \cdot \|E_{\mathsf{mst}}\|$ (or \emph{lightness} $O_d(\epsilon^{-d}\log\epsilon^{-1})$); here $O_d$ suppresses a factor of $d^{O(d)}$ and $\|E_{\mathsf{mst}}\|$ denotes the weight of a minimum spanning tree of the input point set.
Importantly, these two upper bounds are (near-)optimal (up to the $d^{O(d)}$ factor and disregarding the factor of $\log(\epsilon^{-1})$ in the lightness bound) for some \emph{extremal instances} [Le and Solomon, 2019], and therefore they are (near-)\emph{optimal in an existential sense}.
Moreover, both these upper bounds are attained by the same construction—the classic \emph{greedy spanner}, whose sparsity and lightness are not only existentially optimal, but they also significantly outperform those of any other Euclidean spanner construction studied in an experimental study by [Farshi-Gudmundsson, 2009] for various practical point sets in the plane. This raises the natural question of whether the greedy spanner is (near-) optimal for \emph{any point set instance}?
Motivated by this question, we initiate the study of \emph{instance optimal Euclidean spanners}. Our results are two-fold.
* Rather surprisingly (given the aforementioned experimental study), we demonstrate that the \emph{greedy spanner is far from being instance optimal}, even when allowing its stretch to grow. More concretely, we design two hard instances of point sets in the plane, where the greedy $(1+x \epsilon)$-spanner (for basically any parameter $x \geq 1$) has $\Omega_x(\epsilon^{-1/2}) \cdot |E_\mathrm{spa}|$ edges and weight $\Omega_x(\epsilon^{-1}) \cdot \|E_\mathrm{light}\|$, where $E_\mathrm{spa}$ and $E_\mathrm{light}$ denote the per-instance sparsest and lightest $(1+\epsilon)$-spanners, respectively, and the $\Omega_x$ notation suppresses a polynomial dependence on $1/x$.
* As our main contribution, we design a new construction of Euclidean spanners, which is inherently different from known constructions, achieving the following bounds: a stretch of $1+\epsilon\cdot 2^{O(\log^*(d/\epsilon))}$ with $O(1) \cdot |E_\mathrm{spa}|$ edges and weight $O(1) \cdot \|E_\mathrm{light}\|$. In other words, we show that a slight increase to the stretch suffices for obtaining \emph{instance optimality up to an absolute constant for both sparsity and lightness}. Remarkably, there is only a log-star dependence on the dimension in the stretch, and there is no dependence on it whatsoever in the number of edges and weight. In general, for any integer $k \geq 1$, we can construct a Euclidean spanner in $\mathbb{R}^d$ of stretch $1+\epsilon\cdot 2^{O(k)}$ with $O(\log^{(k)}(\epsilon^{-1}) + \log^{(k-1)}(d)) \cdot |E_\mathrm{spa}|$ edges and weight $O(\log^{(k)}(\epsilon^{-1}) + \log^{(k-1)}(d)) \cdot \|E_\mathrm{light}\|$, where $\log^{(k)}$ denotes the $k$-iterated logarithm.
Authors
——-
4. Csaba D. T\’oth <
[email protected]> (California State University Northridge and Tufts
University)
Topics
——
* algorithmic graph theory
* algorithms and data structures
* computational geometry
Stochastic Online Correlated Selection
=======================================================
Abstract
——–
We initiate the study of Stochastic Online Correlated Selection (SOCS), a family of online rounding algorithms for the general Non-IID model of Stochastic Online Submodular Welfare Maximization and its special cases such as unweighted and vertex-weighted Online Stochastic Matching, Stochastic AdWords, and Stochastic Display Ads. At each time step, the algorithm sees the type of an online item and a fractional allocation of the item, then immediately allocates the item to an agent. We propose a metric called the convergence rate that measures the quality of SOCS algorithms in the above special cases. This is cleaner than most metrics in the related Online Correlated Selection (OCS) literature and may be of independent interest.
We propose a Type Decomposition framework that reduces the design of SOCS algorithms to the easier special case of two-way SOCS. First, we sample a surrogate type whose fractional allocation is half-integer. The rounding is trivial for a one-way surrogate type fully allocated to one agent. For a two-way surrogate type split equally between two agents, we round it using a two-way SOCS. We design the distribution of surrogate types to get two-way surrogate types as often as possible, while respecting the original fractional allocation in expectation.
Following this framework, we make progress on numerous problems including two open questions related to AdWords:
– *Online Stochastic Matching:* We improve the state-of-the-art $0.666$ competitive ratio for unweighted and vertex-weighted matching by Tang, Wu, and Wu (STOC 2022) to $0.69$.
– *Query-Commit Matching:* We further enhance the above competitive ratio to $0.705$ in the random-order relaxation. Using a known reduction, we get that same ratio in the Query-Commit model. This result improves the best previous ratios $0.696$ for unweighted matching by Mahdian and Yan (STOC 2011) and $0.662$ for vertex-weighted matching by Jin and Williamson (WINE 2021).
– *Stochastic AdWords:* We give a $0.6338$ competitive algorithm for Stochastic AdWords, breaking the $1-\frac{1}{e}$ barrier for the first time. This answers a decade-old open question from the survey by Mehta (2013) about breaking this barrier in the IID special case.
– *AdWords:* The framework of Type Decomposition can also be applied to the adversarial model if the two-way rounding algorithm is oblivious to the distribution of future items. From the two-way algorithm’s viewpoint, the fixed adversarial sequence of items is a non-IID distribution that is a point mass, and the stochasticity comes from sampling surrogate types. Following this framework, we get the first multi-way OCS for AdWords, addressing an open question in the OCS literature. This further leads to a $0.504$ competitive ratio for AdWords, improving the previous $0.501$ ratio by Huang, Zhang, and Zhang (FOCS 2020).
– *Stochastic Display Ads:* We design a $0.644$ competitive online algorithm for Stochastic Display Ads, breaking the $1-\frac{1}{e}$ barrier for the first time.
Authors
——-
Topics
——
* algorithmic game theory
* online algorithms
Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
=============================================================================
Abstract
——–
A sequence of predictions is calibrated if and only if it induces no swap regret to all downstream decision tasks. We study the Maximum Swap Regret (MSR) of predictions for binary events: the swap regret maximized over all downstream tasks with bounded payoffs. Previously, the best online prediction algorithm for minimizing MSR is obtained by minimizing the $K_1$ calibration error, which upper bounds MSR up to a constant factor. However, recent work (Qiao
and Valiant, 2021) gives an $\Omega(T^{0.528})$ lower bound for the worst-case expected $K_1$ calibration error incurred by any randomized algorithm in $T$ rounds, presenting a barrier to achieving better rates for MSR. Several relaxations of MSR have been considered to overcome this barrier, via external regret (Kleinberg et al., 2023) and regret bounds depending polynomially on the number of actions in downstream tasks (Noarov et al., 2023; Roth and Shi, 2024). We show that the barrier can be surpassed without any relaxations: we give an efficient randomized prediction algorithm that guarantees $O(\sqrt{T}\log T)$ expected MSR. We also discuss the economic utility of calibration by viewing MSR as a decision-theoretic calibration error metric and study its relationship to existing metrics.
Authors
——-
Topic
—–
* online algorithms
Simple constructions of linear-depth t-designs and pseudorandom unitaries
==========================================================================================
Abstract
——–
Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties but cannot be implemented efficiently.
This has motivated a long line of research into random unitaries that “look” sufficiently Haar random while also being efficient to implement.
Two different notions of derandomisation have emerged:
$t$-designs are random unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.
In this work, we take a unified approach to constructing $t$-designs and PRUs.
For this, we introduce and analyse the “$PFC$ ensemble”, the product of a computational basis permutation $P$, a random binary phase operator $F$, and a random Clifford unitary $C$.
We show that this ensemble reproduces exponentially high moments of the Haar measure.
We can then derandomise the $PFC$ ensemble to show the following:
– **Linear-depth $t$-designs.** We give the first construction of a (diamond-error) approximate $t$-design on $n$ qubits with $O(n t)$ circuit depth, making significant progress towards the long-standing open question of optimal $t$-design constructions.
This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their $t$-wise independent counterparts.
– **Non-adaptive PRUs.** We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state.
This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts.
– **Adaptive pseudorandom isometries.** We show that if one considers isometries (rather than unitaries) from $n$ to $n + \omega(\log n)$ qubits, a small modification of our PRU construction achieves adaptive security, i.e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.
\end{itemize}
Authors
——-
Topics
——
* pseudorandomness and derandomization
* quantum computing
Exploration is Harder than Prediction: Cryptographically Separating
Reinforcement Learning from Supervised Learning
================================================================================================
Abstract
——–
Supervised learning is often computationally easy in practice. But to what extent does this mean that other modes of learning, such as reinforcement learning (RL), ought to be computationally easy by extension? In this work we show the first cryptographic separation between RL and supervised learning, by exhibiting a class of block MDPs and associated decoding functions where reward-free exploration is provably computationally harder than the associated regression problem. We also show that there is no computationally efficient algorithm for reward-directed RL in block MDPs, even when given access to an oracle for this regression problem.
It is known that being able to perform regression in block MDPs is necessary for finding a good policy; our results suggest that it is not sufficient. Our separation lower bound uses a new robustness property of the *Learning Parities with Noise (LPN)* hardness assumption, which is crucial in handling the dependent nature of RL data. We argue that separations and oracle lower bounds, such as ours, are a more meaningful way to prove hardness of learning because the constructions better reflect the practical reality that supervised learning by itself is often not the computational bottleneck.
Authors
——-
Topics
——
* computational learning theory
* foundations of machine learning
Optimal tradeoffs for estimating Pauli observables
===================================================================
Abstract
——–
We revisit the problem of \emph{Pauli shadow tomography}: given copies of an unknown $n$-qubit quantum state $\rho$, estimate $\text{tr}(P\rho)$ for some set of Pauli operators $P$ to within additive error $\epsilon$. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate $|\text{tr}(P\rho)|$ for all $P$ using $O(n/\epsilon^4)$ copies, but with $k\le n$ qubits of memory, $\Omega(2^{(n-k)/3})$ copies are needed.
These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain \emph{subset} of Paulis? What is the optimal dependence on $\epsilon$? What is the optimal tradeoff between quantum memory and sample complexity?
We answer all of these questions:
– For any subset $A$ of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to $\log |A|$ factors.
– We show any protocol that makes $\text{poly}(n)$-copy measurements must make $\Omega(1/\epsilon^4)$ measurements.
– For any protocol that makes $\text{poly}(n)$-copy measurements and only has $k < n$ qubits of memory, we show that $\widetilde{\Theta}(\min\{2^n/\epsilon^2, 2^{n-k}/\epsilon^4\})$ copies are necessary and sufficient.
The protocols we propose can also estimate the actual values $\text{tr}(P\rho)$, rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of \emph{purity testing} and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.
Authors
——-
Topic
—–
* quantum computing
Dot-Product Proofs and Their Applications
==========================================================
Abstract
——–
A *dot-product proof* (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof $\pi$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a *single* dot-product query $\langle q, (x \| \pi) \rangle$ jointly to $x$ and $\pi$. A DPP can be viewed as a 1-query *fully linear* PCP. We study the feasibility and efficiency of DPPs, obtaining the following results:
– **Small-field DPP.** For any finite field $\mathbb{F}$ and Boolean circuit $C$ of size $S$, there is a DPP for proving that there exists $w$ such that $C(x,w)=0$ with a proof $\pi$ of length $S\cdot\mathsf{poly}(|\mathbb{F}|)$ and soundness error $\varepsilon=O(1/\sqrt{|\mathbb{F}|})$. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields.
– **Large-field DPP.** If $|\mathbb{F}| \ge \mathsf{poly}(S/\varepsilon)$, there is a similar DPP with soundness error $\varepsilon$ and proof length $O(S)$ (in field elements).
The above results do not rely on the PCP theorem and their proofs are considerably simpler.
We apply our DPP constructions toward two kinds of applications.
– **Hardness of approximation.** We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) up to some constant factor $c>1$. Unlike previous PCP-based proofs, our proof yields *exponential-time* hardness under the exponential time hypothesis (ETH).
– **Succinct arguments.** We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier’s computation is dominated by a single group exponentiation.
Authors
——-
Topics
——
* computational complexity
* cryptography
Fast Mixing in Sparse Random Ising Models
==========================================================
Abstract
——–
Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Glauber dynamics for sampling from Ising models with sparse random interactions. It is now well-known that when the interaction matrix has spectral diameter less than $1$, Glauber dynamics mixes in $O(n\log n)$ steps. Unfortunately, such criteria fail dramatically for interactions supported on arguably the most well-studied sparse random graph: the Erdős–Rényi random graph $G(n,d/n)$. There is a scarcity of positive results in this setting due to the presence of almost linearly many outlier eigenvalues of unbounded magnitude.
We prove that for the _Viana-Bray spin glass_, where the interactions are supported on $G(n,d/n)$ and randomly assigned $\pm \beta$, Glauber dynamics mixes in $n^{1+o(1)}$ time with high probability as long as $\beta \leq O(1/\sqrt{d})$, independent of $n$. We further extend our results to random graphs drawn according to the $2$-community stochastic block model, as well as when the interactions are given by a “centered” version of the adjacency matrix. The latter setting is particularly relevant for the inference problem in community detection, as we demonstrate in a companion paper.
The primary technical ingredient in our proof is showing that with high probability, a sparse random graph can be decomposed into two parts — a _bulk_ which behaves like a graph with bounded maximum degree and a well-behaved spectrum, and a _near-forest_ with favorable pseudorandom properties. We then use this decomposition to design a localization procedure that interpolates to simpler Ising models supported only on the near-forest, and then execute a pathwise analysis to establish a modified log-Sobolev inequality.
Authors
——-
Topics
——
* average-case algorithms and complexity
* combinatorics
* high-dimensional algorithms
* Markov chains
* randomized algorithms
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
=================================================================================
Abstract
——–
A $(1 \pm \epsilon)$-sparsifier of a hypergraph $G(V,E)$ is a (weighted) subgraph that preserves the value of every cut to within a $(1 \pm \epsilon)$-factor. It is known that every hypergraph with $n$ vertices admits a $(1 \pm \epsilon)$-sparsifier with $\tilde{O}(n/\epsilon^2)$ hyperedges.
In this work, we explore the task of building such a sparsifier by using only linear measurements (a \emph{linear sketch}) over the hyperedges of $G$, and provide nearly-matching upper and lower bounds for this task.
Specifically, we show that there is a randomized linear sketch of size $\widetilde{O}(n r \log(m) / \epsilon^2)$ bits which with high probability contains sufficient information to recover a $(1 \pm \epsilon)$ cut-sparsifier
with $\tilde{O}(n/\epsilon^2)$ hyperedges for
any hypergraph with at most $m$ edges each of which has arity bounded by $r$. This immediately gives a dynamic streaming algorithm for hypergraph cut sparsification with an identical space complexity, improving on the previous best known bound of $\widetilde{O}(n r^2 \log^4(m) / \epsilon^2)$ bits of space (Guha, McGregor, and Tench, PODS 2015).
We complement our algorithmic result above with a nearly-matching lower bound. We show that for every $\epsilon \in (0,1)$, one needs $\Omega(nr \log(m/n) / \log(n))$ bits to construct a $(1 \pm \epsilon)$-sparsifier via linear sketching, thus showing that our linear sketch achieves an optimal dependence on both $r$ and $\log(m)$.
The starting point for our improved algorithm is importance sampling of hyperedges based on the new notion of $k$-cut strength introduced in the recent work of Quanrud (SODA 2024). The natural algorithm based on this concept leads to $\log m$ levels of sampling where errors can potentially accumulate, and this accounts for the $\text{polylog}(m)$ losses in the sketch size of the natural algorithm. We develop a more intricate analysis of the accumulation in error to show
most levels do not contribute to the error and actual loss is only $\text{polylog}(n)$. Combining with careful preprocessing (and analysis) this enables us to get rid of all extraneous $\log m$ factors in the sketch size, but the quadratic dependence on $r$ remains. This dependence originates from use of correlated $\ell_0$-samplers to recover a large number of low-strength edges in a hypergraph simultaneously by looking at neighborhoods of individual vertices. In graphs, this leads to discovery of $\Omega(n)$ edges in a single shot, whereas in hypergraphs, this may potentially only reveal $O(n/r)$ new edges, thus requiring $\Omega(r)$ rounds of recovery. To remedy this we introduce a new technique of \emph{random fingerprinting} of hyperedges which effectively eliminates the correlations created by large arity hyperedges, and leads to a scheme for recovering hyperedges of low strength with an optimal dependence on $r$. Putting all these ingredients together yields our linear sketching algorithm. Our lower bound is established by a reduction from the universal relation problem in the one-way communication setting.
Authors
——-
Topics
——
* streaming algorithms
* sublinear algorithms
Efficient Certificates of Anti-Concentration Beyond Gaussians
==============================================================================
Abstract
——–
A set of high dimensional points $X=\{x_1, x_2,\ldots, x_n\} \subseteq \R^d$ in isotropic position is said to be $\delta$-anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying $|\langle x_i,v \rangle|\leq \delta$ is at most $O(\delta)$. Motivated by applications to list-decodable learning and clustering, three recent works [KKK’19, RY’20, BK’21] considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points $X$ corresponds to samples from a Gaussian distribution. Their certificates eventually played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures. Unlike related efficient certificates of concentration properties that are known for wide class of distributions, the aforementioned approach has been limited only to \textit{rotationally invariant} distributions (and their affine transformations) with the only prominent example being Gaussian distributions.
This work presents a new (and arguably the most natural) formulation for anti-
concentration.
Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of \emph{non-Gaussian} distributions including anti-concentrated bounded continuous product distributions (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to all such distributions.
As in the case of previous works, our certificates are also obtained via relaxations in the sum-of-squares hierarchy.
However, the nature of our argument differs significantly from prior works that formulate anti-concentration as the non-negativity of an explicit polynomial.
Instead, our argument constructs a canonical integer program for anti-concentration and analysis a SoS relaxation of it, independent of the intended application. The explicit polynomials appearing in prior works can be seen as specific dual certificates to this program.
From a technical standpoint, unlike existing works that explicitly construct these sum-of-squares certificates, our argument relies on duality and analyzes a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial \emph{reweightings} to reduce the problem to analyzing only analytically \emph{dense} or \emph{sparse} directions.
Authors
——-
Topics
——
* computational learning theory
* foundations of machine learning
* high-dimensional algorithms
Minor Containment and Disjoint Paths in almost-linear time
===========================================================================
Abstract
——–
We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time $O_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the $O_H(\cdot)$-notation hides factors that depend on $H$ and are computable.
By the Graph Minor Theorem, this implies the existence of an $n^{1+o(1)}$-time membership test for every minor-closed class of graphs.
More generally, we give an $O_{H,|X|}(m^{1+o(1)})$-time algorithm for the rooted version of the problem, in which $G$ comes with a set of roots $X\subseteq V(G)$ and some of the branch sets of the sought minor model of $H$ are required to contain prescribed subsets of $X$; here, $m$ is the total number of vertices and edges of $G$.
This captures the Disjoint Paths problem, for which we obtain an $O_{k}(m^{1+o(1)})$-time algorithm, where $k$ is the number of terminal pairs. For all the mentioned problems, the fastest algorithms known before are due to Kawarabayashi, Kobayashi, and Reed [JCTB 2012], and have a time complexity that is quadratic in the number of vertices of $G$.
Our algorithm has two main ingredients: First, we show that by using the dynamic treewidth data structure of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023], the irrelevant vertex technique of Robertson and Seymour can be implemented in almost-linear time on apex-minor-free graphs.
Then, we apply the recent advances in almost-linear time flow/cut algorithms to give an almost-linear time implementation of the recursive understanding technique, which effectively reduces the problem to apex-minor-free graphs.
Authors
——-
Topics
——
* algorithmic graph theory
* algorithms and data structures
* parametrized algorithms
Gradient descent for unbounded convex functions on Hadamard manifolds and its
applications to scaling problems
================================================================================================
Abstract
——–
In this paper, we study asymptotic behaviors of continuous-time and discrete-time gradient flows of
a “lower-unbounded” convex function $f$ on a Hadamard manifold $M$, particularly, their convergence properties to the boundary $M^{\infty}$ at infinity of $M$.
We establish a duality theorem that the infimum of the gradient-norm $\|\nabla f(x)\|$ of $f$
over $M$
is equal to the supremum of the negative of the recession function $f^{\infty}$
of $f$ over the boundary $M^{\infty}$. Further,
the infimum and the supremum are
obtained by the limits of the gradient flows of $f$, provided the infimum is positive.
Our results feature convex-optimization ingredients of the moment-weight inequality
for reductive group actions by Georgoulas, Robbin, and Salamon,
and are applied to noncommutative optimization by B\”urgisser et al. FOCS 2019.
We show that the gradient descent of
the Kempf-Ness function for an unstable orbit
converges to a 1-parameter subgroup in the Hilbert-Mumford criterion, and
the associated moment-map sequence converges to the mimimum-norm point of the moment polytope.
We show further refinements on operator scaling—the left-right action
on a matrix tuple $A= (A_1,A_2,\ldots,A_N)$.
We characterize the gradient-flow limit of operator scaling
via a vector-space generalization of
the classical Dulmage-Mendelsohn decomposition of a bipartite graph.
Also, for a special case of $N = 2$,
we reveal that this limit determines
the Kronecker canonical form of matrix pencils $s A_1+A_2$.
Authors
——-
University)
Technology, The University of Tokyo)
Topic
—–
* continuous optimization
A Sampling Lovász Local Lemma for Large Domain Sizes
======================================================================
Abstract
——–
We present polynomial-time algorithms for aphttps://focs24.hotcrp.com/doc/focs24-paper279.pdfproximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime:
$$
pD^{2+o_q(1)}\lesssim 1.
$$
When the domain size $q$ of each variable becomes sufficiently large, this almost matches the known lower bound $pD^2\gtrsim 1$ for approximate counting and sampling solutions to atomic CSPs [Bezáková et al, SICOMP ’19; Galanis, Guo, Wang, TOCT ’22],
thus establishing an almost tight sampling Lovász local lemma for large domain sizes.
Authors
——-
Topic
—–
* randomized algorithms
Naively Sorting Evolving Data is Optimal and Robust
====================================================================
Abstract
——–
We study comparison sorting in the *evolving data model* [AKMU11], where the true total order changes *while* the sorting algorithm is processing the input. More precisely, each comparison operation of the algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the rank of a random item by a “small” random value. The goal is to maintain an ordering that remains close to the true order over time. Previous works have analyzed adaptations of classic sorting algorithms, assuming that an evolution step changes the rank of an item by just one, and that a fixed constant number $b$ of evolution steps take place between two comparisons. In fact, the only previous result achieving optimal $O(n)$ total deviation from the true order, where $n$ is the number of items, applies just for $b=1$ [BvDEGJ18].
We analyze a very simple sorting algorithm suggested in [M14], which samples a random pair of adjacent items in each step and swaps them if they are out of order.
We show that the algorithm achieves and maintains, with high probability, optimal total deviation, $O(n)$, and optimal maximum deviation, $O(\log n)$, under very general model settings. Namely, the perturbation introduced by each evolution step is sampled from a general distribution of bounded moment generating function, and we just require that the *average* number of evolution steps between two sorting steps be bounded by an (arbitrary) constant, where the average is over a linear number of steps.
The key ingredients of our proof are a novel potential function argument that inserts “gaps” in the list of items, and a general analysis framework which separates the analysis of sorting from that of the evolution steps, and is applicable to a variety of settings for which previous approaches do not apply.
Our results settle conjectures by [AKMU11] and [M14], and provide theoretical support for the empirical evidence that simple quadratic algorithms are optimal and robust for sorting evolving data [BvDEGJ18].
Authors
——-
Topics
——
* online algorithms
* parallel and distributed algorithms
* randomized algorithms
Tight Bounds for Sorting Under Partial Information
===================================================================
Abstract
——–
Sorting is one of the fundamental algorithmic problems in theoretical computer science.
It has a natural generalization, introduced by Fredman in 1976, called \emph{sorting under partial information}. The input consists of:
– a ground set $X$ of size $n$,
– a partial oracle $O_P$ (where partial oracle queries for any $(x_i, x_j)$ output whether $x_i \prec_P x_j$,
for some fixed partial order $P$),
– a linear oracle $O_L$ (where linear oracle queries for any $(x_i, x_j)$ output whether $x_i <_L x_j$,
where the linear order $L$ extends $P$)
\noindent
The goal is to recover the linear order $L$ on $X$ using the fewest number of linear oracle queries.
In this problem, we measure algorithmic complexity through three metrics: the number of linear oracle queries to $O_L$, the number of partial oracle queries to $O_P$, and the time spent (the number of algorithmic instructions required to identify for which pairs $(x_i, x_j)$ a partial or linear oracle query is performed).
Let $e(P)$ denote the number of linear extensions of $P$. Any algorithm requires worst-case $\log_2 e(P)$ linear oracle queries to recover the linear order on $X$.
In 1984, Kahn and Saks presented the first algorithm that uses $\Theta(\log e(P))$ linear oracle queries (using $O(n^2)$ partial oracle queries and exponential time). Since then, both the general problem and restricted variants have been consistently studied. The state-of-the-art for the general problem is by Cardinal, Fiorini, Joret, Jungers and Munro who at STOC’10 manage to separate the linear and partial oracle queries into a preprocessing and query phase. They can preprocess $P$ using $O(n^2)$ partial oracle queries and $O(n^{2.5})$ time. Then, given $O_L$, they uncover the linear order on $X$ in $\Theta(\log e(P))$ linear oracle queries and $O(n + \log e(P))$ time — which is worst-case optimal in the number of linear oracle queries but not in the time spent.
We present the first algorithm that uses a subquadratic number of partial oracle queries. For any constant $c \geq 1$, our algorithm can preprocess $O_P$ using $O(n^{1 + \frac{1}{c}})$ partial oracle queries and time. Given $O_L$, we uncover the linear order on $X$ using $\Theta(c \log e(P))$ linear oracle queries and time, which is worst-case optimal. We show a matching lower bound for the prepossessing also, as we show that there exist positive constants $(\alpha, \beta)$ where for any constant $c \geq 1$, any algorithm that uses at most $\alpha \cdot n^{1 + \frac{1}{c}}$ partial oracle queries must use worst-case at least $\beta \cdot c \cdot \log e(P)$ linear oracle queries. Thus, we solve the problem of sorting under partial information through an algorithm that is asymptotically tight across all three metrics.
Authors
——-
Topic
—–
* algorithms and data structures
Revisiting Agnostic PAC Learning
=================================================
Abstract
——–
PAC learning, dating back to Valiant’84, is a classic model for studying supervised learning. In the \emph{agnostic} setting, we have access to a hypothesis set $H$ and a training set of labeled samples $(x_1,y_1),\dots,(x_n,y_n) \in X \times \{-1,1\}$ drawn i.i.d.\ from an unknown distribution $D$. The goal is to produce a classifier $h : X \to \{-1,1\}$ that is competitive with the hypothesis $h^\star_D \in H$ having the least probability of mispredicting the label $y$ of a new sample $(x,y)\sim D$.
Empirical Risk Minimization (ERM) is a natural learning algorithm, where one simply outputs the hypothesis from $H$ making the fewest mistakes on the training data. This simple algorithm is known to have an optimal error in terms of the VC-dimension of $H$ and the number of samples $n$.
In this work, we revisit agnostic PAC learning and first show that ERM is in fact sub-optimal if we treat the performance of the best hypothesis, denoted $\tau:=\Pr_D[h^\star_D(x) \neq y]$, as a parameter. Concretely we show that ERM, and any other proper learning algorithm, is sub-optimal by a $\sqrt{\ln(1/\tau)}$ factor. We then complement this lower bound with the first learning algorithm achieving an optimal error for nearly the full range of $\tau$. Our new algorithm introduces several novel ideas that we hope may find further applications in learning theory.
Authors
——-
Topics
——
* computational learning theory
* foundations of machine learning
Computing the 3-edge-connected components of directed graphs in linear time
============================================================================================
Abstract
——–
Let $G$ be a directed graph with $m$ edges and $n$ vertices. We present a deterministic linear-time algorithm for computing the $3$-edge-connected components of $G$. This is a significant improvement over the previous best bound by Georgiadis et al. [SODA 2023], which is $\tilde{O}(m\sqrt{m})$ and randomized. Our result is based on a novel characterization of $2$-edge cuts in directed graphs and on a new technique that exploits the concept of divergent spanning trees and $2$-connectivity-light graphs, and requires a careful modification of the minset-poset technique of Gabow [TALG 2016]. As a side result, our new technique yields also an oracle for providing in constant time a minimum edge-cut for any two vertices that are not $3$-edge-connected. The oracle uses space $O(n)$ and can be built in $O(m\log n)$ time: given two query vertices, it determines in constant time whether they are $3$-edge-connected, or provides a $k$-edge cut, with $k\leq 2$, that separates them.
Authors
——-
Austria))
Topics
——
* algorithmic graph theory
* algorithms and data structures
Decoding Quasi-Cyclic Quantum LDPC Codes
=========================================================
Abstract
——–
Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits [PK22a, LZ23, DHLV23, GPT23]. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice.
A construction preceding [PK22a] based on the lifted product of an expander-based classical LDPC code with a repetition code [PK22b] achieved a near-linear distance (of $\Omega(N/\log N)$ where $N$ is the number of codeword qubits), and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects $\Theta(N/\log N)$ adversarial errors. En route, we give such an algorithm for the hypergraph product version these codes, which have weaker $\Theta(\sqrt{N})$ distance (but are simpler). Our decoding algorithms leverage the fact that the codes we consider are \textit{quasi-cyclic}, meaning that they respect a cyclic group symmetry.
Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.
Authors
——-
Topics
——
* algorithmic coding theory
* quantum computing
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit
Squares
================================================================================================
Abstract
——–
We show that packing axis-aligned unit squares into a simple polygon $P$ is NP-hard, even when $P$ is an orthogonal and orthogonally convex polygon with half-integer coordinates.
It has been known since the early 80s that packing unit squares into a polygon with holes is NP-hard~[Fowler, Paterson, Tanimoto, Inf. Process. Lett., 1981], but the version without holes was conjectured to be polynomial-time solvable more than two decades ago~[Baur and Fekete, Algorithmica, 2001].
Our reduction relies on a new way of reducing from \textsc{Planar-3SAT}. Interestingly, our geometric realization of a planar formula is non-planar.
Vertices become rows and edges become columns, with crossings being allowed.
The planarity ensures that all endpoints of rows and columns are incident to the outer face of the resulting drawing.
We can then construct a polygon following the outer face that realizes all the logic of the formula geometrically, without the need of any holes.
This new reduction technique proves to be general enough to also show hardness of two natural covering and partitioning problems, even when the input polygon is simple.
We say that a polygon $Q$ is \emph{small} if $Q$ is contained in a unit square.
We prove that it is NP-hard to find a minimum number of small polygons whose union is $P$ (covering) and to find a minimum number of pairwise interior-disjoint small polygons whose union is $P$ (partitioning), when $P$ is an orthogonal simple polygon with half-integer coordinates.
This is the first partitioning problem known to be NP-hard for polygons without holes, with the usual objective of minimizing the number of pieces.
Authors
——-
Topic
—–
* computational geometry
Semirandom Planted Clique and the Restricted Isometry Property
===============================================================================
Abstract
——–
We give a simple, greedy $O(n^{\omega+0.5})$-time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] following [FK01] that succeeds whenever the size of the planted clique is $k\geq O(\sqrt{n} \log^2 n)$. In the model, the edges touching the vertices in the planted $k$-clique are drawn independently with probability $p=1/2$ while the edges not touching the planted clique are chosen by an adversary in response to the random choices. Our result shows that the computational threshold in the semirandom setting is within a $O(\log^2 n)$ factor of the information-theoretic one [Ste17] thus resolving an open question of Steinhard. This threshold also essentially matches the conjectured computational threshold for the well-studied special case of fully random planted clique.
All previous algorithms [CSV17, MMT20, BKS23] in this model are based on rather sophisticated rounding algorithms for entropy-constrained semidefinite programming relaxations and their sum-of-squares strengthenings and the best known guarantee is a $n^{O(1/\epsilon)}$-time algorithm to list-decode planted cliques of size $k \geq \tilde{O}(n^{1/2+\epsilon})$. In particular, the guarantee trivializes to the brute-force running time of $n^{O(\log n)}$ when the planted clique is of size $O(\sqrt{n} \operatorname{polylog} n)$. Our algorithm achieves an almost optimal guarantee with a surprisingly simple greedy algorithm.
The key conceptual idea underlying our result departs from prior state-of-the-art, which is based on a reduction to certifying bounds on the size of unbalanced bicliques in random graphs that is closely related to certifying the restricted isometry property (RIP) of certain random matrices and is known to be hard in the low-degree polynomial model. We circumvent this limitation by a new approach that relies on the truth of — but not efficient certificates for — RIP of a new class of matrices built from the input graphs.
Authors
——-
Topics
——
* average-case algorithms and complexity
* spectral methods
A Lossless Deamortization for Dynamic Greedy Set Cover
=======================================================================
Abstract
——–
The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most $n$ elements and a fixed collection of $m$ sets, where each element appears in a most $f$ sets and the cost of each set is in $[1/C, 1]$, and the goal is to efficiently maintain an approximate minimum set cover under element updates.
Two algorithms that dynamize the classic \emph{greedy} algorithm are known, providing $O(\log n)$ and $((1+\epsilon)\ln n)$-approximation with {\em amortized} update times $O(f \log n)$ and $O(\frac{f \log n}{\epsilon^5})$, respectively [GKKP (STOC’17); SU (STOC’23)].
The question of whether one can get approximation $O(\log n)$ (or even worse) with low \emph{worst-case} update time has remained open — \emph{only the naive $O(f \cdot n)$ time bound is known}, even for unweighted instances.
In this work we devise the first amortized greedy algorithm that is amenable to an efficient deamortization, and also develop a {\em lossless} deamortization approach suitable for the set cover problem, the combination of which yields
a $((1+\epsilon)\ln n)$-approximation algorithm with a worst-case update time of $O(\frac{f\log n}{\epsilon^2})$.
\emph{Our worst-case time bound — the first to break the naive $O(f \cdot n)$ bound — matches the previous best amortized bound, and actually improves its $\epsilon$-dependence}.
Further, to demonstrate the applicability of our deamortization approach, we employ it, in conjunction with the primal-dual amortized algorithm of [BHN (FOCS’19)],
to obtain a $((1+\epsilon)f)$-approximation algorithm with a worst-case update time of $O(\frac{f\log n}{\epsilon^2})$, improving over the previous best bound of $O(\frac{f \cdot \log^2(Cn)}{\epsilon^3})$ [BHNW (SODA’21)].
Finally, as direct implications of our results for set cover, we (i) achieve the first nontrivial worst-case update time for the \emph{dominating set} problem, and (ii) improve the state-of-the-art worst-case update time for the \emph{vertex cover} problem.
Authors
——-
Topics
——
* algorithmic graph theory
* algorithms and data structures
* approximation algorithms
Ramsey Theorems for Trees and a General ‘Private Learning Implies Online
Learning’ Theorem
================================================================================================
Abstract
——–
This work continues to investigate the link between differentially private (DP) and online learning. Alon, Livni, Malliaris, and Moran (2019) showed that for binary concept classes, DP learnability of a given class implies that it has a finite Littlestone dimension (equivalently, that it is online learnable). Their proof relies on a model theoretic result by Hodges (1997), which demonstrates that any binary concept class with a large Littlestone dimension contains a large subclass of thresholds. In a followup work, Jung, Kim, and Tewari (2020) extended this proof to multiclass PAC learning with a bounded number of labels. Unfortunately, Hodges’s result does not apply in other natural settings such as multiclass PAC learning with an unbounded label space, and PAC learning of partial concept classes.
This naturally raises the question whether DP learnability continues to imply online learnability in more general scenarios: indeed, Alon, Hanneke, Holzman, and Moran (2021) explicitly leave it as an open question in the context of partial concept classes, and the same question is open in the general multiclass setting. In this work, we give a positive answer to these questions showing that for general classification tasks, DP learnability implies online learnability. Our proof reasons directly about Littlestone trees, without relying on thresholds. We achieve this by establishing several Ramsey-type theorems for binary trees concerning colorings of subsets of vertices, that might be of independent interest.
Authors
——-
Topics
——
* combinatorics
* computational learning theory
* foundations of fairness, privacy and databases
* foundations of machine learning
Sampling, counting, and large deviations for triangle-free graphs near the
critical density
================================================================================================
Abstract
——–
We study the following combinatorial counting and sampling problems: can we sample from the Erd\H{o}s-R\'{e}nyi random graph $G(n,p)$ conditioned on triangle-freeness? Can we approximate (either algorithmically or with a formula) the probability that $G(n,p)$ is triangle-free? These are prototypical instances of forbidden substructure problems ubiquitous in combinatorics. The algorithmic questions are instances of approximate sampling and counting for a hypergraph hard-core model.
Estimating the probability that $G(n,p)$ has no triangles is a fundamental question in probabilistic combinatorics and one that has led to the development of many important tools in probabilistic combinatorics. Through the work of several authors, the asymptotics of the logarithm of this probability are known if $p =o( n^{-1/2})$ or if $p =\omega( n^{-1/2})$. The regime $p = \Theta(n^{-1/2})$ is more mysterious, as in this range the typical structural properties of $G(n,p)$ conditioned on triangle-freeness change dramatically.
We give two different efficient sampling algorithms for this problem (and complementary approximate counting algorithms), one that is efficient when $p < c/\sqrt{n}$ and one that is efficient when $p > C/\sqrt{n}$ for constants $c, C>0$. The latter algorithm involves a new approach for dealing with large defects in the setting of sampling from low-temperature spin models.
We then use our algorithmic results to give an asymptotic formula for the logarithm of the probability $G(n,p)$ is triangle-free when $p < c/\sqrt{n}$. This formula allows us to conclude that the problem must undergo a phase transition (in the sense of non-analyticity of a rate function) when $p = \Theta(n^{-1/2})$, justifying the terminology `near-critical’ in the title.
This new algorithmic approach to large deviation problems in random graphs is very different than the known approaches in the subcritical regime $p =o( n^{-1/2})$ (based on the Poisson paradigm) and in the supercritical regime $p =\omega( n^{-1/2})$ (based on regularity lemmas or hypergraph containers); in fact, to the best of our knowledge, no asymptotic formula for the log probability in the regime $p = \Theta(n^{-1/2})$ was even conjectured previously.
Authors
——-
Topics
——
* combinatorics
* Markov chains
* randomized algorithms
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
==================================================================================
Abstract
——–
We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.
Derandomized direct product testing, also known as agreement testing, is the following problem. Let $X$ be a family of $k$-element subsets of $[N]$ and let $\{f_s:s\to\Sigma :s\in X \}$ be an ensemble of local functions, each defined over a subset $s\subset [N]$. Suppose that we run the following so-called agreement test: choose a random pair of sets $s_1,s_2\in X$ that intersect on $\sqrt k$ elements, and accept if $f_{s_1},f_{s_2}$ agree on the elements in $s_1\cap s_2$. We denote the success probability of this test by $Agree(\{f_s\})$. Given that $Agree(\{f_s\})=\varepsilon>0$, is there a global function $G:[N]\to\Sigma$ such that $f_s = G|_s$ for a non-negligible fraction of $s\in X$ ?
We construct a family $X$ of $k$-subsets of $[N]$ such that $|X| = O(N)$ and such that it satisfies the low acceptance agreement theorem. Namely,
$$
Agree (\{f_s\}) > \varepsilon \quad \Longrightarrow \quad \exists G:[N]\to\Sigma,\quad \Pr_s[f_s\overset{0.99}{\approx} G|_s]\geq poly(\varepsilon).
$$
A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family $X$ is just the $k$-faces of the new symplectic HDXs. The later serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers.
Authors
——-
Topics
——
* combinatorics
* high-dimensional algorithms
* pseudorandomness and derandomization
* randomized algorithms
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than
2.
================================================================================================
Abstract
——–
In the classical NP-hard Steiner tree problem we are given an edge-weighted undirected graph and a subset of vertices, called terminals. The task is to compute the cheapest tree that contains all the terminals (and possibly other vertices). The best-known approximation algorithms for this problem involve enumeration of a (polynomial but) very large number of candidate components, therefore they are slow in practice.
A promising ingredient for the design of fast and accurate approximation algorithms for Steiner tree might be the bidirected cut relaxation (BCR): bidirect all the edges, choose an arbitrary terminal as a root, and enforce that each cut that contains some terminal but not the root has one unit of fractional edges leaving it. BCR is known to be integral in the spanning tree case [Edmonds’67], i.e., when all the vertices are terminals. For general instances, however, we only know that the integrality gap of BCR is between 6/5 [Vicari’20] and 2. Improving on the latter upper bound is a well-known open problem in the area. We resolve it by proving an upper bound of 1.9988 on the integrality gap of BCR.
Authors
——-
Topics
——
* approximation algorithms
* combinatorial optimization
Chernoff-Hoeffding and Reverse Hypercontractivity on High Dimensional Expanders
================================================================================================
Abstract
——–
We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDXs). Let $X$ be a $k$-dimensional HDX. We show for any $i \leq k$ and function $f: X(i) \to [0,1]$:
$$
\Pr_{s \in X(k)}\left[\left|\underset{{t \subseteq s}}{\mathbb{E}}[f(t)] – \mu \right| \geq \varepsilon \right] \leq \exp\left(-\varepsilon^2 \frac{k}{i}\right).
$$
Using this fact, we prove that high dimensional expanders are \textit{reverse hypercontractive}, a powerful functional inequality from discrete analysis implying that for any sets $A,B \subset X(k)$, the probability a $\rho$-correlated pair passes between them is at least
$$
\Pr_{s,s’ \sim T_\rho}[s \in A, s’ \in B] \geq \Pr[A]^{O(1)} \Pr[B]^{O(1)}.
$$
Our results hold under weak spectral assumptions on $X$. Namely we prove exponential concentration of measure for any complex below the `Trickling-Down Barrier’ (beyond which concentration may be arbitrarily poor), and optimal concentration for $\sqrt{k}$-skeletons of such complexes. We also show optimal bounds for the top dimension of stronger HDX among other settings.
We leverage our inequalities to prove several new agreement testing theorems on high dimensional expanders, including a new $99\%$-regime test for \textit{subsets}, and a variant of the `Z-test’ achieving \textit{inverse exponential soundness} under the stronger assumption of $\ell_\infty$-expansion. The latter gives rise to the first optimal testers beyond the complete complex and products, and a renewed hope towards the construction of sparse testers and strong soundness PCPs from high dimensional expanders. We also give applications within expansion, analysis, combinatorics, and coding theory, including the first explicit bounded-degree complexes with optimal geometric overlap, near-optimal double samplers, new super-exponential degree lower bound for certain HDX, distance-amplified list-decodable and locally testable codes, a Frankl–Rodl Theorem, and more.
Authors
——-
Topics
——
* analysis of Boolean functions
* combinatorics
* high-dimensional algorithms
* pseudorandomness and derandomization
* randomized algorithms
* spectral methods
Three-edge-coloring projective planar cubic graphs:\\ A generalization of the
Four Color Theorem
================================================================================================
Abstract
——–
We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable.
In other words, the only (non-trivial) snark that can be embedded in the projective plane is the Petersen graph.
This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph.
Here, a replacement of a vertex $v$ in a cubic graph $G$ is the operation that takes a 2-connected planar (cubic) multigraph $H$ containing some vertex $u$ of degree 3, unifying $G-v$ and $H-u$, and connecting the vertices in $N_G[v]$ in $G-v$ with the three neighbors of $u$ in $H-u$ with 3 edges. Any graph obtained in such a way is said to be \emph{Petersen-like}.
This result is a nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability.
Using this result, we obtain the following algorithmic consequence.
\begin{quote}
{\bf Input}: A cubic graph $G$.\\
{\bf Output}: Either a 3-edge-coloring of $G$, an obstruction showing that $G$ is not 3-edge-colorable, or the conclusion that $G$ cannot be embedded in the projective plane (certified by exposing a forbidden minor for the projective plane contained in $G$).\\
{\bf Time complexity}: $O(n^2)$, where $n=|V(G)|$.
\end{quote}
An unexpected consequence of this result is a coloring-flow duality statement for the projective plane: A cubic graph embedded in the projective plane is 3-edge-colorable if and only if its dual multigraph is 5-vertex-colorable. Moreover, we show that a 2-edge connected graph embedded in the projective plane admits a nowhere-zero 4-flow unless it is Peteren-like (in which case it does not admit nowhere-zero 4-flows). This proves a strengthening of the Tutte 4-flow conjecture for graphs on the projective plane.
As mentioned above, some of our proofs require extensive computer verification. The necessary source codes, together with the input and output files, are
available on Google Drive\footnote{\url{https://drive.google.com/file/d/1Y-xa6rmkLSI94_f7h0GPRecXbvE4oGfy/view}. Refer to “README.md” file in each directory for instructions on how to run each program.}.
Authors
——-
2. Kenichi Kawarabayashi <
[email protected]> (National Institute of Informatics and The
University of Tokyo)
Topics
——
* algorithmic graph theory
* combinatorics
Interactive Proofs for General Distribution Properties
=======================================================================
Abstract
——–
Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob’s claims using fewer resources (say in terms of samples and computation) than would be needed to run the analysis herself?
We construct an interactive proof system for any distribution property that can be decided by bounded-depth circuits. Taking $N$ to be an upper bound on the distribution’s support size, and $D$ a bound on the depth of a uniform polynomial-size Boolean circuit that gets a complete description of the distribution and decides the property, the verifier’s sample complexity, running time, and the communication complexity are all sublinear in the support size $N$: they are bounded by $\tilde{O}( N^{1-\alpha} + D)$ for a constant $\alpha > 0$. The honest prover runs in $\text{poly}(N)$ time and has quasi-linear sample complexity. We also show similar results for any distribution property that can be decided by a bounded-space Turing machine (that gets as input a complete description of the distribution). We remark that even for simple properties, deciding the property without a prover requires quasi-linear sample complexity and running time. Prior work [Herman and Rothblum, FOCS 2023] demonstrated sublinear interactive proof systems, but only for the much more restricted class of \textit{label-invariant} distribution properties.
Authors
——-
Topics
——
* computational complexity
* cryptography
* sublinear algorithms
Tight Bounds for the Zig-Zag Product
=====================================================
Abstract
——–
The Zig-Zag product of two graphs $Z = G \circ H$, was introduced by Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound which is used throughout, states that the spectral expansion of the Zig-Zag product can be bounded roughly by the sum of the spectral expansions of the individual graphs, $\omega_Z \le \omega_H + \omega_G$.
In this work we derive, for every vertex-transitive $c$-regular graph $H$ on $d$ vertices, a tight bound for $\omega_Z$ by taking into account the \emph{entire} spectrum of $H$. Our work reveals that the bound is precisely the minimum value of the function
$$
\frac{x}{c^2}\cdot\sqrt{1-\frac{d\cdot h(x)}{x\cdot h'(x)}}
$$
within the domain $(c^2,\infty)$, where $h(x)$ is the characteristic polynomial of $H^2$. As a consequence, we deduce that Zig-Zag products are indeed intrinsically quadratic away from being Ramanujan. We further prove tight bounds for the spectral expansion of the replacement product. Our lower bounds are based on deep results from analytic combinatorics, and we make use of finite free probability to prove their tightness. In a wider scope, our work uncovers intriguing links between these fields and the well-studied graph operators.
Authors
——-
Topics
——
* combinatorics
* pseudorandomness and derandomization
* spectral methods
Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its
Applications
================================================================================================
Abstract
——–
The coding theorem for Kolmogorov complexity states that any string sampled from a computable distribution has a description length close to its information content. A coding theorem for resource-bounded Kolmogorov complexity is the key to obtaining fundamental results in average-case complexity, yet whether any samplable distribution admits a coding theorem for randomized time-bounded Kolmogorov complexity ($\mathsf{rK}^\mathsf{poly}$) is open and a common bottleneck in the recent literature of meta-complexity. Previous works bypassed this issue by considering probabilistic Kolmogorov complexity ($\mathsf{pK}^\mathsf{poly}$), in which public random bits are assumed to be available.
In this paper, we present an efficient coding theorem for randomized Kolmogorov complexity under the non-existence of one-way functions, thereby removing the common bottleneck. This enables us to prove $\mathsf{rK}^\mathsf{poly}$ counterparts of virtually all the average-case results that were proved only for $\mathsf{pK}^\mathsf{poly}$, and enables the resolution of the following concrete open problems.
1. The existence of a one-way function is characterized by the failure of average-case symmetry of information for randomized time-bounded Kolmogorov complexity, as well as a conditional coding theorem for randomized time-bounded Kolmogorov complexity. This resolves open problems of Hirahara, Ilango, Lu, Nanashima, and Oliveira (STOC’24) and Haitner, Mazor, and Silbak (ITCS’23).
2. Hirahara, Kabanets, Lu, and Oliveira (2024) showed that randomized time-bounded Kolmogorov complexity admits search-to-decision reductions in the errorless average-case setting over any samplable distribution, and left open whether a similar result holds in the error-prone setting. We resolve this question affirmatively, and as a consequence, characterize the existence of a one-way function by the average-case hardness of computing $\mathsf{rK}^\mathsf{poly}$ with respect to an arbitrary samplable distribution, which is an $\mathsf{rK}^\mathsf{poly}$ analogue of the $\mathsf{pK}^\mathsf{poly}$ characterization of Liu and Pass (CRYPTO’23).
The key technical lemma is that any distribution whose next bits are efficiently predictable admits an efficient encoding and decoding scheme, which could be of independent interest to data compression.
Authors
——-
Topics
——
* average-case algorithms and complexity
* computational complexity
* cryptography
* pseudorandomness and derandomization
Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset
Bounds
================================================================================================
Abstract
——–
Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as $k$-means. Given a point set $P$, a coreset $\Omega$ is a small, weighted summary that preserves the cost of all candidate solutions $S$ up to a $(1\pm \varepsilon)$ factor. For $k$-means in $d$-dimensional Euclidean space the cost for solution $S$ is $\sum_{p\in P}\min_{s\in S}\|p-s\|^2$.
A very popular method for coreset construction, both in theory and practice, is Sensitivity Sampling, where
points are sampled in proportion to their importance.
We show that Sensitivity Sampling yields optimal coresets of size $\tilde{O}(k/\varepsilon^2\min(\sqrt{k},\varepsilon^{-2}))$ for worst-case instances.
Uniquely among all known coreset algorithms, for well-clusterable data sets with $\Omega(1)$ cost stability,
Sensitivity Sampling gives coresets
of size $\tilde{O}(k/\varepsilon^2)$, improving over the worst-case lower bound.
Notably, Sensitivity Sampling does not have to know the cost stability in order to exploit it: It is appropriately sensitive to the clusterability of the data set while being oblivious to it.
We also show that any coreset for stable instances consisting of only input points must have size $\Omega(k/\varepsilon^2)$. Our results
for Sensitivity Sampling also extend to the $k$-median problem, and more general metric spaces.
Authors
——-
Topics
——
* foundations of machine learning
* high-dimensional algorithms
* randomized algorithms
* streaming algorithms
The Online Submodular Assignment Problem
=========================================================
Abstract
——–
Online resource allocation is a rich and varied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp,
Vazirani, and Vazirani \cite{KVV90}. Since then, many variants have been studied, including AdWords, the generalized assignment problem (GAP), and online submodular welfare maximization.
In this paper, we introduce a generalization of GAP which we call the submodular assignment problem (SAP). This generalization captures many online assignment problems, including all classical online bipartite matching problems as well as broader online combinatorial optimization problems such as online arboricity, flow scheduling, and laminar restricted allocations. We present a fractional algorithm for online SAP that is $(1-\frac{1}{e})$-competitive.
Additionally, we study several integral special cases of the problem. In particular, we provide a $(1-\frac{1}{e}-\epsilon)$-competitive integral algorithm under a small-bids assumption, and a $(1-\frac{1}{e})$-competitive integral algorithm for online submodular welfare maximization where the utility functions are given by rank functions of matroids.
The key new ingredient for our results is the construction and structural analysis of a “water level” vector for polymatroids, which allows us to generalize the classic water-filling paradigm used in online matching problems. This construction reveals connections to submodular utility allocation markets and principal partition sequences of matroids.
Authors
——-
Topics
——
* approximation algorithms
* combinatorial optimization
* online algorithms
Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
========================================================================================
Abstract
——–
We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) $\mathcal{C} \colon \{0,1\}^k \rightarrow \{0,1\}^n$. Specifically, we prove:
\begin{enumerate}[(1)]
\item If $\mathcal{C}$ is a linear \emph{design} 3-LCC, then $n \geq 2^{(1 – o(1))\sqrt{k} }$. A design 3-LCC has the additional property that the correcting sets for every codeword bit form a perfect matching, and every pair of codeword bits is queried an equal number of times across all matchings. Our bound is tight up to a factor $\sqrt{8}$ in the exponent of $2$, as the best construction of binary $3$-LCCs (obtained by taking Reed–Muller codes on $\F_4$ and applying a natural projection map) is a design $3$-LCC with $n \leq 2^{\sqrt{8 k}}$. Up to a factor of $8$, this resolves the Hamada conjecture on the maximum $\F_2$-codimension of a $4$-design.
\item If $\mathcal{C}$ is a smooth, non-linear, adaptive $3$-LCC with perfect completeness, then, $n \geq 2^{\Omega(k^{1/5})}$.
\item If $\mathcal{C}$ is a smooth, non-linear, adaptive $3$-LCC with completeness $1 – \eps$, then $n \geq \tilde{\Omega}(k^{\frac{1}{2\eps}})$.
In particular, when $\epsilon$ is a small constant, this implies a lower bound for general non-linear LCCs that beats the prior best $n \geq \tilde{\Omega}(k^3)$ lower bound of Alrabiah, Guruswami, Kothari and Manohar (2023) by a polynomial factor.
Authors
——-
Topics
——
* algorithmic coding theory
* combinatorics
* spectral methods
Efficient Approximation of Hypertree Width
===========================================================
Abstract
——–
We give two new approximation algorithms to compute the {\em fractional hypertree width} of an input hypergraph. The first algorithm takes as input $n$-vertex $m$-edge hypergraph $H$ of fractional hypertree width at most $\omega$, runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $\cO(\omega \log n \log \omega)$. In particular it is an $\cO(\log n \log \omega)$-approximation algorithm. As an immediate corollary this yields polynomial time $\cO(\log^2 n \log \omega)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $\omega$ is considered a constant. For hypergraphs with the {\em bounded intersection property} (i.e. hypergraphs where every pair of hyperedges have at most $\eta$ vertices in common) the algorithm outputs a hypertree decomposition with fractional hypertree width $\cO(\eta \omega^2 \log \omega)$ and generalized hypertree width $\cO(\eta \omega^2 \log \omega (\log \eta + \log \omega))$. This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width $\cO(\omega^2(\omega + \eta))$, but uses time (at least) exponential in $\eta$ and $\omega$.
The second algorithm runs in time $n^{\omega}m^{\cO(1)}$ and produces a tree decomposition of $H$ of fractional hypertree width $\cO(\omega \log^2 \omega)$. This significantly improves over the $(n+m)^{\cO(\omega^3)}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hypertree width $\cO(\omega^3)$, both in terms of running time and the approximation ratio.
Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger’s Theorem for clique separators in graphs: For every graph $G$, vertex sets $A$ and $B$, family ${\cal F}$ of cliques in $G$, and positive rational $f$, either there exists a sub-family of $\cO(f \cdot \log^2 n)$ cliques in ${\cal F}$ whose union separates $A$ from $B$, or there exist $f \cdot \log |{\cal F}|$ paths from $A$ to $B$ such that no clique in ${\cal F}$ intersects more than $\log |{\cal F}|$ paths.
Authors
——-
1. Vaishali Surianarayanan <
[email protected]> (University of California Santa Barbara)
2. Daniel Lokshtanov <
[email protected]> (University of California Santa Barbara, USA)
Topics
——
* algorithmic graph theory
* approximation algorithms
* combinatorics
* foundations of fairness, privacy and databases
* parametrized algorithms
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial
Notions of Pseudorandomness
================================================================================================
Abstract
——–
This paper revisits the study of two classical technical tools in theoretical computer science: Yao’s transformation of distinguishers to next-bit predictors (FOCS 1982), and the “reconstruction paradigm” in pseudorandomness. Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and Tell (STOC 2024) showed that both of these tools can be \emph{derandomized} in the specific context of \emph{read-once branching programs} ($\mathsf{ROBP}$s), but left open the question of derandomizing them in more general settings.
Our main contributions give appealing evidence that derandomization of the two tools is possible in general settings, show surprisingly strong consequences of such derandomization, and reveal several new settings where such derandomization is unconditionally possible (and has useful consequences) for algorithms stronger than $\mathsf{ROBP}$s. Specifically:
* We show that derandomizing these tools is equivalent to general derandomization. Specifically, we show that derandomizing Yao’s transformation is equivalent to $\mathsf{prBPP}=\mathsf{prP}$, and that derandomized reconstruction procedures (in a more general sense that we introduce) is equivalent to $\mathsf{prBPP}=\mathsf{prZPP}$. These statements hold even when scaled down to weak circuit classes and to algorithms that run in super-polynomial time.
* Our main technical contributions are unconditional constructions of derandomized versions of Yao’s transformation (or reductions of this task to other problems) for classes and for algorithms beyond $\mathsf{ROBP}$s. Consequently, we deduce new results: A significant relaxation of the hypotheses required to **derandomize the isolation lemma** for logspace algorithms and deduce that $\mathsf{NL}=\mathsf{UL}$; and proofs that **derandomization necessitates targeted PRGs** in catalytic logspace (unconditionally) and in logspace (conditionally).
In addition, we introduce a natural subclass of $\mathsf{prZPP}$ that has been implicitly studied in recent works (Korten FOCS 2021, CCC 2022): The class of problems reducible to a problem called “Lossy Code”. We provide a structural characterization for this class in terms of derandomized reconstruction procedures, and show that this characterization is robust to natural variations.
Lastly, we present alternative proofs of several classical results in the theory of pseudorandomness, relying on the notion of deterministically transforming distinguishers to predictors as the main technical tool.
Authors
——-
Topics
——
* computational complexity
* pseudorandomness and derandomization
Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
======================================================================
Abstract
——–
We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\{1,\dots,U\}$ in $n^{2+o(1)}\log U$ time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework; we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy.
Even in unit-capacity graphs, this breaks the long-standing $O(m\cdot\min\{\sqrt{m},n^{2/3}\})$ time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has $m=\omega(n^{4/3})$ edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022).
Our running time also matches the $n^{2+o(1)}$ time bound of the concurrent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.
Authors
——-
2. Joakim Blikstad <
[email protected]> (KTH Royal Institute of Technology & Max Planck Institute
for Informatics)
Topics
——
* algorithmic graph theory
* algorithms and data structures
* combinatorial optimization
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
=====================================================================================
Abstract
——–
We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from $\{-\Delta,\ldots,\Delta\}$ or more generally $m$-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by $\Delta$ and $m$ for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in $\{0,1\}$, or arbitrary $\Delta$ and $m=1$. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection.
Authors
——-
3. Karol Wegrzycki <
[email protected]> (Saarland University and Max Planck Institute for
Informatics)
Topics
——
* algorithms and data structures
* combinatorial optimization
* parametrized algorithms
The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds
=======================================================================================
Abstract
——–
A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive non-uniform circuit lower bounds. We show how the **non-existence** of nontrivial circuit-analysis algorithms can also imply non-uniform circuit lower bounds. Our connections yield new win-win circuit lower bounds, and suggests a potential approach to refuting the Orthgonal Vectors Conjecture in the $O(\log n)$-dimensional case, which would be sufficient for refuting the Strong Exponential Time Hypothesis (SETH). For example, we show that at least one of the following lower bounds holds:
$\bullet$ There is an $\varepsilon > 0$ such that for infinitely many $n$, read-once 2-DNFs on $n$ variables cannot be simulated by \emph{non-uniform} $2^{\varepsilon n}$-size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class $\E^{\NP}$ does not have polynomial-size depth-two exact threshold circuits, so such a lower bound would be a significant advance in low-depth circuit complexity. In fact, a stronger lower bound holds in this case: the $2^n \times 2^n$ Disjointness Matrix (well-studied in communication complexity) cannot be expressed by a linear combination of $2^{o(n)}$ structured matrices that we call “equality matrices”.
$\bullet$ For every $c \geq 1$ and every $\varepsilon > 0$, Orthogonal Vectors on $n$ vectors in $c \log n$ dimensions can be solved in $n^{1+\varepsilon}$ **uniform** deterministic time. This case would provide a strong refutation of the Orthogonal Vectors conjecture, and of SETH: for example, CNF-SAT on $n$ variables and $O(n)$ clauses could be solved in $2^{n/2 + o(n)}$ time. Moreover, this case would imply non-uniform circuit lower bounds for $E^{NP}$, against Valiant series-parallel circuits.
Inspired by this connection, we give evidence from practical SAT/SMT solvers that the first item (in particular, the Disjointness lower bound) may be false in its full generality. In particular, we give a systematic approach to solving Orthogonal Vectors via constant-sized decompositions of the Disjointness Matrix, which already yields interesting new OV algorithms. For example, using a linear combination of $6$ equality matrices that express $2^6 \times 2^6$ Disjointness, we derive an $\tilde{O}(n \cdot 6^{d/6}) \leq \tilde{O}(n \cdot 1.35^d)$ time and $n \cdot poly(\log n, d)$ space algorithm for Orthogonal Vectors on $n$ vectors in $d$ dimensions. We show similar results for counting orthogonal vectors.
Author
——
Topics
——
* algorithms and data structures
* circuit complexity
* computational complexity
* high-dimensional algorithms
* parametrized algorithms
Computational Dynamical Systems
================================================
Abstract
——–
We study the computational complexity theory of smooth, finite-dimensional dynamical systems. Building off of previous work, we give definitions for what it means for a smooth dynamical system to simulate a Turing machine. We then show that `chaotic’ dynamical systems (more precisely, Axiom A systems) and `integrable’ dynamical systems cannot robustly simulate universal Turing machines, although such machines can be robustly simulated by other kinds of dynamical systems. Subsequently, we show that any Turing machine that can be encoded into a structurally stable one-dimensional dynamical system must have a decidable halting problem, and moreover an explicit time complexity bound in instances where it does halt. We also provide an inexplicit time complexity bound for higher-dimensional Anosov systems. Next we turn to forced dynamical systems, and study how they can implement deterministic finite state machines and pushdown automata. We develop a partial classification of all finite state machines that can be instantiated by forced diffeomorphisms of the interval, and discuss variations for natural constraints on the type of forcing. More broadly, our work elucidates what it means for one `machine’ to simulate another, and emphasizes the necessity of defining low-complexity `encoders’ and `decoders’ to translate between the dynamics of the simulation and the system being simulated. We highlight how the notion of a computational dynamical system leads to questions at the intersection of computational complexity theory, dynamical systems theory, real algebraic geometry, and combinatorics.
Authors
——-
Topics
——
* algebraic computation
* computational complexity
* Markov chains
On the Complexity of Avoiding Heavy Elements
=============================================================
Abstract
——–
We introduce and study the following natural total search problem, which we call the heavy element avoidance (Heavy Avoid) problem: for a distribution on N bits specified by a Boolean circuit sampling it, and for some parameter δ(N) ≥ 1/poly(N) fixed in advance, output an N-bit string that has probability less than δ(N). We show that the complexity of Heavy Avoid is closely tied to frontier open questions in complexity theory about uniform randomized lower bounds and derandomization. Among other results, we show:
1. For a wide range of circuit classes 𝒞, including $\mathsf{ACC}^0$, $\mathsf{TC}^0$, $\mathsf{NC}^1$, and general Boolean circuits, EXP does not have uniform randomized 𝒞-circuits if and only if Heavy Avoid for uniform implicit 𝒞-samplers has efficient deterministic algorithms infinitely often. This gives the first algorithmic characterization of lower bounds for EXP against uniform randomized low-depth circuits. We show similar algorithmic characterizations for lower bounds in PSPACE, NP, and EXP$^\mathsf{NP}$.
2. Unconditionally, there are polynomial-time pseudodeterministic algorithms that work infinitely often for several variants of Heavy Avoid, such as for uniform samplers of small randomness complexity. In contrast, the existence of a similar algorithm that solves Heavy Avoid for arbitrary polynomial-time samplers would solve a long-standing problem about hierarchies for probabilistic time.
3. If there is a time and depth efficient deterministic algorithm for Heavy Avoid, then BPP = P. Without the depth-efficiency requirement in the assumption, we still obtain a non-trivial form of infinitely-often deterministic simulation of randomized algorithms. These results are shown using non-black-box reductions, and we argue that the use of non-black-box reductions is essential here.
Authors
——-
Topics
——
* circuit complexity
* computational complexity
* pseudorandomness and derandomization
Trading Determinism for Noncommutativity in Edmonds’ Problem
=============================================================================
Abstract
——–
Let $X=X_1 \sqcup X_2 \sqcup \ldots \sqcup X_k$ be a partitioned set of variables such that the variables in each part $X_i$ are noncommuting but for any $i\neq j$, the variables $x \in X_i$ commute with the variables $x’ \in X_j$. Given as input a square matrix $T$ whose entries are linear forms over $\mathbb{Q} \langle{X}\rangle$, we consider the problem of checking if $T$ is invertible or not over the universal skew field of fractions of the partially commutative polynomial ring $\mathbb{Q}\langle{X}\rangle$ (Klep, Vinnikov, Volcic’ 20). In this paper, we design a deterministic polynomial-time algorithm for this problem for constant $k$. The special case $k=1$ is the noncommutative Edmonds’ problem (NSING) which has a deterministic polynomial-time algorithm by recent results (Garg-Gurvits-Oliveira-Wigderson’16, Ivanyos-Qiao-Subrahmanyam’18, Hamada-Hirai’21).
En-route, we obtain the first deterministic polynomial-time algorithm for the equivalence testing problem of $k$-tape \emph{weighted} automata (for constant $k$) resolving a long-standing open problem (Harju and Juhani Karhum\”{a}ki’ 91, Worrell’13). Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set $X$ is zero or not (Worrell’13). Decidability of this problem was established by Harju and Karhum\”{a}ki (1991). Prior to this work, a \emph{randomized} polynomial-time algorithm for this problem was given by Worrell (2013) and, subsequently, a deterministic quasipolynomial-time algorithm was also developed (Arvind et al. ’21).
Authors
——-
1. V. Arvind <
[email protected]> (Institute of Mathematical Sciences (HBNI), and CMI)
Topics
——
* algebraic computation
* pseudorandomness and derandomization
Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis
================================================================================
Abstract
——–
Non-Gaussian Component Analysis (NGCA) is the statistical task of
finding a non-Gaussian direction in a high-dimensional dataset.
Specifically, given i.i.d.\ samples from a distribution $P^A_{v}$
on $\mathbb{R}^n$ that behaves like a known distribution $A$ in a hidden direction $v$
and like a standard Gaussian in the orthogonal complement, the goal is to
approximate the hidden direction. The standard formulation posits that
the first $k-1$ moments of $A$ match those of the standard Gaussian
and the $k$-th moment differs. Under mild assumptions,
this problem has sample complexity $O(n)$. On the other hand, all known
efficient algorithms require $\Omega(n^{k/2})$ samples.
Prior work developed sharp Statistical Query
and low-degree testing lower bounds
suggesting an information-computation tradeoff for this problem.
Here we study the complexity of NGCA in the Sum-of-Squares (SoS) framework.
Our main contribution is the first super-constant degree
SoS lower bound for NGCA.
Specifically, we show that if the non-Gaussian distribution $A$ matches
the first $(k-1)$ moments of $\mathcal N(0, 1)$ and satisfies other mild
conditions, then with fewer than $n^{\frac{(1 – \epsilon)k}{2}}$ many samples from the normal distribution, with high probability,
degree $(\log n)^{{1\over 4}-o_n(1)}$ SoS fails to refute the existence of such a direction $v$.
Our result significantly strengthens prior work by establishing a
super-polynomial information-computation tradeoff
against a broader family of algorithms. As a corollary, we obtain
SoS lower bounds for several problems in robust statistics and learning of mixture models.
Our SoS lower bound proof introduces a novel technique,
that we believe may be of broad interest,
and a number of refinements over existing methods.
As in previous work, we use the framework of [Barak et al. FOCS 2016],
where we express the moment matrix $M$ as a sum of graph matrices,
find a factorization $M\approx LQL^T$ using minimum vertex separators,
and show that with high probability $Q$ is positive semidefinite (PSD) while the errors are small.
Our technical innovations involve the following:
First, instead of the minimum weight separator (used in prior work),
we crucially make use of the minimum square separator.
Second, proving that $Q$ is PSD poses significant challenges
for an intrinsic reason. Specifically, in all prior work,
the major part of $Q$ was always a constant term,
i.e., a matrix whose entries are constant functions of the input.
In our setting, even after removing a small error term,
$Q$ remains a nontrivial linear combination of non-constant, equally dominating terms.
To address this difficulty, we develop a novel algebraic method
that we believe is of more general interest.
Specifically, we %first
model the multiplications between the “important” graph matrices
by an $\mathbb R$-algebra, construct a representation of this algebra, and use this representation to analyze $Q$. By using this approach, we show that the PSDness of $Q$ boils down
to the multiplicative identities of Hermite polynomials.
Authors
——-
Topics
——
* average-case algorithms and complexity
* foundations of machine learning
$\Pi_2^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction
Problem
================================================================================================
Abstract
——–
The Quantified Constraint Satisfaction Problem is the problem of evaluating a sentence with both quantifiers, over relations from some constraint language, with conjunction as the only connective. We show that for any constraint language on a finite domain the Quantified Constraint Satisfaction Problem is either in $\Pi_{2}^{P}$, or PSpace-complete. Additionally, we build a constraint language on a 6-element domain such that the Quantified Constraint Satisfaction Problem over this language is $\Pi_{2}^{P}$-complete.
Author
——
Topic
—–
* computational complexity
Near-Optimal $(1+\epsilon)$-Approximate Fully-Dynamic All-Pairs Shortest Paths
in Planar Graphs
================================================================================================
Abstract
——–
We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an $n$-vertex planar graph $G=(V,E)$ undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a $(1+\epsilon)$-approximate dynamic algorithm that supports edge updates and distance queries in $n^{o(1)}$ time, for any $1/\text{poly}(\log n) < \epsilon < 1$. Our result is a significant improvement over the best previously known bound of $\tilde{O}(\sqrt{n})$ on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a $\Omega(\sqrt{n})$ conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chan, Krauthgamer, Tan, STOC ’22].
Authors
——-
Topics
——
* algorithmic graph theory
* algorithms and data structures
* online algorithms
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
=====================================================================================
Abstract
——–
This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ distance. Our goals are twofold: to further understand the relationship between classical and directed isoperimetry, and to give a monotonicity tester with sublinear query complexity in this setting.
Our main results are 1) an $L^2$ monotonicity tester for $M$-Lipschitz functions with query complexity $\widetilde O(\sqrt{d} M^2 / \epsilon^2)$ and, behind this result, 2) the directed Poincaré inequality $\mathsf{dist}^{\mathsf{mono}}_2(f)^2 \le C\, \mathbb{E}[|\nabla^- f|^2]$, where the “directed gradient” operator $\nabla^-$ measures the local violations of monotonicity of $f$.
To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function $f$ into a monotone function $f^*$ over time and enjoys many desirable analytic properties. We obtain the directed Poincaré inequality by combining convergence aspects of this PDE with the theory of optimal transport. Crucially for our conceptual motivation, this proof is in complete analogy with the mathematical physics perspective on the classical Poincaré inequality, namely as characterizing the convergence of the standard heat equation toward equilibrium.
Author
——
Topics
——
* high-dimensional algorithms
* randomized algorithms
* sublinear algorithms
On Robustness to k-wise Independence of Optimal Bayesian Mechanisms
====================================================================================
Abstract
——–
This paper reexamines the classic problem of revenue maximization in single-item auctions with $n$ buyers under the lens of the robust optimization framework. The celebrated Myerson’s mechanism is the format that maximizes the seller’s revenue under the prior distribution, which is mutually independent across all $n$ buyers. As argued in a recent line of work (Caragiannis et al. 22), (Dughmi et al. 24), mutual independence is a strong assumption that is extremely hard to verify statistically, thus it is important to relax the assumption.
While optimal under mutual independent prior, we find that Myerson’s mechanism may lose almost all of its revenue when the independence assumption is relaxed to pairwise independence, i.e., Myerson’s mechanism is not pairwise-robust.
The mechanism regains robustness when the prior is assumed to be 3-wise independent. In contrast, we show that second-price auctions with anonymous reserve, including optimal auctions under i.i.d. priors, lose at most a constant fraction of their revenues on any regular pairwise independent prior. Our findings draw a comprehensive picture of robustness to $k$-wise independence in single-item auction settings.
Authors
——-
Topics
——
* algorithmic game theory
* economics and computation
Expansion of high-dimensional cubical complexes with application to quantum
locally testable codes
================================================================================================
Abstract
——–
We introduce a high-dimensional cubical complex, for any dimension t ∈ N, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case t = 2), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively.
We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes h_1, … , h_t as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex.
For t = 4 our construction gives a new family of “almost-good” quantum LTCs — with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant- size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.
Authors
——-
Topics
——
* combinatorics
* quantum computing
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved
MIS
================================================================================================
Abstract
——–
This paper improves and in two cases nearly settles, up to logarithmically lower order factors, the deterministic complexity of some of the most central problems in distributed graph algorithms, which have been studied for over three decades:
– \textbf{Near-Optimal Network Decomposition}: We present a deterministic distributed algorithm that computes a network decomposition in $\tilde{O}(\log^2 n)$ rounds, with ideal parameters: $O(\log n)$ diameter and $O(\log n)$ colors. This round complexity is near-optimal in the following sense: even given an ideal network decomposition, using it (in the standard way) requires round complexity equal to the product of diameter and number of colors, and that is known to be $\tilde{\Omega}(\log^2 n)$. We find this near-optimality remarkable, considering the rarity of optimal deterministic distributed algorithms and that for network decomposition, even the first polylogarithmic round algorithm was achieved only recently, by Rozhon and Ghaffari [STOC 2020], after three decades of work.
– \textbf{Near-Optimal Ruling Set}: We present a deterministic distributed algorithm that computes an $O(\log\log n)$ ruling set—i.e., an independent set such that each node is within its $O(\log\log n)$ distance—in $\tilde{O}(\log n)$ rounds. This is an exponential improvement on the $O(\log n)$ ruling set of Awerbuch, Goldberg, Luby, and Plotkin [FOCS’89], while almost matching their $O(\log n)$ round complexity. Our result’s round complexity nearly matches the $\tilde{\Omega}(\log n)$ lower bound of Balliu, Brandt, Kuhn, and Olivetti [STOC 2022] that holds for any $poly(\log\log n)$ ruling set.
– \textbf{Improved Maximal Independent Set (MIS)}: We present a deterministic distributed algorithm for computing an MIS in $\tilde{O}(\log^{5/3} n)$ rounds. This improves on the $\tilde{O}(\log^2 n)$ complexity achieved by Ghaffari and Grunau [STOC 2023] and breaks the log-squared barrier necessary for any method based on network decomposition. By known reductions, the $\tilde{O}(\log^{5/3} n)$ round complexity also applies to deterministic algorithms for maximal matching, $\Delta+1$ vertex coloring, and $(2\Delta-1)$ edge coloring. Also, via the shattering technique, the improvement spreads also to randomized complexities of these problems, e.g., the new state-of-the-art randomized complexity of $\Delta+1$ vertex coloring is now $\tilde{O}((\log\log n)^{5/3})$.
Authors
——-
Topic
—–
* parallel and distributed algorithms
A computational test of quantum contextuality, and even simpler proofs of
quantumness
================================================================================================
Abstract
——–
Bell non-locality is a fundamental feature of quantum mechanics whereby measurements performed on “spatially separated” quantum systems can exhibit correlations that cannot be understood as revealing predetermined values. This is a special case of the more general phenomenon of “quantum contextuality”, which says that such correlations can occur even when the measurements are not necessarily on separate quantum systems, but are merely “compatible” (i.e. commuting). Crucially, while any non-local “game” yields an experiment that demonstrates quantum advantage by leveraging the “spatial separation” of two or more devices (and in fact several such demonstrations have been conducted successfully in recent years), the same is not true for quantum contextuality: finding the contextuality analogue of such an experiment is one of the central open questions in the foundations of quantum mechanics.
In this work, we show that an arbitrary contextuality game can be compiled into an operational “test of contextuality” involving a single quantum device, by only making the assumption that the device is computationally bounded. Our work is inspired by the recent work of Kalai et al. (STOC ’23) that converts any non-local game into a classical test of quantum advantage with a single device. The central idea in their work is to use cryptography to enforce spatial separation within subsystems of a single quantum device. Our work can be seen as using cryptography to enforce “temporal separation”, i.e. to restrict communication between sequential measurements.
Beyond contextuality, we employ our ideas to design a “proof of quantumness” that, to the best of our knowledge, is arguably even simpler than the ones proposed in the literature so far.
Authors
——-
Maryland)
4. Kishor Bharti <
[email protected]> (A*STAR Quantum Innovation Centre (Q.InC), Institute
of High Performance Computing (IHPC), Agency for Science, Technology and Research (A*STAR),
Singapore. Centre for Quantum Engineering, Research and Education, TCG CREST, India.)
Topics
——
* cryptography
* quantum computing
On Pigeonhole Principles and Ramsey in TFNP
============================================================
Abstract
——–
We show that the TFNP problem Ramsey is not black-box reducible to Pigeon, refuting
a conjecture of Goldberg and Papadimitriou in the black-box setting. We prove this by giving
reductions to Ramsey from a new family of TFNP problems that correspond to generalized
versions of the pigeonhole principle. Formally, we define t-PPP as the class of total NP-search
problems reducible to finding a t-collision in a mapping from (t − 1)N + 1 pigeons to N holes.
We show that these classes form a hierarchy as t increases, and also give a natural condition on
the parameters t[1], t[2] which captures exactly whether two classes t[1]-PPP and t[2]-PPP collapse in the black-box setting. Finally, we prove other inclusion and separation results between the generalized Pigeon problems and other previously studied TFNP subclasses, such as PLS, PPA, and PLC
Authors
——-
Topics
——
* algorithms and data structures
* computational complexity
New investigations into noncommutative CSPs
============================================================
Abstract
——–
Much is known about approximability for $\textsf{NP}$-hard problems. This picture is particularly clear for constraint satisfaction problems (CSPs): For example, Max-Cut can be approximated up to $0.878$ in polynomial-time but any ratio beyond that is $\textsf{NP}$-hard assuming the Unique Games Conjecture. Now, with the $\textsf{MIP}^*=\textsf{RE}$ theorem, we know that most interesting \emph{noncommutative CSPs}, which are \emph{higher-dimensional operator} variants of classical CSPs, are $\textsf{RE}$-hard. However, very little is known about approximability of these CSPs.
The simplest noncommutative CSP that is undecidable is the noncommutative Max-$3$-Cut, making it an ideal testbed for developing an approximation theory for noncommutative CSPs (perhaps similar to the role Max-Cut played in the classical theory). We give a polynomial-time $0.864$-approximation algorithm for this CSP.
Our main technical contribution is a general framework which can be applied to approximations for a broad class of both classical and noncommutative CSPs. The innovations in this work are the introduction of the three concepts of \emph{approximate isometry}, \emph{relative distribution}, and \emph{generalized anticommutation}, each of which may be of independent interest. The analysis of our algorithms relies on tools from free probability and representation theory.
We explore at length the close ties this line of investigation has with Quantum Max-Cut, nonlocal games, Grothendieck inequalities, and Unique Games. We propose an expansive list of open problems in the hope of further developing this theory.
Authors
——-
Topics
——
* approximation algorithms
* quantum computing
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff
for Feasibility Problems
================================================================================================
Abstract
——–
In this paper we provide oracle complexity lower bounds for finding a point in a given set using a memory-constrained algorithm that has access to a separation oracle. We assume that the set is contained within the unit $d$-dimensional ball and contains a ball of known radius $\epsilon>0$. This setup is commonly referred to as the \emph{feasibility problem}. We show that to solve feasibility problems with accuracy $\epsilon \geq e^{-d^{o(1)}}$, any deterministic algorithm either uses $d^{1+\delta}$ bits of memory or must make at least $1/(d\epsilon^{2\frac{1-\delta}{1+1.01 \delta}-o(1)})$ oracle queries, for any $\delta\in[0,1]$. Additionally, we show that randomized algorithms either use $d^{1+\delta}$ memory or make at least $1/(d \epsilon^{2(1-4\delta)-o(1)})$ queries for any $\delta\in[0,\frac{1}{4}]$. Because gradient descent only uses linear memory $\mathcal O(d\ln 1/\epsilon)$ but makes $\Omega(1/\epsilon^2)$ queries, our results imply that it is essentially Pareto-optimal in the oracle complexity/memory tradeoff. Further, our results show that the oracle complexity for deterministic algorithms is always polynomial in $1/\epsilon$ if the algorithm has less than quadratic memory in $d$. This reveals a sharp phase transition since with quadratic $\mathcal O(d^2 \ln1/\epsilon)$ memory, cutting plane methods only require $\mathcal O(d\ln 1/\epsilon)$ queries.
Author
——
Topics
——
* computational learning theory
* continuous optimization
* foundations of machine learning
Strong vs. Weak Range Avoidance and the Linear Ordering Principle
==================================================================================
Abstract
——–
In a pair of recent breakthroughs \cite{CHR,Li} it was shown that the classes $\mathsf{S_2^E}, \mathsf{ZPE^{NP}}$, and $\mathsf{\Sigma_2^E}$ require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan \cite{Kannan}. These results were obtained by designing a surprising new algorithm for the total search problem \emph{Range Avoidance:} given a circuit $C: \B^n \to \B^{n+1}$, find an $n+1$-bit string outside its range. Range Avoidance is a member of the class $\mathsf{TF\Sigma_2^P}$ of total search problems in the \emph{second level} of the polynomial hierarchy, analogous to its better-known counterpart $\mathsf{TFNP}$ in the first level. $\mathsf{TF\Sigma_2^P}$ was only recently introduced in \cite{KKMP} and its structure is not well understood. We investigate here the extent to which algorithms of the kind in \cite{CHR,Li} can be applied to other search problems in this class, and prove a variety of results both positive and negative.
On the positive side we show that Li’s Range Avoidance algorithm \cite{Li} can be improved to give a reduction from Range Avoidance to a natural total search problem we call the \emph{Linear Ordering Principle} or “LOP”: given a circuit $\prec:\B^n \times \B^n \to \B$ purportedly defining a total order on $\B^n$, find either a witness that $\prec$ is not a total order or else a minimal element in the ordering. The problem LOP is quite interesting in its own right, as it defines a natural \emph{syntactic subclass} “$\mathsf{L_2^P}$” of $\mathsf{S_2^P}$ which nonetheless maintains most of the interesting properties of $\mathsf{S_2^P}$; in particular we show that $\mathsf{L_2^P}$ contains $\mathsf{MA}$ and that its exponential analogue $\mathsf{L_2^E}$ requires $2^n/n$ size circuits. Both of these are consequences of our reduction from Range Avoidance to LOP.
On the negative side we prove that the algorithms developed in \cite{CHR,Li} cannot be extended to \emph{Strong Range Avoidance}, a problem considered in the same paper which first introduced Range Avoidance \cite{KKMP}. In this problem we are given a circuit $C: \B^n \setminus\{0^n\} \to \B^n$, and once again seek a point outside its range. We give a separation in the decision tree (oracle) model showing that this problem cannot be solved in $\mathsf{FP^{\Sigma_2^P}_{||}}$, which in particular rules out all of the new kinds of algorithms considered in \cite{CHR,Li}. This black box separation is derived from a novel depth 3 $\mathsf{AC^0}$ circuit lower bound for a \emph{total search problem}, which we believe is of independent interest from the perspective of circuit complexity: we show that unlike previous depth 3 lower bounds, ours \emph{cannot be proven} by reduction from a decision problem, and thus requires new techniques specifically tailored to total search problems. Proving lower bounds of this kind was recently proposed by Vyas and Williams in the context of the original (Weak) Avoid problem \cite{vyas-williams}.
Authors
——-
Topics
——
* circuit complexity
* computational complexity
* pseudorandomness and derandomization
Novel properties of hierarchical probabilistic partitions and their algorithmic
applications
================================================================================================
Abstract
——–
We present a refined construction of \emph{hierarchical probabilistic partitions} with novel properties, substantially stronger than previously known. Our construction provides a family of hierarchical partitions enabling fast dynamic programming algorithms, by guaranteeing that given a sparse set of balls, \emph{each cell} of the hierarchical partition intersects only a small number of balls. The number of balls intersecting a cell is bounded solely as a function of the padding parameter of the partition (which is bounded in particular by the doubling dimension). This is in contrast to standard guarantees for probabilistic partitions which holds only in expectation. Additionally, each cell of our partition has a significantly smaller description than in previous constructions.
These novel partition properties allow faster dynamic programs for a wide spectrum of fundamental problems defined by inherent or implicit sparsity.
Among our main applications highlighting the utility of the novel properties are two well-studied clustering problems: \textbf{min-sum radii (MSR)} and \textbf{min-sum diameters (MSD)} clustering. The input to both these problems is a metric space and an integer $k$, and the goal is to partition the space into $k$ clusters so as to minimize the sum of radii or diameters of the clusters, respectively. We apply our construction to give dramatically improved exact and approximation algorithms for these problems in Euclidean and doubling spaces, planar graphs, and more general settings. In particular, we obtain for these problems the \emph{first} PTAS for doubling spaces, improving and generalizing upon the time bounds known for Euclidean space, even achieving \emph{linear time} algorithms for fixed parameter $k$. We also obtain the \emph{first} PTAS for MSR for all metrics of bounded padding parameter, including planar and minor excluded metrics.
Our methods also extend to other clustering problems, including $\alpha$-\textbf{MSR} and $\alpha$-\textbf{MSD} (where the measure is the sum of radii or diameters raised to power of $\alpha$), as well as \textbf{aversion clustering},
providing in similar settings the \emph{first} QPTAS and \emph{first fixed parameter} PTAS for these problems. Moreover, all of our clustering results extend to the corresponding clustering problems \emph{with outliers}.
Our construction applies as well to a wide range of network design problems possessing inherent sparsity properties in doubling spaces. Notably, we can apply our method to dramatically improve upon the best known bounds for the \textbf{traveling salesman (TSP)} and \textbf{Steiner tree} problems in doubling spaces.
%and matching and significantly generalizing the state-of-the-art run-times
%that were only recently shown
%for the special case of the Euclidean space.
Similarly, we significantly improve upon the best known run-times for \textbf{Steiner forest}, \textbf{TSP with neighborhoods}, \textbf{prize collecting TSP}, and \textbf{2-ECSS} (two edge-connected spanning subgraph), all in doubling spaces.
Our new constructions of hierarchical probabilistic partitions present a major simplification of previous methods, and provide a more natural and useful tool for future applications.
Authors
——-
Topics
——
* approximation algorithms
* high-dimensional algorithms
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
============================================================================
Abstract
——–
We present a deterministic comparison-based algorithm that sorts sequences avoiding a fixed permutation $\pi$ in linear time, even if $\pi$ is a priori unkown.
Moreover, the dependence of the multiplicative constant on the pattern $\pi$ matches the information-theoretic lower bound.
A crucial ingredient is an algorithm for performing efficient multi-way merge based on the Marcus-Tardos theorem.
As a direct corollary, we obtain a linear-time algorithm for sorting permutations of bounded twin-width.
Author
——
Topics
——
* algorithms and data structures
* combinatorics
* computational complexity
Succinct arguments for QMA from standard assumptions via compiled nonlocal
games
================================================================================================
Abstract
——–
We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work of Mahadev (FOCS ’18), Bartusek et al. (CRYPTO ’22) also constructed a succinct classical argument system for QMA. However, their construction relied on post-quantumly secure indistinguishability obfuscation, a very strong primitive which is not known from standard cryptographic assumptions. In contrast, the primitives we use (namely, collapsing hash functions and a mild version of quantum homomorphic encryption) are much weaker and are implied by standard assumptions such as LWE. Our protocol is constructed using a general transformation which was designed by Kalai et al. (STOC ’23) as a candidate method to compile any quantum nonlocal game into an argument system. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements on maximally entangled states, the latter of which is a key component in the proof of MIP* = RE in quantum complexity.
Authors
——-
Topics
——
* computational complexity
* cryptography
* pseudorandomness and derandomization
* quantum computing
An XOR Lemma for Deterministic Communication Complexity
========================================================================
Abstract
——–
We prove a lower bound on the communication complexity of computing the $n$-fold xor of an arbitrary function $f$, in terms of the communication complexity and rank of $f$. We prove that $D(f^{\oplus n}) \geq n \cdot \Big(\frac{\Omega(D(f))}{\log \mathsf{rk}(f)} -\log \mathsf{rk}(f)\Big )$, where here $D(f), D(f^{\oplus n})$ represent the deterministic communication complexity, and $\mathsf{rk}(f)$ is the rank of $f$. Our methods involve a new way to use information theory to reason about deterministic communication complexity.
Authors
——-
Topic
—–
* communication complexity
Certifying almost all quantum states with few single-qubit measurements
========================================================================================
Abstract
——–
Certifying that an $n$-qubit state $\rho$ synthesized in the lab is close to the target state $|\psi \rangle$ is a fundamental task in quantum information science. However, existing rigorous protocols either require deep quantum circuits or exponentially many single-qubit measurements. In this work, we prove that almost all $n$-qubit target states $|\psi \rangle$, including those with exponential circuit complexity, can be certified from only $O(n^2)$ single-qubit measurements. This result is established by a new technique that relates certification to the mixing time of a random walk. Our protocol has applications for benchmarking quantum systems, for optimizing quantum circuits to generate a desired target state, and for learning and verifying neural networks, tensor networks, and various other representations of quantum states using only single-qubit measurements. We show that such verified representations can be used to efficiently predict highly non-local properties of $\rho$ that would otherwise require an exponential number of measurements on $\rho$. We demonstrate these applications in numerical experiments with up to 120 qubits, and observe advantage over existing methods such as cross-entropy benchmarking (XEB).
Authors
——-
Topic
—–
* quantum computing
Canonical forms for matrix tuples in polynomial time
=====================================================================
Abstract
——–
Left-right and conjugation actions on matrix tuples have received considerable attention in theoretical computer science due to their connections with polynomial identity testing, group isomorphism, and tensor isomorphism. In this paper, we present polynomial-time algorithms for computing canonical forms of matrix tuples over a finite field under these actions. Our algorithm builds upon new structural insights for matrix tuples, which can be viewed as a generalization of Schur’s lemma for irreducible representations to general representations.
Authors
——-
Topics
——
* algebraic computation
* algorithms and data structures
Locally Stationary Distributions
=================================================
Abstract
——–
Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow-mixing is inevitable since it is computationally intractable to sample from their stationary measure.
Nevertheless, Markov chains can be shown to always converge quickly to measures that are *locally stationary*, i.e., measures that don’t change over a small number of steps. These locally stationary measures are analogous to local minima in continuous optimization, while stationary measures correspond to global minima.
While locally stationary measures can be statistically far from stationary measures, do they enjoy provable theoretical guarantees that have algorithmic implications? We study this question in this work and demonstrate three algorithmic applications of locally stationary measures:
1. We show that Glauber dynamics on the hardcore model can be used to find independent sets of size $\Omega\left(\frac{\log d}{d} \cdot n\right)$ in triangle-free graphs of degree at most $d$.
2. Let $W$ be a symmetric real matrix with bounded spectral diameter and $v$ be a unit vector. Given the matrix $M = \lambda vv^\top + W$ with a planted rank-one spike along vector $v$, for sufficiently large constant $\lambda$, Glauber dynamics on the Ising model defined by $M$ samples vectors $x \in \{\pm 1\}^n$ that have constant correlation with the vector $v$.
3. Let $M = A_{G} – \frac{d}{n}11^\top$ be a centered version of the adjacency matrix where the graph $G$ is drawn from a sparse 2-community stochastic block model. Leveraging the results from a parallel submission of a subset of the coauthors (FOCS submission ID \#260), we show that for sufficiently large constant $\lambda$, Glauber dynamics on the Ising model defined by $M$ samples vectors $x \in \{\pm 1\}^n$ that have constant correlation with the hidden community vector $\sigma$.
In other words, Glauber dynamics subsumes the spectral method for *spiked Wigner* and *community detection*, by *weakly* recovering the planted spike.
Authors
——-
Topics
——
* average-case algorithms and complexity
* combinatorics
* high-dimensional algorithms
* Markov chains
* randomized algorithms
Computational hardness of detecting graph lifts and certifying lift-monotone
properties of random regular graphs
================================================================================================
Abstract
——–
We introduce a new conjecture on the computational hardness of detecting random lifts of graphs: we claim that there is no polynomial-time algorithm that can distinguish between a large random $d$-regular graph and a large random lift of a Ramanujan $d$-regular base graph (provided the lift is corrupted by a small amount of extra noise), and likewise for bipartite random graphs and lifts of bipartite Ramanujan graphs. We give evidence for this conjecture by proving lower bounds against the local statistics hierarchy of hypothesis testing semidefinite programs. We then explore the consequences of the conjecture for the hardness of certifying bounds on numerous functions of random regular graphs, expanding on a direction initiated by Bandeira, Banks, Kunisky, Moore, and Wein (2021). Conditional on this conjecture, we show that no polynomial-time algorithm can certify tight bounds on the maximum cut or maximum independent set of random 3- or 4-regular graphs, or on the chromatic number of random 7-regular graphs. Asymptotically for large degree for the maximum independent set and for any degree for the minimum dominating set, we show similar gaps, finding that naive spectral and combinatorial bounds are optimal among efficiently computable ones. Likewise, for small set vertex and edge expansion in the limit of very small sets, we show that the spectral bounds due to Kahale (1995) are optimal efficient certificates.
Authors
——-
Topics
——
* average-case algorithms and complexity
* combinatorial optimization
* combinatorics
* continuous optimization
Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
===============================================================================================
Abstract
——–
In the task of differentially private (DP) continual counting, we receive a stream of increments and our goal is to output an approximate running total of these increments, without revealing too much about any specific increment.
Despite its simplicity, differentially private continual counting has attracted significant attention both in theory and in practice.
Existing algorithms for differentially private continual counting are either inefficient in terms of their space usage or add an excessive amount of noise.
We present two approaches (for different parameter regimes) that achieve near-optimal accuracy for DP continual counting and only require logarithmic or polylogarithmic space (and time).
Our first approach is based on a space-efficient streaming matrix multiplication algorithm for a class of Toeplitz matrices.
We show that to instantiate this algorithm for DP continual counting, it is sufficient to find a low-degree rational function that approximates the square root on the complex unit circle. We then apply and extend tools from approximation theory to achieve this.
We also derive efficient closed-forms for the objective function for arbitrarily many steps, and show direct numerical optimization yields a highly practical solution to the problem.
Authors
——-
Topics
——
* foundations of fairness, privacy and databases
* streaming algorithms
The Communication Complexity of Approximating Matrix Rank
==========================================================================
Abstract
——–
We fully determine the communication complexity of approximating matrix rank, over any finite field $\mathbb{F}$. We study the most general version of this problem, where $0\leq r<R\leq n$ are given integers and Alice and Bob need to determine whether their respective matrices $A,B\in\mathbb{F}^{n\times n}$ satisfy $\rk(A+B)=r$ versus $\rk(A+B)=r.$ We show that this problem has communication cost $\Omega(r^{2}\log|\mathbb{F}|),$ which is optimal. Our lower bound holds even for quantum protocols and even for error probability $\frac{1}{2}(1-\mathbb{F}^{-r/3}),$ which too is optimal because this problem has a two-bit classical protocol with error $\frac{1}{2}(1-|\mathbb{F}|^{-\Theta(r)}).$ Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers $r$ and $R,$ with no implication for the approximation of matrix rank.
We settle an analogous question for subspaces, where Alice has an $m$-dimensional subspace $S\subseteq\mathbb{F}^{n},$ Bob has an $\ell$-dimensional subspace $T\subseteq\mathbb{F}^{n},$ and they need to approximate the dimension of $S\cap T$ (equivalently, approximate the dimension of the subspace $S+T$ generated by $S$ and $T$). We prove that distinguishing the case $\dim(S\cap T)=r$ from $\dim(S\cap T)=R$ with probability $\frac{1}{2}(1-\gamma)$ has communication cost $\Theta((\log_{|\mathbb{F}|}\lceil q^{m-R}\gamma\rceil+1)(\log_{|\mathbb{F}|}\lceil q^{\ell-R}\gamma\rceil+1)\log|\mathbb{F}|),$ for all meaningful settings of the problem parameters $m,\ell,r,R,\gamma,$ where $r<R.$
As an application, we obtain an $\Omega(\frac{1}{p}\cdot n^{2}\log|\mathbb{F}|)$ memory lower bound for any streaming algorithm with $p$ passes that approximates the rank of an input matrix $M\in\mathbb{F}^{n\times n}$ within a factor of $2-\delta,$ for any $\delta>0.$ Our result is an exponential improvement in $p$ over previous work, and furthermore it holds even for correctness probability $\frac{1}{2}+|\mathbb{F}|^{-\Theta(n)}.$
Authors
——-
Topics
——
* algebraic computation
* communication complexity
* streaming algorithms
Jump operators, Interactive Proofs and Proof Complexity Generators
===================================================================================
Abstract
——–
A jump operator $J$ in proof complexity is a function such that for any proof system $P$, $J(P)$ is a proof system such that $P$ cannot simulate $J(P)$. Some candidate jump operators were proposed by Kraj\'{\i}\v{c}ek and Pudl{\’a}k \cite{kp89} and Kraj\'{\i}\v{c}ek \cite{krimp}, but it is an open problem whether computable jump operators exist or not. In the first part of this paper, we introduce a new candidate jump operator based on the power of interactive proofs which given a proof system $P$, $\lp\IP,P\rp$ ($\IP$-randomized implicit proof system based on $P$) is a $\MA$ proof system. This jump operator can be seen as a version of Kraj\'{\i}\v{c}ek’s implicit proof system \cite{krimp} and in a sense, it is related to the Ideal proof system of Grochow and Pitassi \cite{ips}. In the first step, we prove that for any proof system $P$, there is an explicit strongly enough proof system $Q$ such that if $Q$ proves exponential hard on average circuit lower bounds efficiently, then $Q$ simulates $\lp\IP,P\rp$. In particular, if $i\EF$ (Kraj\'{\i}\v{c}ek’s implicit Extended Frege) proves exponential hard on average circuit lower bounds efficiently, then $i\EF$ simulates $\lp \IP,\EF\rp$. In the rest of the first part of the paper, we show that $\IP$-randomized implicit proof systems can be used to prove new connections between different well-studied concepts in complexity theory:
\begin{enumerate}
\item Hardness magnification for strong proof systems: We prove that for any strong enough proof system $P$, if the truth-table generator is hard for $P$, then for any proof system $Q$ that contains tree-like Resolution and any tautology $\phi$, $P$ requires $2^{\Omega(|\phi|)}$ size $P$-proofs to prove the formula “$\lp\IP,Q\rp$ does not have polynomial size proofs for $\phi$”.
\item Hardness of proving proof complexity lower bounds: We prove that under different hardness assumptions, it is hard to prove super-polynomial lower bounds for $\lp\IP,\res^*\rp$ ($\res^*$ is tree-like Resolution) by showing unprovability results for the statement which says that “$\lp\IP,\res^*\rp$ is not a polynomially bounded proof system” in different strong bounded arithmetics. In particular, we prove that if there is a stretching generator $g$ which is exponentially pseudo-surjective for $\EF$, then $\S$ is consistent with the statement “$\lp\IP,\res^*\rp$ is a sound proof system and it has polynomial size proofs for any true DNF”.
\item Automatability and feasible disjunction property for Extended Frege: We show that if $\P/\poly$ natural properties useful against $\P/\poly$ do not exist, then either $\EF$ is not automatable or intuitionistic $\S$ does not prove the strong soundness of $\lp\IP,\res^*\rp$. Similarly, if $\NP/\poly$ natural properties useful against $\P/\poly$ do not exist, then either $\EF$ does not have the feasible disjunction property or intuitionistic $\S$ does not prove the strong soundness of $\lp\IP,\res^*\rp$.
\end{enumerate}
Motivated by the hardness assumptions that enable us to prove item 2 in the above list, we introduce a new hardness property for proof complexity generators. We give a model-theoretic characterization of this property and investigate its relationship with previously known hardness properties.
One ingredient of our proofs is a formalization of the sum-check protocol \cite{sumcheck} in $\S$ which might be of independent interest.
In the second part of the paper, we looked at the general theory of jump operators and considered an
old conjecture by Pudl\’ak \cite{pudcon} about finite consistency sentences for first-order theories of arithmetic. In this direction, we proved that certain statements are equivalent, in particular, we proved that the
widely believed assumption about the existence of computable jump operators in proof complexity is
equivalent to a weaker form of Pudlák’s conjecture:
\begin{itemize}
\item There exists a partial recursive jump operator in proof complexity.
\item For any strong enough finitely axiomatizable arithmetical theory $S$, $S$ does not have polynomial size proofs for $Con_{S+Con_S}(\bar{n})$ in $n$.
\end{itemize}
Author
——
Topic
—–
* computational complexity
Optimal quantile estimation: beyond the comparison model
=========================================================================
Abstract
——–
Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1, x_2, \dots, x_n$ from some universe of size $U$ arriving in a data stream, a \textit{quantile sketch} estimates the rank of any element with additive error at most $\varepsilon n$. A low-space algorithm solving this task has applications in database systems, network measurement, load balancing, and many other practical scenarios.
Current quantile estimation algorithms described as optimal include the GK sketch (Greenwald and Khanna 2001) using $O(\varepsilon^{-1} \log n)$ words (deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using $O(\varepsilon^{-1} \log\log(1/\delta))$ words (randomized, with failure probability $\delta$). However, both algorithms are only optimal in the comparison-based model, whereas most typical applications involve streams of integers that the sketch can use aside from making comparisons.
If we go beyond the comparison-based model, the deterministic q-digest sketch (Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity of $O(\varepsilon^{-1}\log U)$ words, which is incomparable to the previously-mentioned sketches. It has long been asked whether there is a quantile sketch using $O(\varepsilon^{-1})$ words of space (which is optimal as long as $n \leq \mathrm{poly}(U)$). In this work, we present a \textit{deterministic} algorithm using $O(\varepsilon^{-1})$ words, resolving this line of work.
Authors
——-
Topic
—–
* streaming algorithms
New Structures and Algorithms for Length-Constrained Expander Decompositions
=============================================================================================
Abstract
——–
Expander decompositions form the basis of one of the most ubiquitous and flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this paradigm to better work for problems with lengths, distances and costs. Roughly, an $(h,s)$-length $\phi$-expander decomposition is a collection of length increases to a graph so that nodes within distance $h$ can route flow over paths of length $hs$ with congestion at most $1/\phi$.
In this work, we give an almost-linear-time algorithm for computing length-constrained expander decompositions in graphs with general lengths and capacities. Notably, and unlike previous works, our algorithm allows for one to trade off off between the size of the decomposition and the length of routing paths: for any $\epsilon > 0$ not too small, our algorithm computes in almost-linear-time an $(h,s)$-length $\phi$-decomposition of size $m \cdot \phi \cdot n^\epsilon$ where $s = \exp(\text{poly}(1/\epsilon))$. The key foundations of our algorithm are: (1) a simple yet powerful structural theorem which states that the union of a sequence of sparse length-constrained cuts is itself sparse and (2) new algorithms for computing sparse length-constrained flows. A direct corollary of our result is the first efficient construction of length-constrained oblivious routings for capacitated graphs (with constant length slack).
Authors
——-
Topics
——
* algorithmic graph theory
* algorithms and data structures
* approximation algorithms
* parallel and distributed algorithms
How to Simulate Random Oracles with Auxiliary Input
====================================================================
Abstract
——–
The \emph{random oracle model} (ROM) allows us to optimistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh [CRYPTO~’07] proposed the \emph{auxiliary-input random oracle model} (AI-ROM), where a non-uniform attacker additionally gets a bounded amount of advice about the random oracle.
Proving security in the AI-ROM is often much more difficult, but a series of works starting with Unruh provided useful technical tools to do so. Although these tools lead to good results in the information-theoretic setting, they are unsatisfactory in the computational setting where the random oracle is used alongside other computational hardness assumptions. At the most basic level, we did not even know whether it is possible to efficiently simulate random oracle queries given auxiliary input, which has remained as an explicit open problem since the work of Unruh.
In this work, we resolve the above open problem and show how to efficiently simulate auxiliary-input random oracles. Moreover, the simulation has low concrete overhead, leading to small losses in exact security. We use it to prove the security of a broad class of computational schemes in the AI-ROM, including the first non-interactive zero-knowledge (NIZK) scheme in the AI-ROM. As a tool of independent interest, we develop a new notion of ultra-secure pseudorandom functions with fast RAM evaluation, which can achieve $2^\lambda$ security while having sublinear $\smallo(\lambda)$ evaluation time.
Authors
——-
Topic
—–
* cryptography
Tensor cumulants for statistical inference on invariant distributions
======================================================================================
Abstract
——–
Many problems in high-dimensional statistics appear to have a \emph{statistical-computational gap}: a range of values of the signal-to-noise ratio where inference is information-theoretically possible, but (conjecturally) computationally intractable. A canonical such problem is Tensor PCA, where we observe a tensor $Y$ consisting of a rank-one signal plus Gaussian noise. Multiple lines of work suggest that Tensor PCA becomes computationally hard at a critical transition. In particular, the low-degree likelihood ratio shows that, below this transition, no low-degree polynomial algorithm can detect the signal with high probability, or estimate the signal with reasonable accuracy. Conversely, various spectral algorithms are known to succeed above this transition.
Here we unify and extend this work by considering \emph{tensor networks}, invariant polynomials where multiple copies of $Y$ are “contracted” to produce scalars, vectors, matrices, or other tensors. We define a new set of objects, \emph{tensor cumulants}, which provide an explicit, near-orthogonal basis for invariant polynomials of a given degree. This basis lets us unify and strengthen previous results on low-degree hardness, giving a combinatorial explanation of the hardness transition and of a continuum of subexponential-time algorithms that work below it. They also allow us to solve a new problem of distinguishing between different tensor ensembles, such as Wigner and Wishart tensors, giving a computational version of the Central Limit Theorem. Finally, we believe these cumulants are valuable objects in their own right: they generalize the free cumulants of free probability theory from matrices to tensors, and share many of their properties.
Authors
——-
Topics
——
* average-case algorithms and complexity
* foundations of machine learning
* high-dimensional algorithms
Improved Condensers for Chor-Goldreich Sources
===============================================================
Abstract
——–
One of the earliest models of weak randomness is the Chor-Goldreich (CG) source.
A $(t,n,k)$-CG-source is a sequence of random variables
$X=(X_1,\dots,X_t) \in (\{0, 1\}^n)^t$ where each $X_i$ has min-entropy $k$ conditioned on any fixing of $X_1,\dots,X_{i-1}$.
Chor and Goldreich proved that there is no deterministic way to extract randomness from such a source.
Nevertheless, Doron, Moshkovitz, Oh, and Zuckerman showed that there is a deterministic way to condense a CG-source into a string close to having small entropy gap $g$, i.e., the min-entropy of $Z \in \{0, 1\}^m$ is $m-g$.
They gave applications of such a condenser to simulating randomized algorithms with small error and certain cryptographic tasks.
They studied the case when the block length $n$ is small and the entropy rate $k/n$ is constant.
We study the much more general setting where $n$ can be arbitrarily large, the number of blocks $t$ can be small, and the entropy rate can be small.
Specifically, we construct a condenser with small entropy gap even if $k \geq C\log n$ for a large enough constant $C$.
However, this condenser requires $t \geq \mathsf{poly}(n)$ blocks in order for the output to have entropy rate $.9$, say.
We also design a condenser that requires just a constant number of of blocks $t$ for the output entropy rate to be $.9$ when the CG-source has constant entropy rate.
Moreover, this second condenser has exponentially small error.
Finally, we provide strong existential results and a nearly matching lower bound.
Authors
——-
Topic
—–
* pseudorandomness and derandomization
Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond
Gaussians
================================================================================================
Abstract
——–
We study the problem of estimating the parameters of an exponential family distribution when samples are shown only if they fall in some (unknown) subset $S \subseteq \R^d$. Kontonis et al. (FOCS’19) give a $d^{\text{poly}(1/\epsilon)}$ time algorithm for finding $\epsilon$-accurate parameters for the special case of Gaussians with diagonal covariance matrix. Recently, Diakonikolas et al. show that this exponential dependence on $1/\epsilon$ is necessary when $S$ belongs to some special classes. These works leave the following open problems: (1) can we estimate arbitrary Gaussians with unknown truncation or even extend the results beyond Gaussian distributions?, and (2) can we design of polynomial in $1/\epsilon$ time algorithms when $S$ is simple, e.g., $S$ is a halfspace or an axis-aligned rectangle.
Our work answers these open questions via the following results:
* We provide an estimation algorithm with sample and time complexity $d^{\text{poly}(p/\epsilon)}$ for any exponential family that satisfies some structural assumptions and any unknown set $S$ that is $\epsilon$-approximable by a degree-$p$ polynomial. This result has two important applications:
* the first algorithm for truncated linear regression with unknown truncation under Gaussian features, and
* the first algorithm for estimating general Gaussian distributions (even with non-diagonal covariance matrix) from truncated samples with unknown truncation.
* We provide an algorithm with poly$(d, 1/\epsilon)$ sample and time complexity that works for a set of exponential families, that contain multivariate Gaussian, when $S$ is a half-space or a union of a constant number of axis-aligned rectangles. This is the first fully polynomial time algorithm for estimation with unknown truncation.
Authors
——-
Topics
——
* computational learning theory
* high-dimensional algorithms
A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear
Sketches
================================================================================================
Abstract
——–
The majority of streaming problems are defined and analyzed in a static setting, where the data stream is fixed in advance to be a fixed sequence of insertions and deletions. However, many real world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied $\ell_0$-estimation problem over turnstile, integer streams. For any linear streaming algorithm $\mathcal{A}$ which uses sketching matrix $\bA \in \mathbb{Z}^{r \times n}$, this attack makes $\tilde O(r^8)$ queries and succeeds with high constant probability in breaking the sketch. Additionally, we give an adaptive attack against linear sketches for the $\ell_0$-estimation problem over finite fields $\mathbb{F}_p$, which requires a smaller number of $\tilde O(r^3)$ queries. Our results provide an exponential improvement over the previous number of queries known to break an $\ell_0$-estimation sketch.
Authors
——-
Topics
——
* streaming algorithms
* sublinear algorithms
Fully Dynamic Matching and Ordered Ruzsa-Szemer\’edi Graphs
============================================================================
Abstract
——–
We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is particularly on algorithms that maintain the edges of a $(1-\epsilon)$-approximate maximum matching for an arbitrarily small constant $\epsilon > 0$. Until recently, the fastest known algorithm for this problem required $\Theta(n)$ time per update where $n$ is the number of vertices. This bound was slightly improved to $n/(\log^* n)^{\Omega(1)}$ by Assadi, Behnezhad, Khanna, and Li [STOC’23] and very recently to $n/2^{\Omega(\sqrt{\log n})}$ by Liu [ArXiv’24]. Whether this can be improved to $n^{1-\Omega(1)}$ remains a major open problem.
In this paper, we present a new algorithm that maintains a $(1-\epsilon)$-approximate maximum matching. The update-time of our algorithm is parametrized based on the density of a certain class of graphs that we call Ordered Ruzsa-Szemerédi (ORS) graphs, a generalization of the well-known Ruzsa-Szemerédi graphs. While determining the density of ORS (or RS) remains a hard problem in combinatorics, we prove that if the existing constructions of ORS graphs are optimal, then our algorithm runs in $\widetilde{O}(\sqrt{n^{1+\epsilon}})$ time for any fixed $\epsilon > 0$ which would be significantly faster than existing near-linear in $n$ time algorithms.
Our second main contribution is a better upper bound on density of both ORS and RS graphs with linear size matchings. The previous best upper bound was due to a proof of the triangle-removal lemma from more than a decade ago due to Fox [Annals of Mathematics ’11].
Authors
——-
Topics
——
* combinatorics
* sublinear algorithms
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
===========================================================================================
Abstract
——–
Given a so called “Sperner coloring” of a triangulation of the $D$-dimensional simplex, Sperner’s lemma guarantees the existence of a *rainbow simplex*, i.e.~a simplex colored by all $D+1$ colors. However, finding a rainbow simplex was the first problem to be proven \PPAD-complete in Papadimitriou’s classical paper introducing the class PPAD [Pap94].
In this paper, we prove that the problem does not become easier if we relax “all $D+1$ colors” to allow some fraction of missing colors: in fact, for any constant $D$, finding even a simplex with just three colors remains PPAD-complete!
Our result has an interesting application for the envy-free cake cutting from fair division.
It is known that if agents value pieces of cake using general continuous functions satisfying a simple boundary condition (“a non-empty piece is better than an empty piece of cake”), there exists an envy-free allocation with connected pieces. We show that for any constant number of agents it is PPAD-complete to find an allocation –even using any constant number of possibly disconnected pieces– that makes just three agents envy-free.
Authors
——-
Topics
——
* algorithmic game theory
* computational complexity
Faster isomorphism testing of p-groups of Frattini class-2
===========================================================================
Abstract
——–
The finite group isomorphism problem asks to decide whether two finite groups of order $N$ are isomorphic. Improving the classical $N^{O(\log N)}$-time algorithm for group isomorphism is a long-standing open problem. It is generally regarded that $p$-groups of class $2$ and exponent $p$ form a bottleneck case for group isomorphism in general. The recent breakthrough by Sun (STOC ’23) presents an $N^{O((\log N)^{5/6})}$-time algorithm for this group class.
In this paper, we improve Sun’s algorithm by presenting an $N^{\tilde O((\log N)^{1/2})}$-time algorithm for this group class. We also extend our result to the more general $p$-groups of Frattini class-$2$, which includes non-abelian $2$-groups.
Our algorithm is obtained by sharpening the key technical ingredients in Sun’s algorithm and building connections with other research topics. One intriguing connection is with the maximal and non-commutative ranks of matrix spaces, which have recently received considerable attention in algebraic complexity and computational invariant theory. Results from the theory of Tensor Isomorphism complexity class (Grochow–Qiao, SIAM J. Comput. ’23) are utilized to simplify the algorithm and achieve the extension to $p$-groups of Frattini class-$2$.
Authors
——-
E\”otv\”os Lor\’and Research Network (ELKH), Budapest, Hungary)
University of Technology, Ultimo NSW 2007, Australia)
Topics
——
* algebraic computation
* algorithms and data structures
Spectral Guarantees for Adversarial Streaming PCA
==================================================================
Abstract
——–
In streaming PCA, we see a stream of vectors
$x_1, \dotsc, x_n \in \R^d$ and want to estimate the top eigenvector
of their covariance matrix. This is easier if the spectral ratio
$R = \lambda_1 / \lambda_2$ is large. We ask: how large does $R$
need to be to solve streaming PCA in $\widetilde O(d)$ space? Existing
algorithms require $R = \widetilde\Omega(d)$. We show:
\begin{itemize}
\item In the linear sketching model, $R = \widetilde\Omega(\sqrt{d})$ is necessary.
\item In the insertion-only model, a variant of Oja’s algorithm
gets $o(1)$ error for $R = O(\log n \log d)$.
\item No algorithm {with $o(d^2)$ space} gets $o(1)$ error for $R = O(1)$.
\end{itemize}
Our analysis is the first application of Oja’s algorithm to
adversarial streams. It is also the first algorithm for adversarial
streaming PCA that is designed for a \emph{spectral}, rather than
\emph{Frobenius}, bound on the tail; and the bound it needs is
exponentially better than is possible by adapting a Frobenius
guarantee.
Authors
——-
Topics
——
* streaming algorithms
* sublinear algorithms
