Kasper Green Larsen

Achieving a provable exponential quantum speedup for an important machine learning task has been a central research goal since the seminal HHL quantum algorithm for solving linear systems and the subsequent quantum recommender systems algorithm by Kerenidis and Prakash. These algorithms were initially believed to be strong candidates for exponential speedups, but a lower bound ruling out similar classical improvements remained absent. In breakthrough work by Tang, it was demonstrated that this lack of progress in classical lower bounds was for good reasons. Concretely, she gave a classical counterpart of the quantum recommender systems algorithm, reducing the quantum advantage to a mere polynomial. Her approach is quite general and was named quantum-inspired classical algorithms. Since then, almost all the initially exponential quantum machine learning speedups have been reduced to polynomial via new quantum-inspired classical algorithms. From the current state-of-affairs, it is unclear whether we can hope for exponential quantum speedups for any natural machine learning task.
In this work, we present the first such provable exponential separation between quantum and quantum-inspired classical algorithms. We prove the separation for the basic problem of solving a linear system when the input matrix is well-conditioned and has sparse rows and columns.

Union volume estimation is a classical algorithmic problem. Given a family of objects O₁,...,O_n⊆ℝ^d, we want to approximate the volume of their union. In the special case where all objects are boxes (also known as hyperrectangles) this is known as Klee's measure problem. The state-of-the-art algorithm [Karp, Luby, Madras '89] for union volume estimation as well as Klee's measure problem in constant dimension d computes a (1+ε)-approximation with constant success probability by using a total of O(n/ε²) queries of the form (i) ask for the volume of O_i, (ii) sample a point uniformly at random from O_i, and (iii) query whether a given point is contained in O_i.
First, we show that if one can only interact with the objects via the aforementioned three queries, the query complexity of [Karp, Luby, Madras '89] is indeed optimal, i.e., Ω(n/ε²) queries are necessary. Our lower bound already holds for estimating the union of equiponderous axis-aligned polygons in ℝ², and even if the algorithm is allowed to inspect the coordinates of the points sampled from the polygons, and still holds when a containment query can ask containment of an arbitrary (not necessarily sampled) point.
Second, guided by the insights of the lower bound, we provide a more efficient approximation algorithm for Klee's measure problem improving the O(n/ε²) time to O((n+ε^-2)·lg^O(d)n). We achieve this improvement by exploiting the geometry of Klee's measure problem in various ways: (1) Since we have access to the boxes' coordinates, we can split the boxes into classes of boxes of similar shape. (2) Within each class, we show how to sample from the union of all boxes, by using orthogonal range searching. And (3) we exploit that boxes of different classes have small intersection, for most pairs of classes.

In boosting, we aim to leverage multiple weak learners to produce a strong learner. At the center of this paradigm lies the concept of building the strong learner as a voting classifier, which outputs a weighted majority vote of the weak learners. While many successful boosting algorithms, such as the iconic AdaBoost, produce voting classifiers, their theoretical performance has long remained sub-optimal: The best known bounds on the number of training examples necessary for a voting classifier to obtain a given accuracy has so far always contained at least two logarithmic factors above what is known to be achievable by general weak-to-strong learners. In this work, we break this barrier by proposing a randomized boosting algorithm that outputs voting classifiers whose generalization error contains a single logarithmic dependency on the sample size. We obtain this result by building a general framework that extends sample compression methods to support randomized learning algorithms based on sub-sampling.

Recent works on the parallel complexity of Boosting have established strong lower bounds on the tradeoff between the number of training rounds p and the total parallel work per round t. These works have also presented highly non-trivial parallel algorithms that shed light on different regions of this tradeoff. Despite these advancements, a significant gap persists between the theoretical lower bounds and the performance of these algorithms across much of the tradeoff space. In this work, we essentially close this gap by providing both improved lower bounds on the parallel complexity of weak-to-strong learners, and a parallel Boosting algorithm whose performance matches these bounds across the entire p vs. t compromise spectrum, up to logarithmic factors. Ultimately, this work settles the true parallel complexity of Boosting algorithms that are nearly sample-optimal.

Multi-distribution or collaborative learning involves learning a single predictor that works well across multiple data distributions, using samples from each during training. Recent research on multi-distribution learning, focusing on binary loss and finite VC dimension classes, has shown near-optimal sample complexity that is achieved with oracle efficient algorithms. That is, these algorithms are computationally efficient given an efficient ERM for the class. Unlike in classical PAC learning, where the optimal sample complexity is achieved with deterministic predictors, current multi-distribution learning algorithms output randomized predictors. This raises the question: can these algorithms be derandomized to produce a deterministic predictor for multiple distributions? Through a reduction to discrepancy minimization, we show that derandomizing multi-distribution learning is computationally hard, even when ERM is computationally efficient. On the positive side, we identify a structural condition enabling an efficient black-box reduction, converting existing randomized multi-distribution predictors into deterministic ones.

Boosting is an extremely successful idea, allowing one to combine multiple low accuracy classifiers into a much more accurate voting classifier. In this work, we present a new and surprisingly simple Boosting algorithm that obtains a provably optimal sample complexity. Sample optimal Boosting algorithms have only recently been developed, and our new algorithm has the fastest runtime among all such algorithms and is the simplest to describe: Partition your training data into 5 disjoint pieces of equal size, run AdaBoost on each, and combine the resulting classifiers via a majority vote. In addition to this theoretical contribution, we also perform the first empirical comparison of the proposed sample optimal Boosting algorithms. Our pilot empirical study suggests that our new algorithm might outperform previous algorithms on large data sets.

PAC learning, dating back to Valiant'84 and Vapnik and Chervonenkis'64,'74, is a classic model for studying supervised learning. In the agnostic setting, we have access to a hypothesis set H and a training set of labeled samples (x₁,y₁),...,(x_n,y_n)∈X×{-1,1} drawn i.i.d. from an unknown distribution D. The goal is to produce a classifier h : X→{-1,1} that is competitive with the hypothesis h
*
D
∈H having the least probability of mispredicting the label y of a new sample (x,y)~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 τ : =Pr_D[h
*
D
≠y], as a parameter. Concretely we show that ERM, and any other proper learning algorithm, is sub-optimal by a (ln(1/τ))^1/2 factor. We then complement this lower bound with the first learning algorithm achieving an optimal error for nearly the full range of τ. Our algorithm introduces several new ideas that we hope may find further applications in learning theory.

Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, which is clearly also a lower bound in the worst case. However, several works have shown how to solve this problem in sublinear time in expectation when the input graph is drawn from one of several classes of random graphs. In this work, we extend these results by giving sublinear time shortest path (and short path) algorithms for expander graphs. We thus identify a natural deterministic property of a graph (that is satisfied by typical random regular graphs) which suffices for sublinear time shortest paths. The algorithms are very simple, involving only bidirectional breadth first search and short random walks. We also complement our new algorithms by near-matching lower bounds.

While machine learning theory and theoretical computer science are both based on a solid mathematical foundation, the two research communities have a smaller overlap than what the proximity of the fields warrant. In this invited abstract, I will argue that traditional theoretical computer scientists have much to offer the learning theory community and vice versa. I will make this argument by telling a personal story of how I broadened my research focus to encompass learning theory, and how my TCS background has been extremely useful in doing so. It is my hope that this personal account may inspire more TCS researchers to tackle the many elegant and important theoretical questions that learning theory has to offer.

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing n elements and ensuring correctness with probability at least 1-δ, existing IBLT constructions require Ω(n(lg(1/δ)/lg(n)+1)) space and they crucially rely on fully random hash functions.
We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing n elements with a failure probability of at most δ, our data structure only requires O(n+lg(1/δ)lglg(1/δ)) space and O(lg(lg(n)/δ))-wise independent hash functions.
As a key technical ingredient we show that hashing n keys with any k-wise independent hash function h : U→[Cn] for some sufficiently large constant C guarantees with probability 1-2^-Ω(k) that at least n/2 keys will have a unique hash value. Proving this is highly non-trivial as k approaches n. We believe that the techniques used to prove this statement may be of independent interest.

Developing an optimal PAC learning algorithm in the realizable setting, where empirical risk minimization (ERM) is suboptimal, was a major open problem in learning theory for decades. The problem was finally resolved by Hanneke a few years ago. Unfortunately, Hanneke's algorithm is quite complex as it returns the majority vote of many ERM classifiers that are trained on carefully selected subsets of the data. It is thus a natural goal to determine the simplest algorithm that is optimal. In this work we study the arguably simplest algorithm that could be optimal: returning the majority vote of three ERM classifiers. We show that this algorithm achieves the optimal in-expectation bound on its error which is provably unattainable by a single ERM classifier. Furthermore, we prove a near-optimal high-probability bound on this algorithm's error. We conjecture that a better analysis will prove that this algorithm is in fact optimal in the high-probability regime.

We provide efficient replicable algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and Sorrell (STOC'22). We design the first dimension-independent replicable algorithms for this task which runs in polynomial time, is proper, and has strictly improved sample complexity compared to the one achieved by Impagliazzo et al.'22 with respect to all the relevant parameters. Moreover, our first algorithm has sample complexity that is optimal with respect to the accuracy parameter ε. We also design an SGD-based replicable algorithm that, in some parameters' regimes, achieves better sample and time complexity than our first algorithm.
Departing from the requirement of polynomial time algorithms, using the DP-to-Replicability reduction of Bun et al. (STOC'23), we show how to obtain a replicable algorithm for large-margin halfspaces with improved sample complexity with respect to the margin parameter τ, but running time doubly exponential in 1/τ² and worse sample complexity dependence on ε than one of our previous algorithms. We then design an improved algorithm with better sample complexity than all three of our previous algorithms and running time exponential in 1/τ².

The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. It supports embedding a set of n points in ℝ^d into m=O(ε^-2lgn) dimensions while preserving all pairwise distances to within 1±ε. Each input point x is embedded to Ax, where A is an m×d matrix having s non-zeros per column, allowing for an embedding time of O(s||x||₀).
Since the sparsity of A governs the embedding time, much work has gone into improving the sparsity s. The current state-of-the-art by Kane and Nelson (JACM'14) shows that s=O(ε^-1lgn) suffices. This is almost matched by a lower bound of s=Ω(ε^-1lgn/lg(1/ε)) by Nelson and Nguyen (STOC'13). Previous work thus suggests that we have near-optimal embeddings.
In this work, we revisit sparse embeddings and identify a loophole in the lower bound. Concretely, it requires d≥n, which in many applications is unrealistic. We exploit this loophole to give a sparser embedding when d=o(n), achieving s=O(ε^-1(lgn/lg(1/ε)+lg^2/3nlg^1/3d)). We also complement our analysis by strengthening the lower bound of Nelson and Nguyen to hold also when d≪n, thereby matching the first term in our new sparsity upper bound. Finally, we also improve the sparsity of the best oblivious subspace embeddings for optimal embedding dimensionality.

We present a simple and provably optimal non-adaptive cell probe data structure for the static dictionary problem. Our data structure supports storing a set of n key-value pairs from [u]×[u] using s words of space and answering key lookup queries in t=O(lg(u/n)/lg(s/n)) non-adaptive probes. This generalizes a solution to the membership problem (i.e., where no values are associated with keys) due to Buhrman et al. and matches a recent lower bound by Persiano and Yeo.
Using the ideas underlying our data structure, we also obtain the first implementation of a n-wise independent family of hash functions with optimal evaluation time in the cell probe model.

The aim of boosting is to convert a sequence of weak learners into a strong learner. At their heart, these methods are fully sequential. In this paper, we investigate the possibility of parallelizing boosting. Our main contribution is a strong negative result, implying that significant parallelization of boosting requires an exponential blow-up in the total computing resources needed for training.

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even referred to him as a "scientific charlatan".
    In the game Kronecker maintains a list of m binary vectors, each of length n, and Cantor's goal is to produce a new binary vector which is different from each of Kronecker's vectors, or prove that no such vector exists. Cantor does not see Kronecker's vectors but he is allowed to ask queries of the form
    "What is bit number j of vector number i?"
    What is the minimal number of queries with which Cantor can achieve his goal? How much better can Cantor do if he is allowed to pick his queries adaptively, based on Kronecker's previous replies?
    The case when m=n is solved by diagonalization using n (non-adaptive) queries. We study this game more generally, and prove an optimal bound in the adaptive case and nearly tight upper and lower bounds in the non-adaptive case.

We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphabets.
We show that this barrier appears in many variations throughout the algorithmic literature by introducing a framework of Colored Walk problems. These yield fine-grained equivalent formulations of the NFA Acceptance problem as problems concerning detection of an s-t-walk with a prescribed color sequence in a given edge- or node-colored graph. For NFA Acceptance on sparse NFAs (or equivalently, Colored Walk in sparse graphs), a tight lower bound under the Strong Exponential Time Hypothesis has been rediscovered several times in recent years. We show that our hardness hypothesis, which concerns dense NFAs, has several interesting implications:

It gives a tight lower bound for Context-Free Language Reachability. This proves conditional optimality for the class of 2NPDA-complete problems, explaining the cubic bottleneck of interprocedural program analysis.
It gives a tight (n+nm^1/3)^1-o(1) lower bound for the Word Break problem on strings of length n and dictionaries of total size m.
It implies the popular OMv hypothesis. Since the NFA acceptance problem is a static (i.e., non-dynamic) problem, this provides a static reason for the hardness of many dynamic problems.

Thus, a proof of the NFA Acceptance hypothesis would resolve several interesting barriers. Conversely, a refutation of the NFA Acceptance hypothesis may lead the way to attacking the current barriers observed for Context-Free Language Reachability, the Word Break problem and the growing list of dynamic problems proven hard under the OMv hypothesis.

In this work, we prove a ∼Ω(lg^3/2n) unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.

Determining the optimal sample complexity of PAC learning in the realizable setting was a central open problem in learning theory for decades. Finally, the seminal work by Hanneke (2016) gave an algorithm with a provably optimal sample complexity. His algorithm is based on a careful and structured sub-sampling of the training data and then returning a majority vote among hypotheses trained on each of the sub-samples. While being a very exciting theoretical result, it has not had much impact in practice, in part due to inefficiency, since it constructs a polynomial number of sub-samples of the training data, each of linear size.
In this work, we prove the surprising result that the practical and classic heuristic bagging (a.k.a. bootstrap aggregation), due to Breiman (1996), is in fact also an optimal PAC learner. Bagging pre-dates Hanneke's algorithm by twenty years and is taught in most undergraduate machine learning courses. Moreover, we show that it only requires a logarithmic number of sub-samples to reach optimality.

AdaBoost is a classic boosting algorithm for combining multiple inaccurate classifiers produced by a weak learner, to produce a strong learner with arbitrarily high accuracy when given enough training data. Determining the optimal number of samples necessary to obtain a given accuracy of the strong learner, is a basic learning theoretic question. Larsen and Ritzert (NeurIPS'22) recently presented the first provably optimal weak-to-strong learner. However, their algorithm is somewhat complicated and it remains an intriguing question whether the prototypical boosting algorithm AdaBoost also makes optimal use of training samples. In this work, we answer this question in the negative. Concretely, we show that the sample complexity of AdaBoost, and other classic variations thereof, are sub-optimal by at least one logarithmic factor in the desired accuracy of the strong learner.

The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP'09) embeds a set of n points in d-dimensional Euclidean space into optimal k=O(ε^-2lnn) dimensions, while preserving all pairwise distances to within a factor (1±ε). The Fast JL transform supports computing the embedding of a data point in O(dlnd+kln²n) time, where the dlnd term comes from multiplication with a d×d Hadamard matrix and the kln²n term comes from multiplication with a sparse k×d matrix. Despite the Fast JL transform being more than a decade old, it is one of the fastest dimensionality reduction techniques for many tradeoffs between ε,d and n.
In this work, we give a surprising new analysis of the Fast JL transform, showing that the kln²n term in the embedding time can be improved to (kln²n)/α for an α=Ω(min{ε^-1ln(1/ε),lnn}). The improvement follows by using an even sparser matrix. We also complement our improved analysis with a lower bound showing that our new analysis is in fact tight.

We formalize and study the problem of distributed shuffling in adversarial environments. In this setting, there are m shufflers that have access to a public bulletin board that stores a vector (c₁,...,c_n) of re-randomizable commitments. The shufflers repeatedly read k of the n commitments, with k potentially much smaller than n, and shuffle them. An adversary has the ability to initially corrupt and then track some of the commitments throughout the shuffles and can adaptively corrupt a bounded number of shufflers in every single round. The goal of the distributed shuffling protocol is to hide the output locations of commitments that are not corrupted by the adversary.
We present and analyze a protocol that solves this problem with essentially optimal shuffling complexity. As an exemplary data point, our protocol can shuffle a list of length n with shuffles of size k, where k∈Ω(lg²n), in the presence of an adversary that can corrupt 4n/5 many shufflers in each round and can corrupt 4n/5 commitments in the input vector. Our m-party shuffling protocol with m∈Ω(n/k) terminates in O(lgn) rounds. We provide numerical benchmarks that validate our theoretically proven guarantees and in fact show that the number of rounds is not just theoretically, but also concretely small.
Our shuffling protocol can either improve efficiency or lead to more secure solutions in multiple research domains, such as the design of mix-nets, single secret leader election protocols, and electronic voting.

We study the task of obliviously compressing a vector comprised of n ciphertexts of size ξ bits each, where at most t of the corresponding plaintexts are non-zero. This problem commonly features in applications involving encrypted outsourced storages, such as searchable encryption or oblivious message retrieval. We present two new algorithms with provable worst-case guarantees, solving this problem by using only homomorphic additions and multiplications by constants. Both of our new constructions improve upon the state of the art asymptotically and concretely.
Our first construction, based on sparse polynomials, is perfectly correct and the first to achieve an asymptotically optimal compression rate by compressing the input vector into O(tξ) bits. Compression can be performed homomorphically by performing O(nlgn) homomorphic additions and multiplications by constants. The main drawback of this construction is a decoding complexity of Ω(n^1/2).
Our second construction is based on a novel variant of invertible bloom lookup tables and is correct with probability 1-2^-κ. It has a slightly worse compression rate compared to our first construction as it compresses the input vector into O(ξκt/lgt) bits, where κ≥lgt. In exchange, both compression and decompression of this construction are highly efficient. The compression complexity is dominated by O(nκ) homomorphic additions and multiplications by constants. The decompression complexity is dominated by O(ξκt/lgt) decryption operations and equally many inversions of a pseudorandom permutation.

The Johnson-Lindenstrauss transform allows one to embed a dataset of n points in ℝ^d into ℝ^m, while preserving the pairwise distance between any pair of points up to a factor (1±ε), provided that m=Ω(ε^-2lgn). The transform has found an overwhelming number of algorithmic applications, allowing to speed up algorithms and reducing memory consumption at the price of a small loss in accuracy. A central line of research on such transforms, focus on developing fast embedding algorithms, with the classic example being the Fast JL transform by Ailon and Chazelle. All known such algorithms have an embedding time of Ω(dlgd), but no lower bounds rule out a clean O(d) embedding time. In this work, we establish the first non-trivial lower bounds (of magnitude Ω(mlgm)) for a large class of embedding algorithms, including in particular most known upper bounds.

Efficiently computing low discrepancy colorings of various set systems, has been studied extensively since the breakthrough work by Bansal (FOCS 2010), who gave the first polynomial time algorithms for several important settings, including for general set systems, sparse set systems and for set systems with bounded hereditary discrepancy. The hereditary discrepancy of a set system, is the maximum discrepancy over all set systems obtainable by deleting a subset of the ground elements. While being polynomial time, Bansal's algorithms were not practical, with e.g. his algorithm for the hereditary setup running in time Ω(mn^4.5) for set systems with m sets over a ground set of n elements. More efficient algorithms have since then been developed for general and sparse set systems, however, for the hereditary case, Bansal's algorithm remains state-of-the-art. In this work, we give a significantly faster algorithm with hereditary guarantees, running in O(mn²lg(2+m/n)+n³) time. Our algorithm is based on new structural insights into set systems with bounded hereditary discrepancy. We also implement our algorithm and show experimentally that it computes colorings that are significantly better than random and finishes in a reasonable amount of time, even on set systems with thousands of sets over a ground set of thousands of elements.

The 3SUM-Indexing problem was introduced as a data structure version of the 3SUM problem, with the goal of proving strong conditional lower bounds for static data structures via reductions. Ideally, the conjectured hardness of 3SUM-Indexing should be replaced by an unconditional lower bound. Unfortunately, we are far from proving this, with the strongest current lower bound being a logarithmic query time lower bound by Golovnev et al. from STOC'20. Moreover, their lower bound holds only for non-adaptive data structures and they explicitly asked for a lower bound for adaptive data structures. Our main contribution is precisely such a lower bound against adaptive data structures. As a secondary result, we also strengthen the non-adaptive lower bound of Golovnev et al. and prove strong lower bounds for 2-bit-probe non-adaptive 3SUM-Indexing data structures via a completely new approach that we find interesting in its own right.

The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We present a new algorithm that constructs a strong learner from a weak learner but uses less training data than AdaBoost and all other weak to strong learners to achieve the same generalization bounds. A sample complexity lower bound shows that our new algorithm uses the minimum possible amount of training data and is thus optimal. Hence, this work settles the sample complexity of the classic problem of constructing a strong learner from a weak learner.

Given a set of n points in d dimensions, the Euclidean k-means problem (resp. the Euclidean k-median problem) consists of finding k centers such that the sum of squared distances (resp. sum of distances) from every point to its closest center is minimized. The arguably most popular way of dealing with this problem in the big data setting is to first compress the data by computing a weighted subset known as a coreset and then run any algorithm on this subset. The guarantee of the coreset is that for any candidate solution, the ratio between coreset cost and the cost of the original instance is less than a (1±ε) factor. The current state of the art coreset size is Õ(min(k²·ε^-2,k·ε^-4)) for Euclidean k-means and Õ(min(k²·ε^-2,k·ε^-3)) for Euclidean k-median. The best known lower bound for both problems is Ω(kε^-2). In this paper, we improve the upper bounds Õ(min(k^3/2·ε^-2,k·ε^-4)) for k-means and Õ(min(k^4/3·ε^-2,k·ε^-3)) for k-median. In particular, ours is the first provable bound that breaks through the k² barrier while retaining an optimal dependency on ε.

In colored range counting (CRC), the input is a set of points where each point is assigned a ``color'' (or a ``category'') and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data.
However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exists or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through reductions from the orthogonal vectors problem.

Given a set of points in a metric space, the (k,z)-clustering problem consists of finding a set of k points called centers, such that the sum of distances raised to the power of z of every data point to its closest center is minimized. Special cases include the famous k-median problem (z=1) and k-means problem (z=2). The k-median and k-means problems are at the heart of modern data analysis and massive data applications have given raise to the notion of coreset: a small (weighted) subset of the input point set preserving the cost of any solution to the problem up to a multiplicative (1±ε) factor, hence reducing from large to small scale the input to the problem.
While there has been an intensive effort to understand what is the best coreset size possible for both problems in various metric spaces, there is still a significant gap between the state-of-the-art upper and lower bounds. In this paper, we make progress on both upper and lower bounds, obtaining tight bounds for several cases, namely:

In finite n point general metrics, any coreset must consist of Ω(klgn/ε²) points. This improves on the Ω(klgn/ε) lower bound of Braverman, Jiang, Krauthgamer, and Wu [ICML'19] and matches the upper bounds proposed for k-median by Feldman and Langberg [STOC'11] and k-means by Cohen-Addad, Saulpic, and Schwiegelshohn [STOC'21] up to polylog factors.
For doubling metrics with doubling constant D, any coreset must consist of Ω(kD/ε²) points. This matches the k-median and k-means upper bounds by Cohen-Addad, Saulpic, and Schwiegelshohn [STOC'21] up to polylog factors.
In d-dimensional Euclidean space, any coreset for (k,z) clustering requires Ω(k/ε²) points. This improves on the Ω(k/(ε)^1/2) lower bound of Baker, Braverman, Huang, Jiang, Krauthgamer, and Wu [ICML'20] for k-median and complements the Ω(kmin(d,2^z/20)) lower bound of Huang and Vishnoi [STOC'20].

We complement our lower bound for d-dimensional Euclidean space with the construction of a coreset of size Õ(k/ε²·min(ε^-z,k)). This improves over the Õ(k²ε^-4) upper bound for general power of z proposed by Braverman Jiang, Krauthgamer, and Wu [SODA'21] and over the Õ(k/ε⁴) upper bound for k-median by Huang and Vishnoi [STOC'20]. In fact, ours is the first construction breaking through the ε^-2·min(d,ε^-2) barrier inherent in all previous coreset constructions. To do this, we employ a novel chaining based analysis that may be of independent interest. Together our upper and lower bounds for k-median in Euclidean spaces are tight up to a factor O(ε^-1polylog(k/ε)).

It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used, not much is known in terms of bounds on their performance. The question of whether the JL method is optimal for practical measures of distortion was recently raised in [BFN19] (NeurIPS'19). They provided upper bounds on its quality for a wide range of practical measures and showed that indeed these are best possible in many cases. Yet, some of the most important cases, including the fundamental case of average distortion were left open. In particular, they show that the JL transform has 1+ε average distortion for embedding into k-dimensional Euclidean space, where k=O(1/ε²), and for more general q-norms of distortion, k=O(max{1/ε²,q/ε}), whereas tight lower bounds were established only for large values of q via reduction to the worst case.
    In this paper we prove that these bounds are best possible for any dimensionality reduction method, for any 1≤q≤O(lg(2ε²n)/ε) and ε≥1/n^1/2, where n is the size of the subset of Euclidean space.
    Our results also imply that the JL method is optimal for various distortion measures commonly used in practice, such as stress, energy and relative error. We prove that if any of these measures is bounded by ε then k=Ω(1/ε²), for any ε≥1/n^1/2, matching the upper bounds of [BFN19] and extending their tightness results for the full range moment analysis.
    Our results may indicate that the JL dimensionality reduction method should be considered more often in practical applications, and the bounds we provide for its quality should be served as a measure for comparison when evaluating the performance of other methods and heuristics.

Property-preserving hash functions allow for compressing long inputs x₀ and x₁ into short hashes h(x₀) and h(x₁) in a manner that allows for computing a predicate P(x₀,x₁) given only the two hash values without having access to the original data. Such hash functions are said to be adversarially robust if an adversary that gets to pick x₀ and x₁ after the hash function has been sampled, cannot find inputs for which the predicate evaluated on the hash values outputs the incorrect result.
    In this work we construct robust property-preserving hash functions for the hamming-distance predicate which distinguishes inputs with a hamming distance at least some threshold t from those with distance less than t. The security of the construction is based on standard lattice hardness assumptions.
    Our construction has several advantages over the best known previous construction by Fleischhacker and Simkin (Eurocrypt 2021). Our construction relies on a single well-studied hardness assumption from lattice cryptography whereas the previous work relied on a newly introduced family of computational hardness assumptions. In terms of computational effort, our construction only requires a small number of modular additions per input bit, whereas the work of Fleischhacker and Simkin required several exponentiations per bit as well as the interpolation and evaluation of high-degree polynomials over large fields. An additional benefit of our construction is that the description of the hash function can be compressed to λ bits assuming a random oracle. Previous work has descriptions of length O(ℓλ) bits for input bit-length ℓ, which has a secret structure and thus cannot be compressed.
    We prove a lower bound on the output size of any property-preserving hash function for the hamming distance predicate. The bound shows that the size of our hash value is not far from optimal.

In this paper, we revisit the classic CountSketch method, which is a sparse, random projection that transforms a (high-dimensional) Euclidean vector v to a vector of dimension (2t-1)s, where t,s>0 are integer parameters. It is known that even for t=1, a CountSketch allows estimating coordinates of v with variance bounded by ||v||
2
2
/s. For t>1, the estimator takes the median of 2t-1 independent estimates, and the probability that the estimate is off by more than 2||v||₂/s^1/2 is exponentially small in t. This suggests choosing t to be logarithmic in a desired inverse failure probability. However, implementations of CountSketch often use a small, constant t. Previous work only predicts a constant factor improvement in this setting.
Our main contribution is a new analysis of CountSketch, showing an improvement in variance to O(min{||v||
2
1
/s²,||v||
2
2
/s}) when t>1. That is, the variance decreases proportionally to s^-2, asymptotically for large enough s. We also study the variance in the setting where an inner product is to be estimated from two CountSketches. This finding suggests that the Feature Hashing method, which is essentially identical to CountSketch but does not make use of the median estimator, can be made more reliable at a small cost in settings where using a median estimator is possible.
We confirm our theoretical findings in experiments and thereby help justify why a small constant number of estimates often suffice in practice. Our improved variance bounds are based on new general theorems about the variance and higher moments of the median of i.i.d. random variables that may be of independent interest.

Consider a sender S and a group and of n recipients. S holds a secret message m of length l bits and the goal is to allow S to create a secret sharing of m with privacy threshold t among the recipients, by broadcasting a single message c to the recipients. Our goal is to do this with information theoretic security in a model with a simple form of correlated randomness. Namely, for each subset A of recipients of size q, S may share a secret random bit string with all recipients in A. We call this Broadcast Secret-Sharing (BSS) with parameters l, n, t and q.
    Our main question is: how large must c be, as a function of the parameters? We show that ((n-t)/q)l is a lower bound, and we show an upper bound of (n(t+1)/(q+t)-t)l, matching the lower bound whenever t=0, or when q=1 or n-t.
    When q=n-t, the size of c is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires S to share a key with every subset of size n-t. We show that this overhead cannot be avoided when c has minimal size.
    We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes ((n-t)/q)λ+l-negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes (n(t+1)/(q+t)-t)λ+l.
    BSS can be applied directly to secret-key threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and non-interactive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for non-interactive secret sharing becomes an ad hoc threshold encryption (ATE) scheme, which is a threshold encryption scheme with no trusted setup beyond a PKI. Our upper bounds imply new ATE schemes, and our lower bound becomes a lower bound on the ciphertext size in any ATE scheme that uses a key exchange functionality and no other cryptographic primitives.

In a landmark paper, Patrascu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth of new and previous lower bounds via reductions. These lower bounds are tight for numerous static data structure problems. Moreover, he also showed that reachability in the butterfly graph reduces to dynamic marked ancestor, a classic problem used to prove lower bounds for dynamic data structures. Unfortunately, Patrascu's reduction to marked ancestor loses a lglgn factor and therefore falls short of fully recovering all the previous dynamic data structure lower bounds that follow from marked ancestor. In this paper, we revisit Patrascu's work and give a new lossless reduction to dynamic marked ancestor, thereby establishing reachability in the butterfly graph as a single seed problem from which a range of tight static and dynamic data structure lower bounds follow.

In this work, we present the first asymptotically optimal oblivious priority queue, which matches the lower bound of Jacob, Larsen, and Nielsen (SODA'19). Our construction is conceptually simple, statistically secure, and has small hidden constants. We illustrate the power of our optimal oblivious priority queue by presenting a conceptually equally simple construction of statistically secure offline ORAMs with O(lgn) bandwidth overhead.

Social networks involve both positive and negative relationships, which can be captured in signed graphs. The edge sign prediction problem aims to predict whether an interaction between a pair of nodes will be positive or negative. We provide theoretical results for this problem that motivate natural improvements to recent heuristics. The edge sign prediction problem is related to correlation clustering; a positive relationship means being in the same cluster. We consider the following model for two clusters: we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability 0<q<1/2. Let δ=1-2q be the bias. We provide an algorithm that recovers all signs correctly with high probability in the presence of boise with O(nlgn/δ²+lg²n/δ⁶) queries. This is the best known result for this problem for all but tiny δ, improving on the recent work of Mazumdar and Saha. We also provide an algorithm that performs O(nlgn/δ⁴) queries, and uses breadth first search as its main algorithmic primitive. While both the running time and number of queries for this algorithm are sub-optimal, our result relies on novel theoretical techniques, and naturally suggests the use of edge-disjoint paths as a feature for predicting signs in online social networks. Correspondingly, we experiment with using edge disjoint s-t paths of short length as a feature for predicting the sign of edge (s,t) in real-world signed networks. Empirical findings suggest that the use of such paths improves the classification accuracy, especially for pairs of nodes with no common neighbors.

Boosting is one of the most successful ideas in machine learning, achieving great practical performance with little fine-tuning. The success of boosted classifiers is most often attributed to improvements in margins. The focus on margin explanations was pioneered in the seminal work by Schapire et al. (1998) and has culminated in the k'th margin generalization bound by Gao and Zhou (2013), which was recently proved to be near-tight for some data distributions (Grønlund et al. 2019). In this work, we first demonstrate that the k'th margin bound is inadequate in explaining the performance of state-of-the-art gradient boosters. We then explain the short comings of the k'th margin bound and prove a stronger and more refined margin-based generalization bound for boosted classifiers that indeed succeeds in explaining the performance of modern gradient boosters. Finally, we improve upon the recent generalization lower bound by Grønlund et al. (2019).

In this work, we consider the construction of oblivious RAMs (ORAM) in a setting with multiple servers and the adversary may corrupt a subset of the servers. We present an Ω(lgn) overhead lower bound for any k-server ORAM that limits any PPT adversary to distinguishing advantage at most 1/4k when only one server is corrupted. In other words, if one insists on negligible distinguishing advantage, then multi-server ORAMs cannot be faster than single-server ORAMs even with polynomially many servers of which only one unknown server is corrupted. Our results apply to ORAMs that may err with probability at most 1/8 as well as scenarios where the adversary corrupts larger subsets of servers. We also extend our lower bounds to other important data structures including oblivious stacks, queues, deques, priority queues and search trees.

A secret sharing scheme allows a dealer to distribute shares of a secret among a set of n parties P={p₁,...,p_n} such that any authorized subset of parties can reconstruct the secret, yet any unauthorized subset learns nothing about it. The family A⊆2^P of all authorized subsets is called the access structure. Classic results show that if A contains precisely all subsets of cardinality at least t, then there exists a secret sharing scheme where the length of the shares is proportional to lgn bits plus the length of the secret. However, for general access structures, the best known upper bounds have shares of length exponential in n, whereas the strongest lower bound shows that the shares must have length at least n/lgn. Beimel conjectured that the exponential upper bound is tight, but proving it has so far resisted all attempts. In this paper we make progress towards proving the conjecture by showing that there exists an access structure A, such that any secret sharing scheme for A must have either exponential share length, or the function used for reconstructing the secret by authorized parties must have an exponentially long description. As an example corollary, we conclude that if one insists that authorized parties can reconstruct the secret via a constant fan-in boolean circuit of size polynomial in the share length, then there exists an access structure that requires a share length that is exponential in n.

Support Vector Machines (SVMs) are among the most fundamental tools for binary classification. In its simplest formulation, an SVM produces a hyperplane separating two classes of data using the largest possible margin to the data. The focus on maximizing the margin has been well motivated through numerous generalization bounds. In this paper, we revisit and improve the classic generalization bounds in terms of margins. Furthermore, we complement our new generalization bound by a nearly matching lower bound, thus almost settling the generalization performance of SVMs in terms of margins.

We consider the following problem, which is useful in applications such as joint image and shape alignment. The goal is to recover n discrete variables g_i∈{0,...,k-1} (up to some global offset) given noisy observations of a set of their pairwise differences {(g_i-g_j) mod k}; specifically, with probability 1/k+δ for some δ>0 one obtains the correct answer, and with the remaining probability one obtains a uniformly random incorrect answer. We consider a learning-based formulation where one can perform a query to observe a pairwise difference, and the goal is to perform as few queries as possible while obtaining the exact joint alignment. We provide an easy-to-implement, time efficient algorithm that performs O(nlgn/(kδ²)) queries, and recovers the joint alignment with high probability. We also show that our algorithm is optimal by proving a general lower bound that holds for all non-adaptive algorithms. Our work improves significantly recent work by Chen and Candes, who view the problem as a constrained principal components analysis problem that can be solved using the power method. Specifically, our approach is simpler both in the algorithm and the analysis, and provides additional insights into the problem structure.

Clustering, i.e., finding groups in the data, is a problem that permeates multiple fields of science and engineering. Recently, the problem of clustering with a noisy oracle has drawn attention due to various applications including crowdsourced entity resolution, and predicting signs of interactions in large-scale online social networks. Here, we consider the following fundamental model for two clusters as proposed by Mitzenmacher and Tsourakakis, and Mazumdar and Saha; there exist n items, belonging to two unknown groups. We are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability 0 < q < 1/2. Let 1>δ=1-2q>0 be the bias.
In this work, we provide a polynomial time algorithm that recovers all signs correctly with high probability in the presence of noise with O(nlgn/δ²+lg²n/δ⁶) queries. This is the best known result for this problem for all but tiny δ, improving on the current state-of-the-art due to Mazumdar and Saha.

We prove an Ω(dlgn/(lglgn)²) lower bound on the dynamic cell-probe complexity of statistically oblivious approximate-near-neighbor search (ANN) over the d-dimensional Hamming cube. For the natural setting of d=Θ(lgn), our result implies an ∼Ω(lg²n) lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for ANN. This is the first super-logarithmic unconditional lower bound for ANN against general (non black-box) data structures. We also show that any oblivious static data structure for decomposable search problems (like ANN) can be obliviously dynamized with O(lgn) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).

Boosting is one of the most successful ideas in machine learning. The most well-accepted explanations for the low generalization error of boosting algorithms such as AdaBoost stem from margin theory. The study of margins in the context of boosting algorithms was initiated by Schapire, Freund, Bartlett and Lee (1998) and has inspired numerous boosting algorithms and generalization bounds. To date, the strongest known generalization (upper bound) is the kth margin bound of Gao and Zhou (2013). Despite the numerous generalization upper bounds that have been proved over the last two decades, nothing is known about the tightness of these bounds. In this paper, we give the first margin-based lower bounds on the generalization error of boosted classifiers. Our lower bounds nearly match the kth margin bound and thus almost settle the generalization performance of boosted classifiers in terms of margins.

We prove a lower bound on the communication complexity of unconditionally secure multiparty computation, both in the standard model with n=2t+1 parties of which t are corrupted, and in the preprocessing model with n=t+1. In both cases, we show that for any g∈ℕ there exists a Boolean circuit C with g gates, where any secure protocol implementing C must communicate Ω(ng) bits, even if only passive and statistical security is required. The results easily extends to constructing similar circuits over any fixed finite field. This shows that for all sizes of circuits, the O(n) overhead of all known protocols when t is maximal is inherent. It also shows that security comes at a price: the circuit we consider could namely be computed among n parties with communication only O(g) bits if no security was required. Our results extend to the case where the threshold t is suboptimal. For the honest majority case, this shows that the known optimizations via packed secret-sharing can only be obtained if one accepts that the threshold is t=(1/2-c)n for a constant c. For the honest majority case, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor lgn off for Boolean circuits).

Boosting algorithms produce a classifier by iteratively combining base hypotheses. It has been observed experimentally that the generalization error keeps improving even after achieving zero training error. One popular explanation attributes this to improvements in margins. A common goal in a long line of research, is to maximize the smallest margin using as few base hypotheses as possible, culminating with the AdaBoostV algorithm by (Rätsch and Warmuth [JMLR'04]). The AdaBoostV algorithm was later conjectured to yield an optimal trade-off between number of hypotheses trained and the minimal margin over all training points (Nie et al. [JMLR'13]). Our main contribution is a new algorithm refuting this conjecture. Furthermore, we prove a lower bound which implies that our new algorithm is optimal.

Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, by Fürer, shows that two n-bit numbers can be multiplied via a boolean circuit of size O(nlgn·4^{lg^*n}), where lg^*n is the very slowly growing iterated logarithm. In this work, we prove that if a central conjecture in the area of network coding is true, then any constant degree boolean circuit for multiplication must have size Ω(nlgn), thus almost completely settling the complexity of multiplication circuits. We additionally revisit classic conjectures in circuit complexity, due to Valiant, and show that the network coding conjecture also implies one of Valiant's conjectures.

Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer's main memory; thus external memory sorting algorithms, first introduced by Aggarwal and Vitter (1988), are often used. The complexity of comparison based external memory sorting has been understood for decades by now, however the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of n integer keys of Θ(lgn) bits each in O(n) time using the classic Radix Sort algorithm, however in external memory, there are no faster integer sorting algorithms known than the simple comparison based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades.
In this paper, we present a tight conditional lower bound on the complexity of external memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs.
The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the memory access pattern is fixed and independent of the input data). Unfortunately obliviousness is a strong limitations, especially for integer sorting: we show that the Li and Li conjecture implies an Ω(nlgn) lower bound for internal memory oblivious sorting when the keys are Θ(lgn) bits. This is in sharp contrast to the classic (non-oblivious) Radix Sort algorithm. Indeed going beyond obliviousness is highly non-trivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external memory integer sorting.

In discrepancy minimization problems, we are given a family of sets F={S₁,...,S_m}, with each S_i∈F a subset of some universe U={u₁,...,u_n} of n elements. The goal is to find a coloring χ : U→{-1,+1} of the elements of U such that each set S∈F is colored as evenly as possible. Two classic measures of discrepancy are ℓ_∞-discrepancy defined as disc_∞(F,χ) : =max_S∈F|Σ_{u_i∈S}χ(u_i)| andℓ₂-discrepancy defined as disc₂(F,χ) : =((1/|F|)Σ_S∈F(Σ_{u_i∈S}χ(u_i))²)^1/2. Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring χ such that disc_∞(F,χ)=O(lgn·herdisc_∞(F)) where herdisc_∞(F) is the hereditary ℓ_∞-discrepancy of F. We complement his work by giving a clean and simple O((m+n)n²) time algorithm for finding a coloring χ such disc₂(F,χ)=O((lgn)^1/2·herdisc₂(F)) where herdisc₂(F) is the hereditary ℓ₂-discrepancy of F. Interestingly, our algorithm avoids solving an SDP and instead relies simply on computing eigendecompositions of matrices. Moreover, we use some of the ideas in our algorithm to speed up the Edge-Walk algorithm by Lovett and Meka [SICOMP'15] for non-square matrices.
To prove that our algorithm has the claimed guarantees, we also prove new inequalities relating both herdisc_∞ and herdisc₂ to the eigenvalues of the incidence matrix corresponding to F. Our inequalities improve over previous work by Chazelle and Lvov [SCG'00] and by Matousek, Nikolov and Talwar [SODA'15+SCG'15]. We believe these inequalities are of independent interest as powerful tools for proving hereditary discrepancy lower bounds. Finally, we also implement our algorithm and show that it far outperforms random sampling of colorings in practice. Moreover, the algorithm finishes in a reasonable amount of time on matrices of sizes up to 10000×10000.

An oblivious data structure is a data structure where the memory access patterns reveals no information about the operations performed on it. Such data structures were introduced by Wang et al. [ACM SIGSAC'14] and are intended for situations where one wishes to store the data structure at an untrusted server. One way to obtain an oblivious data structure is simply to run a classic data structure on an oblivious RAM (ORAM). With the current best ORAM implementations, this results in an overhead of ω(lgn) for the most natural setting of parameters. Moreover, a recent lower bound for ORAMs by Larsen and Nielsen [CRYPTO'18] show that they always incur an overhead of at least Ω(lgn) if used in a black box manner. To circumvent the current ω(lgn) overhead, researchers have instead studied classic data structure problems more directly and have obtained efficient solutions for many such problems such as stacks, queues, deques, priority queues and search trees. However, none of these data structures process operations faster than Θ(lgn), leaving open the question of whether even faster solutions exist. In this paper, we rule out this possibility by proving Ω(lgn) lower bounds for oblivious stacks, queues, deques, priority queues and search trees.

A priority queue is a fundamental data structure that maintains a dynamic set of (key, priority)-pairs and supports Insert, Delete, ExtractMin and DecreaseKey operations. In the external memory model, the current best priority queue supports each operation in amortized O((1/B)lg(N/B)) I/Os. If the DecreaseKey operation does not need to be supported, one can design a more efficient data structure that supports the Insert, Delete and ExtractMin operations in O((1/B)lg(N/B)/lg(M/B)) I/Os. A recent result shows that a degradation in performance is inevitable by proving a lower bound of Ω((1/B)lgB/lglgN) I/Os for priority queues with DecreaseKeys. In this paper we tighten the gap between the lower bound and the upper bound by proposing a new priority queue which supports the DecreaseKey operation and has an expected amortized I/O complexity of O((1/B)lg(N/B)/lglgN). Our result improves the external memory priority queue with DecreaseKeys for the first time in over a decade, and also gives the fastest external memory single source shortest path algorithm.

Feature hashing, also known as the hashing trick, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix A : ℝⁿ→ℝ^m (where m≪n) in order to reduce the dimension of the data from n to m while approximately preserving the Euclidean norm. Every column of A contains exactly one non-zero entry, equals to either -1 or 1.
Weinberger et al. showed tail bounds on ||Ax||
2
2
. Specifically they showed that for every ε,δ, if ||x||_∞/||x||₂ is sufficiently small, and m is sufficiently large, then

Pr[|||Ax||
2
2
-||x||
2
2
|<ε||x||
2
2
]≥1-δ.

These bounds were later extended by Dasgupta et al. (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters ||x||_∞/||x||₂,m,ε,δ remained an open question.
We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants "hiding" in the asymptotic notation are, in fact, very close to 1, thus further illustrating the tightness of the presented bounds in practice.

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM'96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The main performance metric of an ORAM is the bandwidth overhead, i.e., the multiplicative factor extra memory blocks that must be accessed to hide the operation sequence. In their seminal paper introducing the ORAM, Goldreich and Ostrovsky proved an amortized Ω(lgn) bandwidth overhead lower bound for ORAMs with memory size n. Their lower bound is very strong in the sense that it applies to the ``offline'' setting in which the ORAM knows the entire sequence of operations ahead of time.
However, as pointed out by Boyle and Naor [ITCS'16] in the paper ``Is there an oblivious RAM lower bound?'', there are two caveats with the lower bound of Goldreich and Ostrovsky: (1) it only applies to ``balls in bins'' algorithms, i.e., algorithms where the ORAM may only shuffle blocks around and not apply any sophisticated encoding of the data, and (2), it only applies to statistically secure constructions. Boyle and Naor showed that removing the ``balls in bins'' assumption would result in super linear lower bounds for sorting circuits, a long standing open problem in circuit complexity. As a way to circumventing this barrier, they also proposed a notion of an ``online'' ORAM, which is an ORAM that remains secure even if the operations arrive in an online manner. They argued that most known ORAM constructions work in the online setting as well.
Our contribution is an Ω(lgn) lower bound on the bandwidth overhead of any online ORAM, even if we require only computational security and allow arbitrary representations of data, thus greatly strengthening the lower bound of Goldreich and Ostrovsky in the online setting. Our lower bound applies to ORAMs with memory size n and any word size r≥1. The bound therefore asymptotically matches the known upper bounds when r=Ω(lg²n).

The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems, see Henzinger et al. [STOC'15]. In recent work, Larsen and Williams [SODA'17] attacked the problem from the upper bound side and gave a surprising cell probe data structure (that is, we only charge for memory accesses, while computation is free). Their cell probe data structure answers queries in Õ(n^7/4) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional Õ(n^7/4) bits on the side. In this paper, we essentially settle the cell probe complexity of succinct Boolean matrix-vector multiplication. We present a new cell probe data structure with query time Õ(n^3/2) storing just Õ(n^3/2) bits on the side. We then complement our data structure with a lower bound showing that any data structure storing r bits on the side, with n<r<n² must have query time t satisfying tr=∼Ω(n³). For r≤n, any data structure must have t=∼Ω(n²). Since lower bounds in the cell probe model also apply to classic word-RAM data structures, the lower bounds naturally carry over. We also prove similar lower bounds for matrix-vector multiplication over 𝔽₂.

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.
We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a ∼Ω(lg^1.5n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over 𝔽₂ ([Pat07]). Proving an ω(lgn) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Patrascu's obituary [Tho13]. This result also implies the first ω(lgn) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median.
Our technical centerpiece is a new way of ``weakly" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebychev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the ``cell sampling" method of Panigrahy et al. [PTW10].

We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length m and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an O(m^1/2-ε) time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.

The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given N, for any set of N vectors X⊂ℝⁿ, there exists a mapping f : X→ℝ^m such that f(X) preserves all pairwise distances between vectors in X to within (1±ε) if m=O(ε^-2lgN). Much effort has gone into developing fast embedding algorithms, with the Fast Johnson-Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal m=O(ε^-2lgN) dimensions has an embedding time of O(nlgn+ε^-2lg³N). An exciting approach towards improving this, due to Hinrichs and Vybiral, is to use a random m×n Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in O(nlgm) time. The big question is of course whether m=O(ε^-2lgN) dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson-Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybiral shows that m=O(ε^-2lg²N) dimensions suffices. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exists a set of N vectors requiring m=Ω(ε^-2lg²N) for the Toeplitz approach to work.

We study regular expression membership testing: Given a regular expression of size m and a string of size n, decide whether the string is in the language described by the regular expression. Its classic O(nm) algorithm is one of the big success stories of the 70s, which allowed pattern matching to develop into the standard tool that it is today.
Many special cases of pattern matching have been studied that can be solved faster than in quadratic time. However, a systematic study of tractable cases was made possible only recently, with the first conditional lower bounds reported by Backurs and Indyk [FOCS'16]. Restricted to any ``type'' of homogeneous regular expressions of depth 2 or 3, they either presented a near-linear time algorithm or a quadratic conditional lower bound, with one exception known as the Word Break problem.
In this paper we complete their work as follows:

We present two almost-linear time algorithms that generalize all known almost-linear time algorithms for special cases of regular expression membership testing.
We classify all types, except for the Word Break problem, into almost-linear time or quadratic time assuming the Strong Exponential Time Hypothesis. This extends the classification from depth 2 and 3 to any constant depth.
For the Word Break problem we give an improved Õ(nm^1/3+m) algorithm. Surprisingly, we also prove a matching conditional lower bound for combinatorial algorithms. This establishes Word Break as the only intermediate problem.

In total, we prove matching upper and lower bounds for any type of bounded-depth homogeneous regular expressions, which yields a full dichotomy for regular expression membership testing.

For any integers d,n≥2 and 1/(min{n,d})^0.4999<ε<1, we show the existence of a set of n vectors X⊂ℝ^d such that any embedding f : X→ℝ^m satisfying

∀x,y∈X,(1-ε)||x-y||
2
2
≤||f(x)-f(y)||
2
2
≤(1+ε)||x-y||
2
2

must have

m=Ω(ε^-2lgn).

This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of ε of interest, since there is always an isometric embedding into dimension min{d,n} (either the identity map, or projection onto span(X)).
Previously such a lower bound was only known to hold against linear maps f, and not for such a wide range of parameters ε,n,d [LN16]. The best previously known lower bound for general f was m=Ω(ε^-2lgn/lg(1/ε)) [Wel74,Alo03], which is suboptimal for any ε=o(1).

One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be supported, one can design a comparison-based priority queue performing O((N/B)lg_M/BN) I/Os over a sequence of N operations, where B is the disk block size in number of words and M is the main memory size in number of words. This matches the lower bound for comparison-based sorting and is hence optimal for comparison-based priority queues. However, if we also need to support DecreaseKeys, the performance of the best known priority queue is only O((N/B)lg₂N) I/Os. The big open question is whether a degradation in performance really is necessary. We answer this question affirmatively by proving a lower bound of Ω((N/B)lg_lgNB) I/Os for processing a sequence of N intermixed Insert, ExtraxtMin and DecreaseKey operations. Our lower bound is proved in the cell probe model and thus holds also for non-comparison-based priority queues.

We consider the Online Boolean Matrix-Vector Multiplication (OMV) problem studied by Henzinger et al. [STOC'15]: given an n×n Boolean matrix M, we receive n Boolean vectors v₁,...,v_n one at a time, and are required to output Mv_i (over the Boolean semiring) before seeing the vector v_i+1, for all i. Previous known algorithms for this problem are combinatorial, running in O(n³/lg²n) time. Henzinger et al. conjecture there is no O(n^3-ε) time algorithm for OMV, for all ε>0; their OMV conjecture is shown to imply strong hardness results for many basic dynamic problems.
We give a substantially faster method for computing OMV, running in n³/2^{Ω((lgn)^1/2)} randomized time. In fact, after seeing 2^{ω((lgn)^1/2)} vectors, we already achieve n²/2^{Ω((lgn)^1/2)} amortized time for matrix-vector multiplication. Our approach gives a way to reduce matrix-vector multiplication to solving a version of the Orthogonal Vectors problem, which in turn reduces to "small" algebraic matrix-matrix multiplication. Applications include faster independent set detection, partial match retrieval, and 2-CNF evaluation.
We also show how a modification of our method gives a cell probe data structure for OMV with worst case O(n^7/4/w^1/2) time per query vector, where w is the word size. This result rules out an unconditional proof of the OMV conjecture using purely information-theoretic arguments.

The k-Means clustering problem on n points is NP-Hard for any dimension d≥2, however, for the 1D case there exists exact polynomial time algorithms. Previous literature reported an O(kn²) time dynamic programming algorithm that uses O(kn) space. It turns out that the problem has been considered under a different name more than twenty years ago. We present all the existing work that had been overlooked and compare the various solutions theoretically. Moreover, we show how to reduce the space usage for some of them, as well as generalize them to data structures that can quickly report an optimal k-Means clustering for any k. Finally we also generalize all the algorithms to work for the absolute distance and to work for any Bregman Divergence. We complement our theoretical contributions by experiments that compare the practical performance of the various algorithms.

In the turnstile ℓ_p heavy hitters problem with parameter ε, one must maintain a high-dimensional vector x∈ℝⁿ subject to updates of the form update(i,Δ) causing the change x_i←x_i+Δ, where i∈[n], Δ∈ℝ. Upon receiving a query, the goal is to report every heavy hitter i∈[n] with |x_i|≥ε||x||_p as part of a list L⊆[n] of size O(1/ε^p), i.e. proportional to the maximum possible number of heavy hitters. In fact we solve the stronger tail version, in which L should include every i such that |x_i|≥ε||x_[ε^-p]||_p, where x_[k] denotes the vector obtained by zeroing out the largest k entries of x in magnitude.
For any p∈(0,2] the COUNTSKETCH of [CCFC04] solves ℓ_p heavy hitters using O(ε^-plgn) words of space with O(lgn) update time, O(nlgn) query time to output L, and whose output after any query is correct with high probability (whp) 1-1/poly(n) [JST11, Section 4.4]. This space bound is optimal even in the strict turnstile model [JST11] in which it is promised that x_i≥0 for all i∈[n] at all points in the stream, but unfortunately the query time is very slow. To remedy this, the work [CM05] proposed the dyadic trick for the COUNTMIN sketch for p=1 in the strict turnstile model, which to maintain whp correctness achieves suboptimal space O(ε^-1lg²n), worse update time O(lg²n), but much better query time O(ε^-1poly(lgn)). An extension to all p∈(0,2] appears in [KNPW11, Theorem 1], and can be obtained from [Pag13].
We show that this tradeoff between space and update time versus query time is unnecessary. We provide a new algorithm, EXPANDERSKETCH, which in the most general turnstile model achieves optimal O(ε^-plgn) space, O(lgn) update time, and fast O(ε^-ppoly(lgn)) query time, providing correctness whp. In fact, a simpler version of our algorithm for p=1 in the strict turnstile model answers queries even faster than the dyadic trick by roughly a lgn factor, dominating it in all regards. Our main innovation is an efficient reduction from the heavy hitters to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a much bigger graph, and the goal is to identify every cluster. Since every heavy hitter must be found, correctness requires that every cluster be found. We thus need a cluster-preserving clustering algorithm, that partitions the graph into clusters with the promise of not destroying any original cluster. To do this we first apply standard spectral graph partitioning, and then we use some novel combinatorial techniques to modify the cuts obtained so as to make sure that the original clusters are sufficiently preserved. Our cluster-preserving clustering may be of broader interest much beyond heavy hitters.

We propose a new zero-knowledge protocol applicable to additively homomorphic functions that map integer vectors to an Abelian group. The protocol demonstrates knowledge of a short preimage and achieves amortised efficiency comparable to the approach of Cramer and Damgård from Crypto 2010, but gives a mich tighter bound on what we can extract from a dishonest prover. Towards achieving this result, we develop an analysis for bins-and-balls games that might be of independent interest. We also provide a general analysis of rewinding of a cut-and-choose protocol as well as a method to use Lyubachevsky's rejection sampling technique efficiently in an interactive protocol when many proofs are given simultaneously.
Our new protocol yields improved proofs of plaintext knowledge for (ring-)LWE based cryptosystems, where such general techniques were not known before. Moreover, they can be extended to prove preimages of homomorphic hash functions as well.

In the orthogonal range reporting problem, we are to preprocess a set of n points with integer coordinates on a U×U grid. The goal is to support reporting all k points inside an axis-aligned query rectangle. This is one of the most fundamental data structure problems in databases and computational geometry. Despite the importance of the problem its complexity remains unresolved in the word-RAM. On the upper bound side, three best tradeoffs exists:

Query time O(lglgn+k) with O(nlg^εn) words of space for any constant ε>0.
Query time O((1+k)lglgn) with O(nlglgn) words of space.
Query time O((1+k)lg^εn) with optimal O(n) words of space.

However, the only known query time lower bound is Ω(lglgn+k), even for linear space data structures.
All three current best upper bound tradeoffs are derived by reducing range reporting to a ball-inheritance problem. Ball-inheritance is a problem that essentially encapsulates all previous attempts at solving range reporting in the word-RAM. In this paper we make progress towards closing the gap between the upper and lower bounds for range reporting by proving cell probe lower bounds for ball-inheritance. Our lower bounds are tight for a large range of parameters, excluding any further progress for range reporting using the ball-inheritance reduction.

For any n>1 and 0<ε<1/2, we show the existence of an n^O(1)-point subset X of ℓ
n
2
such that any linear map from X to ℓ
m
2
with distortion at most 1+ε must have m=Ω(min{n,ε^-2lgn}). This improves a lower bound of Alon, in the linear setting, by a lg(1/ε) factor. Our lower bound matches the upper bounds provided by the identity matrix and the Johnson-Lindenstrauss lemma.

There has been a resurgence of interest in lower bounds whose truth rests on the conjectured hardness of well known computational problems. These conditional lower bounds have become important and popular due to the painfully slow progress on proving strong unconditional lower bounds. Nevertheless, the long term goal is to replace these conditional bounds with unconditional ones. In this paper we make progress in this direction by studying the cell probe complexity of two conjectured to be hard problems of particular importance: matrix-vector multiplication and a version of dynamic set disjointness known as Patrascu's Multiphase Problem. We give improved unconditional lower bounds for these problems as well as introducing new proof techniques of independent interest. These include a technique capable of proving strong threshold lower bounds of the following form: If we insist on having a very fast query time, then the update time has to be slow enough to compute a lookup table with the answer to every possible query. This is the first time a lower bound of this type has been proven.

In this paper, we study the role non-adaptivity plays in maintaining dynamic data structures. Roughly speaking, a data structure is non-adaptive if the memory locations it reads and/or writes when processing a query or update depend only on the query or update and not on the contents of previously read cells. We study such non-adaptive data structures in the cell probe model. The cell probe model is one of the least restrictive lower bound models and in particular, cell probe lower bounds apply to data structures developed in the popular word-RAM model. Unfortunately, this generality comes at a high cost: the highest lower bound proved for any data structure problem is only polylogarithmic (if allowed adaptivity). Our main result is to demonstrate that one can in fact obtain polynomial cell probe lower bounds for non-adaptive data structures.
To shed more light on the seemingly inherent polylogarithmic lower bound barrier, we study several different notions of non-adaptivity and identify key properties that must be dealt with if we are to prove polynomial lower bounds without restrictions on the data structures.
Finally, our results also unveil an interesting connection between data structures and depth-2 circuits. This allows us to translate conjectured hard data structure problems into good candidates for high circuit lower bounds; in particular, in the area of linear circuits for linear operators. Building on lower bound proofs for data structures in slightly more restrictive models, we also present a number of properties of linear operators which we believe are worth investigating in the realm of circuit lower bounds.

We say a turnstile streaming algorithm is non-adaptive if, during updates, the memory cells written and read depend only on the index being updated and random coins tossed at the beginning of the stream (and not on the memory contents of the algorithm). Memory cells read during queries may be decided upon adaptively. All known turnstile streaming algorithms in the literature, except a single recent example for a particular promise problem [Chitnis et al.'14], are non-adaptive. In fact, even more specifically, they are all linear sketches.
We prove the first non-trivial update time lower bounds for both randomized and deterministic turnstile streaming algorithms, which hold when the algorithms are non-adaptive. While there has been abundant success in proving space lower bounds, there have been no non-trivial turnstile update time lower bounds. Our lower bounds hold against classically studied problems such as heavy hitters, point query, entropy estimation, and moment estimation. In some cases of deterministic algorithms, our lower bounds nearly match known upper bounds.

This paper studies the ε-approximate range emptiness problem, where the task is to represent a set S of n points from {0,...,U-1} and answer emptiness queries of the form ``[a;b]∩S≠∅ ?'' with a probability of false positives allowed. This generalizes the functionality of Bloom filters from single point queries to any interval length L. Setting the false positive rate to ε/L and performing L queries, Bloom filters yield a solution to this problem with space O(nlg(L/ε)) bits, false positive probability bounded by ε for intervals of length up to L, using query time O(Llg(L/ε)). Our first contribution is to show that the space/error trade-off cannot be improved asymptotically: Any data structure for answering approximate range emptiness queries on intervals of length up to L with false positive probability ε, must use space Ω(nlg(L/ε))-O(n) bits. On the positive side we show that the query time can be improved greatly, to constant time, while matching our space lower bound up to a lower order additive term. This result is achieved through a succinct data structure for (non-approximate 1d) range emptiness/reporting queries, which may be of independent interest.

The skyline of a set of points in the plane is the subset of maximal points, where a point (x,y) is maximal if no other point (x',y') satisfies x'≥x and y'≥y. We consider the problem of preprocessing a set P of n points into a space efficient static data structure supporting orthogonal skyline counting queries, i.e. given a query rectangle R to report the size of the skyline of P∩R. We present a data structure for storing n points with integer coordinates having query time O(lgn/lglgn) and space usage O(n) words. The model of computation is a unit cost RAM with logarithmic word size. We prove that these bounds are the best possible by presenting a matching lower bound in the cell probe model with logarithmic word size: Space usage nlg^O(1)n implies worst case query time Ω(lgn/lglgn).

Let T={d₁,d₂,...,d_D} be a collection of D string documents of n characters in total. The two-pattern matching problems asks to index T for answering the following queries efficiently.

report/count the unique documents containing P₁ and P₂.
report/count the unique documents containing P₁, but not P₂.

Here P₁ and P₂ represents input patterns of length p₁ and p₂ respectively. Linear space data structures with O(p₁+p₂+(nk)^1/2lg^O(1)n) query cost are already known for the reporting version, where k represents the output size. For the counting version (i.e., report the value k), a simple linear-space index with O(p₁+p₂+n^1/2) query cost can be constructed in O(n^3/2) time. However, it is still not known if these are the best possible bounds for these problems. In this paper, we show a strong connection between these string indexing problems and the boolean matrix multiplication problem. Based on this, we argue that these results cannot be improved significantly using purely combinatorial techniques. We also provide an improved upper bound for a related problem known as two-dimensional substring indexing.

We consider NCA labeling schemes: Given a rooted tree T, label the nodes of T with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the label of their nearest common ancestor.
For trees with n nodes we present upper and lower bounds establishing that labels of size (2±ε)lgn, ε<1 are both sufficient and necessary.
Alstrup, Bille and Rauhe (Siam J. Discrete Math'05) showed that ancestor and NCA labeling schemes have labels of size lgn+Ω(lglgn). Our lower bound increases this to lgn+Ω(lgn) for NCA labeling schemes. Since Fraigniaud and Korman (STOC'10) established that labels in ancestor schemes have size lgn+Θ(lglgn), our new lower bound separates ancestor and NCA labeling schemes. Our upper bound improves the 10lgn upper bound by Alstrup, Gavoille, Kaplan and Rauhe (TOCS'04), and our theoretical result even outperforms some recent experimental studies by Fischer (ESA'09) where variants of the same NCA labeling scheme are shown to all have labels of size approximately 8lgn.

In this dissertation, we present a number of new techniques and tools for proving lower bounds on the operational time of data structures. These techniques provide new lines of attack for proving lower bounds in both the cell probe model, the group model, the pointer machine model and the I/O-model. In all cases, we push the frontiers further by proving lower bounds higher than what could possibly be proved using previously known techniques.
For the cell probe model, our results have the following consequences:

The first Ω(lgn) query time lower bound for linear space static data structures. The highest previous lower bound for any static data structure problem peaked at Ω(lgn/lglgn).
An Ω((lgn/lglgn)²) lower bound on the maximum of the update time and the query time of dynamic data structures. This is almost a quadratic improvement over the highest previous lower bound of Ω(lgn).

In the group model, we establish a number of intimate connections to the fields of combinatorial discrepancy and range reporting in the pointer machine model. These connections immediately allow us to translate decades of research in discrepancy and range reporting to very high lower bounds on the update time t_u and query time t_q of dynamic group model data structures. We have listed a few in the following:

For d-dimensional halfspace range searching, we get a lower bound of t_ut_q=Ω(n^1-1/d). This comes within a lglgn factor of the best known upper bound.
For orthogonal range searching, we get a lower bound of t_ut_q=Ω(lg^d-1n).
For ball range searching, we get a lower bound of t_ut_q=Ω(n^1-1/d).

The highest previous lower bound proved in the group model does not exceed Ω((lgn/lglgn)²) on the maximum of t_u and t_q.
Finally, we present a new technique for proving lower bounds for range reporting problems in the pointer machine and the I/O-model. With this technique, we tighten the gap between the known upper bound and lower bound for the most fundamental range reporting problem, orthogonal range reporting.

We revisit the classic problem of sampling from a discrete distribution: Given n non-negative w-bit integers x₁,...,x_n build a data structure that allows sampling i with probability proportional to x_i. The classic solution is Walker's alias method that takes, when implemented on a Word RAM, O(n) preprocessing time, O(1) expected query time for one sample, and n(w+2lgn+o(1)) bits of space. Using the terminology of succinct data structures, this solution has redundancy 2nlgn+o(n) bits, i.e., it uses 2nlgn+o(n) bits in addition to the information theoretic minimum required for storing the input. In this paper, we study whether this space usage can be improved.
    In the systematic case, where the input is read-only, we present a novel data structure using r+O(w) redundant bits, O(n/r) expected query time and O(n) preprocessing time for any r, which is an improvement in redundancy by a factor Ω(lgn) over the alias method for r=n, even though the alias method is not systematic. Moreover, we complement our data structure with a lower bound showing that this trade-off is tight for systematic data structures.
    In the non-systematic case, where the input numbers may be represented in more clever ways than just storing them one-by-one, we demonstrate a very surprising separation from the systematic case: With only 1 redundant bit, it is possible to support optimal O(1) expected query time and O(n) preprocessing time!
    On the one hand, our results improve upon the space requirement of the classic solution for a fundamental sampling problem, on the other hand, they provide the largest known separation between the systematic and non-systematic case for any data structure problem. Finally, we also believe our upper bounds are practically efficient and simpler than Walker's alias method.

We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret (z,π) consisting of a binary string z of length n and a permutation π of [n]. The secret must be unveiled by asking queries x∈{0,1}ⁿ, and for each query asked, we are returned the score f_z,π(x) defined as

f_z,π(x) : =max{i∈[0..n]|∀j≤i : z_π(j)=x_π(j)}

i.e., the length of the longest common prefix of x and z with respect to π. The goal is to minimize the number of queries asked.
Our main result are matching upper and lower bounds for this problem, both for deterministic and randomized query schemes. The deterministic query complexity is Θ(nlgn), which, surprisingly, improves to Θ(nlglgn) in the randomized setting.
For the randomized query complexity, both the upper and lower bound are stronger than what can be achieved by standard arguments like the analysis of random queries or information-theoretic considerations. Our proof of the Ω(nlglgn) lower bound is based on a potential function argument, which seems to be uncommon in the query complexity literature. We find this potential function technique a very powerful tool in proving lower bounds for randomized query schemes and we expect it to find applications in many other query complexity problems.

Range reporting on categorical (or colored) data is a well-studied generalization of the classical range reporting problem in which each of the N input points has an associated color (category). A query then asks to report the set of colors of the points in a given rectangular query range, which may be far smaller than the set of all points in the query range.
We study two-dimensional categorical range reporting in both the word-RAM and I/O-model. For the I/O-model, we present two alternative data structures for three-sided queries. The first answers queries in optimal O(lg_BN+K/B) I/Os using O(Nlg^*N) space, where K is the number of distinct colors in the output, B is the disk block size, and lg^*N is the iterated logarithm of N. Our second data structure uses linear space and answers queries in O(lg_BN+lg^(h)N+K/B) I/Os for any constant integer h≥1. Here lg⁽¹⁾N=lgN and lg^(h)N=lg(lg^(h-1)N) when h>1. Both solutions use only comparisons on the coordinates. We also show that the lg_BN terms in the query costs can be reduced to optimal lglg_BU when the input points lie on a U×U grid and we allow word-level manipulations of the coordinates. We further reduce the query time to just O(1) if the points are given on an N×N grid. Both solutions also lead to improved data structures for four-sided queries. For the word-RAM, we obtain optimal data structures for three-sided range reporting, as well as improved upper bounds for four-sided range reporting.
Finally, we show a tight lower bound on one-dimensional categorical range counting using an elegant reduction from (standard) two-dimensional range counting.

Range reporting is a one of the most fundamental topics in spatial databases and computational geometry. In this class of problems, the input consists of a set of geometric objects, such as points, line segments, rectangles etc. The goal is to preprocess the input set into a data structure, such that given a query range, one can efficiently report all input objects intersecting the range. The ranges most commonly considered are axis-parallel rectangles, halfspaces, points, simplices and balls.
In this survey, we focus on the planar orthogonal range reporting problem in the external memory model of Aggarwal and Vitter [CACM'88]. Here the input consists of a set of N points in the plane, and the goal is to support reporting all points inside an axis-parallel query rectangle.

In this paper, we study the cell probe complexity of evaluating an n-degree polynomial P over a finite field F of size at least n^1+Ω(1). More specifically, we show that any static data structure for evaluating P(x), where x∈F, must use Ω(lg|F|/lg(Sw/nlg|F|)) cell probes to answer a query, where S denotes the space of the data structure in number of cells and w the cell size in bits. This bound holds in expectation for randomized data structures with any constant error probability δ<1/2. Our lower bound not only improves over the Ω(lg|F|/lgS) lower bound of Miltersen [TCS'95], but is in fact the highest static cell probe lower bound to date: For linear space (i.e. S=O(nlg|F|/w)), our query time lower bound simplifies to Ω(lg|F|), whereas the highest previous lower bound for any static data structure problem having d different queries is Ω(lgd/lglgd), which was first achieved by Pătraşcu and Thorup [SICOMP'10].
We also use the recent technique of Larsen [STOC'12] to show a lower bound of t_q=Ω(lg|F|lgn/lg(wt_u/lg|F|)lg(wt_u)) for dynamic data structures for polynomial evaluation over a finite field F of size Ω(n²). Here t_q denotes the expected query time and t_u the worst case update time. This lower bound holds for randomized data structures with any constant error probability δ<1/2. This is only the second time a lower bound beyond max{t_u,t_q}=Ω(max{lgn,lgd/lglgd}) has been achieved for dynamic data structures, where d denotes the number of different queries and updates to the problem. Furthermore, it is the first such lower bound that holds for randomized data structures with a constant probability of error.

In this paper we present a number of improved lower bounds for range searching in the pointer machine and the group model. In the pointer machine, we prove lower bounds for the approximate simplex range reporting problem. In approximate simplex range reporting, points that lie within a distance of ε·diam(s) from the border of a query simplex s, are free to be included or excluded from the output, where ε≥0 is an input parameter to the range searching problem. We prove our lower bounds by constructing a hard input set and query set, and then invoking Chazelle and Rosenberg's [CGTA'96] general theorem on the complexity of navigation in the pointer machine.
For the group model, we show that input sets and query sets that are hard for range reporting in the pointer machine (i.e. by Chazelle and Rosenberg's theorem), are also hard for dynamic range searching in the group model. This theorem allows us to reuse decades of research on range reporting lower bounds to immediately obtain a range of new group model lower bounds. Amongst others, this includes an improved lower bound for the fundamental problem of dynamic d-dimensional orthogonal range searching, stating that t_qt_u=Ω((lgn/lglgn)^d-1). Here t_q denotes the query time and t_u the update time of the data structure. This is an improvement of a lg^1-δn factor over the recent lower bound of Larsen [FOCS'11], where δ>0 is a small constant depending on the dimension.

In this paper, we consider two fundamental problems in the pointer machine model of computation, namely orthogonal range reporting and rectangle stabbing. Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space in a data structure, such that the t points in an axis-aligned query rectangle can be reported efficiently. Rectangle stabbing is the ``dual'' problem where a set of n axis-aligned rectangles should be stored in a data structure, such that the t rectangles that contain a query point can be reported efficiently. Very recently an optimal O(lgn+t) query time pointer machine data structure was developed for the three-dimensional version of the orthogonal range reporting problem. However, in four dimensions the best known query bound of O(lg²n/lglgn+t) has not been improved for decades.
We describe an orthogonal range reporting data structure that is the first structure to achieve significantly less than O(lg²n+t) query time in four dimensions. More precisely, we develop a structure that uses O(n(lgn/lglgn)^d) space and can answer d-dimensional orthogonal range reporting queries (for d≥4) in O(lgn(lgn/lglgn)^d-4+1/(d-2)+t) time. Ignoring lglgn factors, this speeds up the best previous query time by a lg^1-1/(d-2)n factor. For the rectangle stabbing problem, we show that any data structure that uses nh space must use Ω(lgn(lgn/lgh)^d-2+t) time to answer a query. This improves the previous results by a lgh factor, and is the first lower bound that is optimal for a large range of h, namely for h≥lg^d-2+εn where ε>0 is an arbitrarily small constant. By a simple geometric transformation, our result also implies an improved query lower bound for orthogonal range reporting.

In this paper we develop a new technique for proving lower bounds on the update time and query time of dynamic data structures in the cell probe model. With this technique, we prove the highest lower bound to date for any explicit problem, namely a lower bound of t_q=Ω((lgn/lg(wt_u))²). Here n is the number of update operations, w the cell size, t_q the query time and t_u the update time. In the most natural setting of cell size w=Θ(lgn), this gives a lower bound of t_q=Ω((lgn/lglgn)²) for any polylogarithmic update time. This bound is almost a quadratic improvement over the highest previous lower bound of Ω(lgn), due to Pătraşcu and Demaine [SICOMP'06].
We prove our lower bound for the fundamental problem of weighted orthogonal range counting. In this problem, we are to support insertions of two-dimensional points, each assigned a Θ(lgn)-bit integer weight. A query to this problem is specified by a point q=(x,y), and the goal is to report the sum of the weights assigned to the points dominated by q, where a point (x',y') is dominated by q if x'≤x and y'≤y. In addition to being the highest cell probe lower bound to date, our lower bound is also tight for data structures with update time t_u=Ω(lg^2+εn), where ε>0 is an arbitrarily small constant.

A mode of a multiset S is an element a∈S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1 : n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i,j) for which a mode of A[i : j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(n^1/2lglgn) query time. We improve their result, by not only eliminating the lglgn factor, but also achieving o(n^1/2) time: specifically, we present an O(n)-space data structure that supports range mode queries in O((n/lgn)^1/2) worst-case time. Furthermore, we present strong evidence that a query time significantly below n^1/2 cannot be achieved by purely combinatorial techniques. We show that boolean matrix multiplication of two n^1/2×n^1/2 matrices reduces to n range mode queries in an array of size O(n). Since the current best combinatorial algorithm for boolean matrix multiplication has cubic running time (ignoring polylogarithmic factors), this reduction shows that achieving preprocessing time significantly less than n^3/2 and query time significantly less than n^1/2 simultaneously would be a major breakthrough. Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O(n^3/4) time), for orthogonal range mode in higher dimensions (queries in near O(n^1-1/2d) time), and for halfspace range mode in higher dimensions (queries in O(n^1-1/d²) time).

Motivated by information retrieval applications, we consider the one-dimensional colored range reporting problem in rank space. The goal is to build a static data structure for sets C₁,...,C_m⊆{1,...,σ} that supports queries of the kind: Given indices a,b, report the set ∪_a≤i≤bC_i.
We study the problem in the I/O model, and show that there exists an optimal linear-space data structure that answers queries in O(1+k/B) I/Os, where k denotes the output size and B the disk block size in words. In fact, we obtain the same bound for the harder problem of three-sided orthogonal range reporting. In this problem, we are to preprocess a set of n two-dimensional points in rank space, such that all points inside a query rectangle of the form [x₁,x₂]×(-∞,y] can be reported. The best previous bounds for this problem is either O(nlg
2
B
n) space and O(1+k/B) query I/Os, or O(n) space and O(lg
(h)
B
n+k/B) query I/Os, where lg
(h)
B
n is the base B logarithm iterated h times, for any constant integer h. The previous bounds are both achieved under the indivisibility assumption, while our solution exploits the full capabilities of the underlying machine. Breaking the indivisibility assumption thus provides us with cleaner and optimal bounds.
Our results also imply an optimal solution to the following colored prefix reporting problem. Given a set S of strings, each O(1) disk blocks in length, and a function c : S→2^{1,...,σ}, support queries of the kind: Given a string p, report the set ∪_x∈S∩p*c(x), where p* denotes the set of strings with prefix p. Finally, we consider the possibility of top-k extensions of this result, and present a simple solution in a model that allows non-blocked I/O.

In this paper we establish an intimate connection between dynamic range searching in the group model and combinatorial discrepancy. Our result states that, for a broad class of range searching data structures (including all known upper bounds), it must hold that t_ut_q=Ω(disc²) where t_u is the worst case update time, t_q the worst case query time and disc is the combinatorial discrepancy of the range searching problem in question. This relation immediately implies a whole range of exceptionally high and near-tight lower bounds for all of the basic range searching problems. We list a few of them in the following:

For d-dimensional halfspace range searching, we get a lower bound of t_ut_q=Ω(n^1-1/d). This comes within a lglgn factor of the best known upper bound.
For orthogonal range searching, we get a lower bound of t_ut_q=Ω(lg^d-1n).
For ball range searching, we get a lower bound of t_ut_q=Ω(n^1-1/d).

We note that the previous highest lower bound for any explicit problem, due to Pătraşcu [STOC'07], states that t_q=Ω((lgn/lg(lgn+t_u))²), which does however hold for a less restrictive class of data structures.
Our result also has implications for the field of combinatorial discrepancy. Using textbook range searching solutions, we improve on the best known discrepancy upper bound for axis-aligned rectangles in all dimensions d≥3.

We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model:

We present two data structures for 2-d orthogonal range emptiness. The first achieves O(nlglgn) space and O(lglgn) query time, assuming that the n given points are in rank space. This improves the previous results by Alstrup, Brodal, and Rauhe (FOCS'00), with O(nlg^εn) space and O(lglgn) query time, or with O(nlglgn) space and O(lg²lgn) query time. Our second data structure uses O(n) space and answers queries in O(lg^εn) time. The best previous O(n)-space data structure, due to Nekrich (WADS'07), answers queries in O(lgn/lglgn) time.
We give a data structure for 3-d orthogonal range reporting with O(nlg^1+εn) space and O(lglgn+k) query time for points in rank space, for any constant ε>0. This improves the previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(nlg³n) space and O(lglgn+k) query time, or with O(nlg^1+εn) space and O(lg²lgn+k) query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above 3.
Our approach also leads to a new data structure for 2-d orthogonal range minimum queries with O(nlg^εn) space and O(lglgn) query time for points in rank space.
We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time O(nlgn) plus the output size. This resolves two open problems (both appeared in Preparata and Shamos' seminal book):
1. given a set of n axis-aligned rectangles in the plane, we can report all k enclosure pairs (i.e., pairs (r₁,r₂) where rectangle r₁ completely encloses rectangle r₂) in O(nlgn+k) expected time;
2. given a set of n points in 4-d, we can find all maximal points (points not dominated by any other points) in O(nlgn) expected time.
The most recent previous development on (a) was reported back in SoCG'95 by Gupta, Janardan, Smid, and Dasgupta, whose main result was an O([nlgn+k]lglgn) algorithm. The best previous result on (b) was an O(nlgnlglgn) algorithm due to Gabow, Bentley, and Tarjan---from STOC'84! As a consequence, we also obtain the current-record time bound for the maxima problem in all constant dimensions above 4.

Given a set of points with uncertain locations, we consider the problem of computing the probability of each point lying on the skyline, that is, the probability that it is not dominated by any other input point. If each point's uncertainty is described as a probability distribution over a discrete set of locations, we improve the best known exact solution. We also suggest why we believe our solution might be optimal. Next, we describe simple, near-linear time approximation algorithms for computing the probability of each point lying on the skyline. In addition, some of our methods can be adapted to construct data structures that can efficiently determine the probability of a query point lying on the skyline.

Range selection is the problem of preprocessing an input array A of n unique integers, such that given a query (i,j,k), one can report the k'th smallest integer in the subarray A[i],A[i+1],...,A[j]. In this paper we consider static data structures in the word-RAM for range selection and several natural special cases thereof.
The first special case is known as range median, which arises when k is fixed to ⌊(j-i+1)/2⌋. The second case, denoted prefix selection, arises when i is fixed to 0. Finally, we also consider the bounded rank prefix selection problem and the fixed rank range selection problem. In the former, data structures must support prefix selection queries under the assumption that k≤κ for some value κ≤n given at construction time, while in the latter, data structures must support range selection queries where k is fixed beforehand for all queries. We prove cell probe lower bounds for range selection, prefix selection and range median, stating that any data structure that uses S words of space needs Ω(lgn/lg(Sw/n)) time to answer a query. In particular, any data structure that uses nlg^O(1)n space needs Ω(lgn/lglgn) time to answer a query, and any data structure that supports queries in constant time, needs n^1+Ω(1) space. For data structures that uses nlg^O(1)n space this matches the best known upper bound.
Additionally, we present a linear space data structure that supports range selection queries in O(lgk/lglgn+lglgn) time. Finally, we prove that any data structure that uses S space, needs Ω(lgκ/lg(Sw/n)) time to answer a bounded rank prefix selection query and Ω(lgk/lg(Sw/n)) time to answer a fixed rank range selection query. This shows that our data structure is optimal except for small values of k.

We consider the problem of automatically cleaning massive sonar data point clouds, that is, the problem of automatically removing noisy points that for example appear as a result of scans of (shoals of) fish, multiple reflections, scanner self-reflections, refraction in gas bubbles, and so on.
We describe a new algorithm that avoids the problems of previous local-neighbourhood based algorithms. Our algorithm is theoretically I/O-efficient, that is, it is capable of efficiently processing massive sonar point clouds that do not fit in internal memory but must reside on disk. The algorithm is also relatively simple and thus practically efficient, partly due to the development of a new simple algorithm for computing the connected components of a graph embedded in the plane. A version of our cleaning algorithm has already been incorporated in a commercial product.

The mode of a multiset of labels, is a label that occurs at least as often as any other label. The input to the range mode problem is an array A of size n. A range query [i,j] must return the mode of the subarray A[i],A[i+1],...,A[j]. We prove that any data structure that uses S memory cells of w bits needs Ω(lgn/lg(Sw/n)) time to answer a range mode query. Secondly, we consider the related range k-frequency problem. The input to this problem is an array A of size n, and a query [i,j] must return whether there exists a label that occurs precisely k times in the subarray A[i],A[i+1],...,A[j]. We show that for any constant k>1, this problem is equivalent to 2D orthogonal rectangle stabbing, and that for k=1 this is no harder than four-sided 3D orthogonal range emptiness. Finally, we consider approximate range mode queries. A c-approximate range mode query must return a label that occurs at least 1/c times that of the mode. We describe a linear space data structure that supports 3-approximate range mode queries in constant time, and a data structure that uses O(n/ε) space and supports (1+ε)-approximation queries in O(lg1/ε) time.

Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space, such that the k points in an axis-orthogonal query box can be reported efficiently. While the 2-d version of the problem was completely characterized in the pointer machine model more than two decades ago, this is not the case in higher dimensions.
    In this paper we provide a space optimal pointer machine data structure for 3-d orthogonal range reporting that answers queries in O(lgn+k) time. Thus we settle the complexity of the problem in 3-d. We use this result to obtain improved structures in higher dimensions, namely structures with a lgn/lglgn factor increase in space and query time per dimension. Thus for d≥3 we obtain a structure that both uses optimal O(n(lgn/lglgn)^d-1) space and answers queries in the best known query bound O(lgn(lgn/lglgn)^d-3+k).
    Furthermore, we show that any data structure for the d-dimensional orthogonal range reporting problem in the pointer machine model of computation that uses S(n) space must spend Ω((lgn/lg(S(n)/n))^⌊d/2⌋-1) time to answer queries. Thus, if S(n)/n is poly-logarithmic, then the query time is at least Ω((lgn/lglgn)^⌊d/2⌋-1). This is the first known non-trivial higher dimensional orthogonal range reporting query lower bound and it has two important implications. First, it shows that the query bound increases with dimension. Second, in combination with our upper bounds it shows that the optimal query bound increases from Θ(lgn+k) to Ω((lgn/lglgn)²+k) somewhere between three and six dimensions.
    Finally, we show that our techniques also lead to improved structures for point location in rectilinear subdivisions, that is, the problem of storing a set of n disjoint d-dimensional axis-orthogonal rectangles, such that the rectangle containing a query point q can be found efficiently.

In orthogonal range reporting we are to preprocess N points in d dimensions such that the points inside an axis-aligned query box can be found efficiently. This is a fundamental problem in various fields, including spatial databases and computational geometry.
In this paper we provide a number of improvements for three and higher dimensional orthogonal range reporting: In the pointer machine model, we improve all the best previous results available, some of which have not seen any improvements in almost two decades. In the I/O-model, we improve the previously known three-dimensional structures and provide the first (non-trivial) structures for four and higher dimensions.

Predicting the success of students participating in introductory programming courses has been an active research area for more than 25 years. Until recently, no variables or tests have had any significant predictive power. However, Dehnadi and Bornat claim to have found a simple test for programming aptitude to cleanly separate programming sheep from non-programming goats. We briefly present their theory and test instruments.
We have repeated their test in our local context in order to verify and perhaps generalise their findings, but we could not show that the test predicts students' success in our introductory programming course.
Based on this failure of the test instrument, we discuss various explanations for our differing results and suggest a research method from which it may be possible to generalise local results in this area. Furthermore, we discuss and criticize Dehnadi and Bornat's programming aptitude test and devise alternative test instruments.

Awards:

Links:

Publications: