We revisit the problem of designing sublinear algorithms for estimating the average degree of an \(n\)-vertex graph. The standard access model for graphs allows for the following queries: sampling a uniform random vertex, the degree of a vertex, sampling a uniform random neighbor of a vertex, and “pair queries” which determine if a pair of vertices form an edge. In this model, original results [Goldreich-Ron, RSA 2008; Eden-Ron-Seshadhri, SIDMA 2019] on this problem prove that the complexity of getting \((1+\varepsilon)\)-multiplicative approximations to the average degree, ignoring \(\varepsilon\)-dependencies, is \(\Theta(\sqrt{n})\). When random edges can be sampled, it is known that the average degree can be estimated in \(\tilde{O}(n^{1/3})\) queries, even without pair queries Motwani-Panigrahy-Xu-ICALP-2007, Beretta-Tetek-TALG-2024.

For a function \(f : \{0, 1\}^n \rightarrow \{0, 1\}\), the junta testing problem asks whether \(f\) depends on only \(k\) variables. If \(f\) depends on only \(k\) variables, the feature selection problem asks to find those variables. We prove that these two tasks are statistically equivalent. Specifically, we show that the “brute-force” algorithm, which checks for any set of \(k\) variables consistent with the sample, is simultaneously sample-optimal for both problems, and the optimal sample size is \begin{align} \Theta\left( \frac{1}{\varepsilon} \left(\sqrt{2^{k} \log\binom{n}{k}} + \log\binom{n}{k} \right) \right).\end{align}

We study the problem of learning junta distributions on {±1}ⁿ, where a distribution is a k-junta if its probability mass function depends on a subset of at most k variables. We make two main contributions: - We show that learning k-junta distributions is computationally equivalent to learning k-parity functions with noise (LPN), a landmark problem in computational learning theory. - We design an algorithm for learning junta distributions whose statistical complexity is optimal, up to polylogarithmic factors. Computationally, our algorithm matches the complexity of previous (non-sample-optimal) algorithms. Combined, our two contributions imply that our algorithm cannot be significantly improved, statistically or computationally, barring a breakthrough for LPN.

We give a reduction from (1 + ε)-approximate Earth Mover’s Distance (EMD) to (1 + ε)-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given p ∈ [1], [2] and two sets of n points $X,Y \subset \left( {{\mathbb{R}^d},{\ell _p}} \right)$, their EMD is the minimum cost of a perfect matching between X and Y, where the cost of matching two vectors is their ℓpdistance. Further, CP is the basic problem of finding a pair of points realizing minx∈X,y∈Y║x − y║p. Our contribution is twofold:• We show that if (1 + ε)-approximate CP can be computed in time n2−ϕ, then a 1 + O(ε) approximation to EMD can be computed in time n2−Ω(ϕ).• Plugging in the fastest known algorithm for CP [5], we obtain a (1 + ε)-approximation algorithm for EMD running in time ${n^{2 - \tilde \Omega \left( {{\varepsilon ^{1/3}}} \right)}}$ for high-dimensional point sets, which improves over the prior fastest running time of ${n^{2 - \Omega \left( {{\varepsilon ^2}} \right)}}$ [13].Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.

In the online sorting problem, $n$ items are revealed one by one and have to be placed (immediately and irrevocably) into empty cells of a size-$n$ array. The goal is to minimize the sum of absolute differences between items in consecutive cells. This natural problem was recently introduced by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) as a tool in their study of online geometric packing problems. They showed that when the items are reals from the interval $[0,1]$ a competitive ratio of $O(\sqrt{n})$ is achievable, and no deterministic algorithm can improve this ratio asymptotically. In this paper, we extend and generalize the study of online sorting in three directions: - randomized: we settle the open question of Aamand et al. by showing that the $O(\sqrt{n})$ competitive ratio for the online sorting of reals cannot be improved even with the use of randomness; - stochastic: we consider inputs consisting of $n$ samples drawn uniformly at random from an interval, and give an algorithm with an improved competitive ratio of $\widetilde{O}(n^{1/4})$. The result reveals connections between online sorting and the design of efficient hash tables; - high-dimensional: we show that $\widetilde{O}(\sqrt{n})$-competitive online sorting is possible even for items from $\mathbb{R}^d$, for arbitrary fixed $d$, in an adversarial model. This can be viewed as an online variant of the classical TSP problem where tasks (cities to visit) are revealed one by one and the salesperson assigns each task (immediately and irrevocably) to its timeslot. Along the way, we also show a tight $O(\log{n})$-competitiveness result for uniform metrics, i.e., where items are of different types and the goal is to order them so as to minimize the number of switches between consecutive items of different types.

Current uncertainty quantification is memory and compute expensive, which hinders practical uptake. To counter, we develop Sketched Lanczos Uncertainty (SLU): an architecture-agnostic uncertainty score that can be applied to pre-trained neural networks with minimal overhead. Importantly, the memory use of SLU only grows logarithmically with the number of model parameters. We combine Lanczos' algorithm with dimensionality reduction techniques to compute a sketch of the leading eigenvectors of a matrix. Applying this novel algorithm to the Fisher information matrix yields a cheap and reliable uncertainty score. Empirically, SLU yields well-calibrated uncertainties, reliably detects out-of-distribution examples, and consistently outperforms existing methods in the low-memory regime.

We design an additive approximation scheme for estimating the cost of the min-weight bipartite matching problem: given a bipartite graph with non-negative edge costs and ε > 0, our algorithm estimates the cost of matching all but O(ε)-fraction of the vertices in truly subquadratic time O(n2−δ(ε)). Our algorithm has a natural interpretation for computing the Earth Mover’s Distance (EMD), up to a ε-additive approximation. Notably, we make no assumptions about the underlying metric (more generally, the costs do not have to satisfy triangle inequality). Note that compared to the size of the instance (an arbitrary n × n cost matrix), our algorithm runs in sublinear time. Our algorithm can approximate a slightly more general problem: max-cardinality bipartite matching with a knapsack constraint, where the goal is to maximize the number of vertices that can be matched up to a total cost B.

Given a large set U where each item a ∈ U has weight w ( a ), we want to estimate the total weight \(W=\sum _{a∈ U} w(a)\) to within factor of 1± ɛ with some constant probability > 1/2. Since n =| U | is large, we want to do this without looking at the entire set U . In the traditional setting in which we are allowed to sample elements from U uniformly, sampling Ω ( n ) items is necessary to provide any non-trivial guarantee on the estimate. Therefore, we investigate this problem in different settings: in the proportional setting we can sample items with probabilities proportional to their weights, and in the hybrid setting we can sample both proportionally and uniformly. These settings have applications, for example, in sublinear-time algorithms and distribution testing. Sum estimation in the proportional and hybrid setting has been considered before by Motwani, Panigrahy, and Xu [ICALP, 2007]. In their article, they give both upper and lower bounds in terms of n . Their bounds are near-matching in terms of n , but not in terms of ɛ. In this article, we improve both their upper and lower bounds. Our bounds are matching up to constant factors in both settings, in terms of both n and ɛ. No lower bounds with dependency on ɛ were known previously. In the proportional setting, we improve their \(\tilde{O}(\sqrt {n}/ɛ ^{7/2})\) algorithm to \(O(\sqrt {n}/ɛ)\) . In the hybrid setting, we improve \(\tilde{O}(\sqrt [3]{n}/ ɛ ^{9/2})\) to \(O(\sqrt [3]{n}/ɛ ^{4/3})\) . Our algorithms are also significantly simpler and do not have large constant factors. We then investigate the previously unexplored scenario in which n is not known to the algorithm. In this case, we obtain a \(O(\sqrt {n}/ɛ + \log n / ɛ ^2)\) algorithm for the proportional setting, and a \(O(\sqrt {n}/ɛ)\) algorithm for the hybrid setting. This means that in the proportional setting, we may remove the need for advice without greatly increasing the complexity of the problem, while there is a major difference in the hybrid setting. We prove that this difference in the hybrid setting is necessary, by showing a matching lower bound. Our algorithms have applications in the area of sublinear-time graph algorithms. Consider a large graph G =( V, E ) and the task of (1 ± ɛ)-approximating | E |. We consider the (standard) settings where we can sample uniformly from E or from both E and V . This relates to sum estimation as follows: we set U = V and the weights to be equal to the degrees. Uniform sampling then corresponds to sampling vertices uniformly. Proportional sampling can be simulated by taking a random edge and picking one of its endpoints at random. If we can only sample uniformly from E , then our results immediately give a \(O(\sqrt {|V|} / ɛ)\) algorithm. When we may sample both from E and V , our results imply an algorithm with complexity \(O(\sqrt [3]{|V|}/ɛ ^{4/3})\) . Surprisingly, one of our subroutines provides an (1 ± ɛ)-approximation of | E | using \(\tilde{O}(d/ɛ ^2)\) expected samples, where d is the average degree, under the mild assumption that at least a constant fraction of vertices are non-isolated. This subroutine works in the setting where we can sample uniformly from both V and E . We find this remarkable since it is O (1/ɛ 2 ) for sparse graphs.

Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical results that often assume access to (unrealistic) uniform/fully-random hash functions. In this paper, we are concerned with designing hash functions that are practical and come with strong theoretical guarantees on their performance.To this end, we present tornado tabulation hashing, which is simple, fast, and exhibits a certain full, local randomness property that provably makes diverse algorithms perform almost as if (abstract) fully-random hashing was used. For example, this includes classic linear probing, the widely used HyperLogLog algorithm of Flajolet, Fusy, Gandouet, Meunier [AOFA’97] for counting distinct elements, and the one-permutation hashing of Li, Owen, and Zhang [NIPS’12] for large-scale machine learning. We also provide a very efficient solution for the classical problem of obtaining fully-random hashing on a fixed (but unknown to the hash function) set of n keys using $O(n)$ space. As a consequence, we get more efficient implementations of the splitting trick of Dietzfelbinger and Rink [ICALP’09] and the succinct space uniform hashing of Pagh and Pagh [SICOMP’08].Tornado tabulation hashing is based on a simple method to systematically break dependencies in tabulation-based hashing techniques.

The $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular $k$-means clustering objective and is known to give an $O(\log k)$-approximation in expectation. To obtain higher quality solutions, Lattanzi and Sohler (ICML 2019) proposed augmenting $k$-means++ with $O(k \log \log k)$ local-search steps obtained through the $k$-means++ sampling distribution to yield a $c$-approximation to the $k$-means clustering problem, where $c$ is a large absolute constant. Here we generalize and extend their local-search algorithm by considering larger and more sophisticated local-search neighborhoods hence allowing to swap multiple centers at the same time. Our algorithm achieves a $9 + \varepsilon$ approximation ratio, which is the best possible for local search. Importantly we show that our algorithm is practical, namely easy to implement and fast enough to run on a variety of classic datasets, and outputs solutions of better cost.

We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used space. Among other variants, we consider strip packing and bin packing, where the container is the infinite horizontal strip [0, ∞) × [0,1] or a collection of 1 × 1 bins, respectively. If polygons may be rotated, there exist O(1)-competitive online algorithms for all problems at hand [Baker and Schwarz, SIAM J. Comput., 1983]. Likewise, if the polygons may not be rotated but only translated, then using a result from [Alt, de Berg and Knauer, JoCG, 2017] we can derive O(1)-approximation algorithms for all problems at hand. Thus, it is natural to conjecture that the online version of these problems, in which only translations are allowed, also admits a O(1)-competitive algorithm. We disprove this conjecture by showing a superconstant lower bound on the competitive ratio for several online packing problems. The offline approximation algorithm for translation-only packing sorts the convex polygons by their “natural slope”, so that they form a fan-like pattern. We prove that this step is essential, in the sense that packing polygons without rotating them is as hard as sorting numbers online. Technically, we prove lower bounds on the competitive ratio of translation-only online packing problems by reducing from a purpose-built novel and natural combinatorial problem that we call online sorting. In a nutshell, the problem requires us to place n numbers x1,…, xn coming online into an oversized array of length γn for γ ≥ 1, while minimizing the sum of absolute differences of consecutive numbers. Note that the offline optimum is achieved by sorting x1,…, xn. We show a superconstant lower bound on the competitive ratio of online sorting, for any constant γ. We prove that this yields superconstant lower bounds for all packing problems at hand. We believe that this technique is of independent interest since it uncovers a deep connection between inherently geometrical and purely combinatorial problems. As a complement, we also include algorithms for both online sorting and translation-only online strip packing with non-trivial competitive ratios. Our algorithm for strip packing relies on a new technique for recursively subdividing the strip into parallelograms of varying height, thickness and slope.

A tournament graph is a complete directed graph, which can be used to model a round-robin tournament between$n$players. In this paper, we address the problem of finding a champion of the tournament, also known as Copeland winner, which is a player that wins the highest number of matches. In detail, we aim to investigate algorithms that find the champion by playing a low number of matches. Solving this problem allows us to speed up several Information Retrieval and Recommender System applications, including question answering, conversational search, etc. Indeed, these applications often search for the champion inducing a round-robin tournament among the players by employing a machine learning model to estimate who wins each pairwise comparison. Our contribution, thus, allows finding the champion by performing a low number of model inferences. We prove that any deterministic or randomized algorithm finding a champion with constant success probability requires$\Omega (\ell n)$comparisons, where$\ell$is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing$\ell$, and we extend our analysis to three variants of the problem. Lastly, we conduct a comprehensive experimental assessment of the proposed algorithms on a question answering task on public data. Results show that our proposed algorithms speed up the retrieval of the champion up to$13\times$with respect to the state-of-the-art algorithm that perform the full tournament. The identification of the most relevant result from a set of candidates is a crucial task in many Information Retrieval and Recommender System applications including ad-hoc search, conversational search, machine translation, question answering, etc. State-of-the-art solutions solving the task leverage ad-hoc machine learning techniques—developed in a field known as Learning-to-Rank—to estimate the relevance of the set of candidate results and to select the most relevant one. These solutions address the problem in two different ways. From one side, several techniques work by estimating one candidate at a time so to select the candidate achieving the highest score. On the other side, some techniques compare a pair of candidate results at a time so to select the candidate achieving the highest sum of pairwise scores of an all-vs-all tournament between results. In this paper, we focus on the second class of techniques. In detail, we propose to model the task of identifying the most relevant result from a set of candidates as the problem of finding the champion of a tournament, which is the player that wins the highest number of matches in the tournament. Our goal is to find the champion, also known as theCopeland winner, of the tournament by minimizing the number of matches played in the tournament, i.e., the number of pairwise comparisons. We prove that any deterministic or randomized algorithm finding a champion with constant success probability requires$\Omega (\ell n)$comparisons, where$\ell$is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing$\ell$. Moreover, we extend the result by providing a parallel version of our algorithm, as well as a version that retrieve all the best$k$players of the tournament. Lastly, we conduct a comprehensive experimental assessment of the proposed algorithms on a public dataset (MS-MARCO) with the aim of speeding up a well-known state-of-the-art solution for ranking textual passages for question answering. Results show that our proposed solutions allow to speed up the identification of the champion up to$13\times$.

Given a large set U where each item a ∊ U has weight w(a), we want to estimate the total weight W = Σa∊U w(a) to within factor of 1 ± ∊ with some constant probability > 1/2. Since n = |U| is large, we want to do this without looking at the entire set U. In the traditional setting in which we are allowed to sample elements from U uniformly, sampling Ω(n) items is necessary to provide any non-trivial guarantee on the estimate. Therefore, we investigate this problem in different settings: in the proportional setting we can sample items with probabilities proportional to their weights, and in the hybrid setting we can sample both proportionally and uniformly. These settings have applications, for example, in sublinear-time algorithms and distribution testing. Sum estimation in the proportional and hybrid setting has been considered before by Motwani, Panigrahy, and Xu [ICALP, 2007]. In their paper, they give both upper and lower bounds in terms of n. Their bounds are near-matching in terms of n, but not in terms of ∊. In this paper, we improve both their upper and lower bounds. Our bounds are matching up to constant factors in both settings, in terms of both n and ∊. No lower bounds with dependency on ∊ were known previously. In the proportional setting, we improve their algorithm to . In the hybrid setting, we improve to . Our algorithms are also significantly simpler and do not have large constant factors. We then investigate the previously unexplored scenario in which n is not known to the algorithm. In this case, we obtain a algorithm for the proportional setting, and a algorithm for the hybrid setting. This means that in the proportional setting, we may remove the need for advice without greatly increasing the complexity of the problem, while there is a major difference in the hybrid setting. We prove that this difference in the hybrid setting is necessary, by showing a matching lower bound. Our algorithms have applications in the area of sublinear-time graph algorithms. Consider a large graph G = (V, E) and the task of (1 ± ∊)-approximating |E|. We consider the (standard) settings where we can sample uniformly from E or from both E and V. This relates to sum estimation as follows: we set U = V and the weights to be equal to the degrees. Uniform sampling then corresponds to sampling vertices uniformly. Proportional sampling can be simulated by taking a random edge and picking one of its endpoints at random. If we can only sample uniformly from E, then our results immediately give a algorithm. When we may sample both from E and V, our results imply an algorithm with complexity . Surprisingly, one of our subroutines provides an (1 ± ∊)-approximation of |E| using Õ(d/∊2) expected samples, where d is the average degree, under the mild assumption that at least a constant fraction of vertices are non-isolated. This subroutine works in the setting where we can sample uniformly from both V and E. We find this remarkable since it is O(1/∊2) for sparse graphs.

We consider online packing problems where we get a stream of axis-parallel rectangles. The rectangles have to be placed in the plane without overlapping, and each rectangle must be placed without knowing the subsequent rectangles. The goal is to minimize the perimeter or the area of the axis-parallel bounding box of the rectangles. We either allow rotations by 90^∘ or translations only. For the perimeter version we give algorithms with an absolute competitive ratio slightly less than 4 when only translations are allowed and when rotations are also allowed. We then turn our attention to minimizing the area and show that the competitive ratio of any algorithm is at least Ω(√n), where n is the number of rectangles in the stream, and this holds with and without rotations. We then present algorithms that match this bound in both cases and the competitive ratio is thus optimal to within a constant factor. We also show that the competitive ratio cannot be bounded as a function of Opt. We then consider two special cases. The first is when all the given rectangles have aspect ratios bounded by some constant. The particular variant where all the rectangles are squares and we want to minimize the area of the bounding square has been studied before and an algorithm with a competitive ratio of 8 has been given [Fekete and Hoffmann, Algorithmica, 2017]. We improve the analysis of the algorithm and show that the ratio is at most 6, which is tight. The second special case is when all edges have length at least 1. Here, the Ω(√n) lower bound still holds, and we turn our attention to lower bounds depending on Opt. We show that any algorithm for the translational case has a competitive ratio of at least Ω(√{Opt}). If rotations are allowed, we show a lower bound of Ω(∜{Opt}). For both versions, we give algorithms that match the respective lower bounds: With translations only, this is just the algorithm from the general case with competitive ratio O(√n) = O(√{Opt}). If rotations are allowed, we give an algorithm with competitive ratio O(min{√n,∜{Opt}}), thus matching both lower bounds simultaneously.