We present a local computation algorithm (LCA) for constructing a connected spanning subgraph whose total weight is at most a (1+ε)-factor larger than that of a minimum spanning tree, in general bounded-degree graphs. Prior to our work, nontrivial LCAs for this problem, namely, algorithms with sublinear query complexity, were known only for the restricted graph family of minor-free graphs by Levi, Ron, and Rubinfeld (Algorithmica 2020). The query complexity of our algorithm in terms of the number of vertices, n, is Õ(n^{2/3}). The best known lower bound for this problem is Ω(n^{1/2}). Our approach consists of three conceptual layers. The first is a localized variant of Prim’s algorithm, which reconstructs, using only local queries, a large fraction of the edges of the minimum spanning tree. The resulting subgraph at this stage is disconnected. To address this, in the second layer, we partition the partially constructed forest into clusters of size Õ(n^{1/3}). To this end, we present a partition oracle, as introduced by Hassidim et al. (FOCS 2009), for trees whose query complexity is nearly optimal in terms of ε, the parameter that controls the number of edges in the boundary. In particular, its query complexity is Õ(d/ε), where d denotes the degree bound. In the third and last layer, we adapt the technique from Lenzen-Levi (ICALP 2018) for locally computing a sparse spanning subgraph and obtain an algorithm that locally identifies and adds a small number of carefully chosen edges in order to restore global connectivity. We show that the number of such additional edges is small, and consequently, their total weight contributes only a small amount to the overall cost, preserving the (1+ε)-approximation guarantee.

STOC ’25, Prague, Czechia

We study the problem of testing $C_k$-freeness ($k$-cycle-freeness) for fixed constant $k > 3$ in graphs with bounded arboricity (but unbounded degrees). In particular, we are interested in one-sided error algorithms, so that they must detect a copy of $C_k$ with high constant probability when the graph is $ε$-far from $C_k$-free. We next state our results for constant arboricity and constant $ε$ with a focus on the dependence on the number of graph vertices, $n$. The query complexity of all our algorithms grows polynomially with $1/ε$. (1) As opposed to the case of $k=3$, where the complexity of testing $C_3$-freeness grows with the arboricity of the graph but not with the size of the graph (Levi, ICALP 2021) this is no longer the case already for $k=4$. We show that $Ω(n^{1/4})$ queries are necessary for testing $C_4$-freeness, and that $\widetilde{O}(n^{1/4})$ are sufficient. The same bounds hold for $C_5$. (2) For every fixed $k \geq 6$, any one-sided error algorithm for testing $C_k$-freeness must perform $Ω(n^{1/3})$ queries. (3) For $k=6$ we give a testing algorithm whose query complexity is $\widetilde{O}(n^{1/2})$. (4) For any fixed $k$, the query complexity of testing $C_k$-freeness is upper bounded by ${O}(n^{1-1/\lfloor k/2\rfloor})$. Our $Ω(n^{1/4})$ lower bound for testing $C_4$-freeness in constant arboricity graphs provides a negative answer to an open problem posed by (Goldreich, 2021).

We study the problem of finding a Hamiltonian cycle under the promise that the input graph has a minimum degree of at least $n/2$, where $n$ denotes the number of vertices in the graph. The classical theorem of Dirac states that such graphs (a.k.a. Dirac graphs) are Hamiltonian, i.e., contain a Hamiltonian cycle. Moreover, finding a Hamiltonian cycle in Dirac graphs can be done in polynomial time in the classical centralized model. This paper presents a randomized distributed CONGEST algorithm that finds w.h.p. a Hamiltonian cycle (as well as maximum matching) within $O(\log n)$ rounds under the promise that the input graph is a Dirac graph. This upper bound is in contrast to general graphs in which both the decision and search variants of Hamiltonicity require $\tildeΩ(n^2)$ rounds, as shown by Bachrach et al. [PODC'19]. In addition, we consider two generalizations of Dirac graphs: Ore graphs and Rahman-Kaykobad graphs [IPL'05]. In Ore graphs, the sum of the degrees of every pair of non-adjacent vertices is at least $n$, and in Rahman-Kaykobad graphs, the sum of the degrees of every pair of non-adjacent vertices plus their distance is at least $n+1$. We show how our algorithm for Dirac graphs can be adapted to work for these more general families of graphs.

Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, since they can be used to order the results of queries. However, these ranking functions are famously subject to attacks by spammers, who modify the web graph in order to give their own pages more rank.

In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In particular, we provide the following algorithms for minor-free unbounded degree graphs. 1) A tester for Hamiltonicity with two-sided error with poly(1/ε)-query complexity, where ε is the proximity parameter. 2) A local algorithm, as defined by Rubinfeld et al. (ICS 2011), for constructing a spanning subgraph with almost minimum weight, specifically, at most a factor (1+ε) of the optimum, with poly(1/ε)-query complexity. Both our algorithms use partition oracles, a tool introduced by Hassidim et al. (FOCS 2009), which are oracles that provide access to a partition of the graph such that the number of cut-edges is small and each part of the partition is small. The polynomial dependence in 1/ε of our algorithms is achieved by combining the recent poly(d/ε)-query partition oracle of Kumar-Seshadhri-Stolman (ECCC 2021) for minor-free graphs with degree bounded by d. For bounded degree minor-free graphs we introduce the notion of covering partition oracles which is a relaxed version of partition oracles and design a poly(d/ε)-time covering partition oracle for this family of graphs. Using our covering partition oracle we provide the same results as above (except that the tester for Hamiltonicity has one-sided error) for minor-free bounded degree graphs, as well as showing that any property which is monotone and additive (e.g. bipartiteness) can be tested in minor-free graphs by making poly(d/ε)-queries. The benefit of using the covering partition oracle rather than the partition oracle in our algorithms is its simplicity and an improved polynomial dependence in 1/ε in the obtained query complexity.

We study the problem of testing triangle freeness in the general graph model. This problem was first studied in the general graph model by Alon et al. (SIAM J. Discret. Math. 2008) who provided both lower bounds and upper bounds that depend on the number of vertices and the average degree of the graph. Their bounds are tight only when d_max = O(d) and ̄{d} ≤ √n or when ̄{d} = Θ(1), where d_max denotes the maximum degree and ̄{d} denotes the average degree of the graph. In this paper we provide bounds that depend on the arboricity of the graph and the average degree. As in Alon et al., the parameters of our tester is the number of vertices, n, the number of edges, m, and the proximity parameter ε (the arboricity of the graph is not a parameter of the algorithm). The query complexity of our tester is Õ(Γ/ ̄{d} + Γ)⋅ poly(1/ε) on expectation, where Γ denotes the arboricity of the input graph (we use Õ(⋅) to suppress O(log log n) factors). We show that for graphs with arboricity O(√n) this upper bound is tight in the following sense. For any Γ ∈ [s] where s = Θ(√n) there exists a family of graphs with arboricity Γ and average degree ̄{d} such that Ω(Γ/ ̄{d} + Γ) queries are required for testing triangle freeness on this family of graphs. Moreover, this lower bound holds for any such Γ and for a large range of feasible average degrees .

We give a distributed algorithm in the \sf CONGEST model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et al. (DISC 2016), who recently initiated the study of property testing in the distributed setting, our algorithm gives the following guarantee: For a graph G = (V,E) and a distance parameter ε, if G is planar, then every node outputs \sf accept, and if G is ε-far from being planar (i.e., more than ε\cdot |E| edges need to be removed in order to make G planar), then with probability 1-1/\rm poly (n) at least one node outputs \sf reject. The algorithm runs in O(log|V|\cdot\poly(1/ε)) rounds, and we show that this result is tight in terms of the dependence on |V|. Our algorithm combines several techniques of graph partitioning and local verification of planar embeddings. Furthermore, we show how a main subroutine in our algorithm can be applied to derive additional results for property testing of cycle-freeness and bipartiteness, as well as the construction of spanners, in minor-free (unweighted) graphs.

Recent advances in T cell repertoire (TCR) sequencing allow for the characterization of repertoire properties, as well as the frequency and sharing of specific TCR. However, there is no efficient measure for the local density of a given TCR. TCRs are often described either through their Complementary Determining region 3 (CDR3) sequences, or theirV/J usage, or their clone size. We here show that the local repertoire density can be estimated using a combined representation of these components through distance conserving autoencoders and Kernel Density Estimates (KDE). We present ELATE-an Encoder-based LocAl Tcr dEnsity and show that the resulting density of a sample can be used as a novel measure to study repertoire properties. The cross-density between two samples can be used as a similarity matrix to fully characterize samples from the same host. Finally, the same projection in combination with machine learning algorithms can be used to predict TCR-peptide binding through the local density of known TCRs binding a specific target.

We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space, and randomness complexities of such samplers. In the standard approach, the whole graph is chosen randomly according to the randomized evolving process, stored in full, and then queries on the sampled graph are answered by simply accessing the stored graph. This may require prohibitive amounts of time, space, and random bits, especially when only a small number of queries are actually issued. Instead, we propose a setting where one generates parts of the sampled graph on-the-fly, in response to queries, and therefore requires amounts of time, space, and random bits that are a function of the actual number of queries. Yet, the responses to the queries correspond to a graph sampled from the distribution in question. Within this framework, we focus on two random graph models: the Barabási-Albert Preferential Attachment model (BA-graphs) ( Science , 286 (5439):509–512) (for the special case of out-degree 1) and the random recursive tree model ( Theory of Probability and Mathematical Statistics , (51):1–28). We give on-the-fly generation algorithms for both models. With probability 1-1/poly( n ), each and every query is answered in polylog( n ) time, and the increase in space and the number of random bits consumed by any single query are both polylog( n ), where n denotes the number of vertices in the graph. Our work thus proposes a new approach for the access to huge graphs sampled from a given distribution, and our results show that, although the BA random graph model is defined by a sequential process, efficient random access to the graph’s nodes is possible. In addition to the conceptual contribution, efficient on-the-fly generation of random graphs can serve as a tool for the efficient simulation of sublinear algorithms over large BA-graphs, and the efficient estimation of their on such graphs.

In this paper we study the problem of testing graph isomorphism (GI) in the CONGEST distributed model. In this setting we test whether the distributive network, $G_U$, is isomorphic to $G_K$ which is given as an input to all the nodes in the network, or alternatively, only to a single node. We first consider the decision variant of the problem in which the algorithm distinguishes $G_U$ and $G_K$ which are isomorphic from $G_U$ and $G_K$ which are not isomorphic. We provide a randomized algorithm with $O(n)$ rounds for the setting in which $G_K$ is given only to a single node. We prove that for this setting the number of rounds of any deterministic algorithm is $\tildeΩ(n^2)$ rounds, where $n$ denotes the number of nodes, which implies a separation between the randomized and the deterministic complexities of deciding GI. We then consider the \emph{property testing} variant of the problem, where the algorithm is only required to distinguish the case that $G_U$ and $G_K$ are isomorphic from the case that $G_U$ and $G_K$ are \emph{far} from being isomorphic (according to some predetermined distance measure). We show that every algorithm requires $Ω(D)$ rounds, where $D$ denotes the diameter of the network. This lower bound holds even if all the nodes are given $G_K$ as an input, and even if the message size is unbounded. We provide a randomized algorithm with an almost matching round complexity of $O(D+(ε^{-1}\log n)^2)$ rounds that is suitable for dense graphs. We also show that with the same number of rounds it is possible that each node outputs its mapping according to a bijection which is an \emph{approximated} isomorphism. We conclude with simple simulation arguments that allow us to obtain essentially tight algorithms with round complexity $\tilde{O}(D)$ for special families of sparse graphs.

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most \((1+\epsilon )n\) edges (where n is the number of vertices and \(\epsilon \) is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e . The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be \(\Omega (\sqrt{n})\) . This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is \(\mathrm{poly}(1/\epsilon , h)\) (independent of n and the maximum degree), where h is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences.

We consider one-sided error property testing of $\mathcal{F}$-minor freeness in bounded-degree graphs for any finite family of graphs $\mathcal{F}$ that contains a minor of $K_{2,k}$, the $k$-circus graph, or the $(k\times 2)$-grid for any $k\in\mathbb{N}$. This includes, for instance, testing whether a graph is outerplanar or a cactus graph. The query complexity of our algorithm in terms of the number of vertices in the graph, $n$, is $\tilde{O}(n^{2/3} / ε^5)$. Czumaj et~al.\ showed that cycle-freeness and $C_k$-minor freeness can be tested with query complexity $\tilde{O}(\sqrt{n})$ by using random walks, and that testing $H$-minor freeness for any $H$ that contains a cycles requires $Ω(\sqrt{n})$ queries. In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor $H$, or we can find a pair of disjoint subsets of vertices whose edge-cut is large, which induces an $H$-minor.

Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O~(poly(Delta/epsilon)n^{2/3}), where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanning subgraph of bounded stretch i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n * (Delta+log n)/epsilon) hops in the output that connects its endpoints.

In this paper we consider the problem of testing whether a graph has bounded arboricity. The family of graphs with bounded arboricity includes, among others, bounded-degree graphs, all minor-closed graph classes (e.g. planar graphs, graphs with bounded treewidth) and randomly generated preferential attachment graphs. Graphs with bounded arboricity have been studied extensively in the past, in particular since for many problems they allow for much more efficient algorithms and/or better approximation ratios. We present a tolerant tester in the sparse-graphs model. The sparse-graphs model allows access to degree queries and neighbor queries, and the distance is defined with respect to the actual number of edges. More specifically, our algorithm distinguishes between graphs that are e-close to having arboricity α and graphs that c · ∊-far from having arboricity 3α, where c is an absolute small constant. The query complexity and running time of the algorithm are1 where n denotes the number of vertices and m denotes the number of edges. In terms of the dependence on n and m this bound is optimal up to poly-logarithmic factors since queries are necessary (and the arboricity of a graph is always . We leave it as an open question whether the dependence on 1/∊ can be improved from quasi-polynomial to polynomial. Our techniques include an efficient local simulation for approximating the outcome of a global (almost) forest-decomposition algorithm as well as a tailored procedure of edge sampling.

We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space and randomness complexities of such samplers. In the standard approach, the whole graph is chosen randomly according to the randomized evolving process, stored in full, and then queries on the sampled graph are answered by simply accessing the stored graph. This may require prohibitive amounts of time, space and random bits, especially when only a small number of queries are actually issued. Instead, we propose to generate the graph on-the-fly, in response to queries, and therefore to require amounts of time, space, and random bits which are a function of the actual number of queries. We focus on two random graph models: the Barabási-Albert Preferential Attachment model (BA-graphs) and the random recursive tree model. We give on-the-fly generation algorithms for both models. With probability 1-1/poly(n), each and every query is answered in polylog(n) time, and the increase in space and the number of random bits consumed by any single query are both polylog(n), where n denotes the number of vertices in the graph. Our results show that, although the BA random graph model is defined by a sequential process, efficient random access to the graph's nodes is possible. In addition to the conceptual contribution, efficient on-the-fly generation of random graphs can serve as a tool for the efficient simulation of sublinear algorithms over large BA-graphs, and the efficient estimation of their performance on such graphs.

In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided error testing algorithms in the general graph model. We first describe a general procedure for converting $ε$-testers with a number of rounds $f(D)$, where $D$ denotes the diameter of the graph, to $O((\log n)/ε)+f((\log n)/ε)$ rounds, where $n$ is the number of processors of the network. We then apply this procedure to obtain an optimal tester, in terms of $n$, for testing bipartiteness, whose round complexity is $O(ε^{-1}\log n)$, which improves over the $poly(ε^{-1} \log n)$-round algorithm by Censor-Hillel et al. (DISC 2016). Moreover, for cycle-freeness, we obtain a \emph{corrector} of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property. In the second part of the paper we design algorithms for testing whether the network is $H$-free for any connected $H$ of size up to four with round complexity of $O(ε^{-1})$. This improves over the $O(ε^{-2})$-round algorithms for testing triangle freeness by Censor-Hillel et al. (DISC 2016) and for testing excluded graphs of size $4$ by Fraigniaud et al. (DISC 2016). In the last part we generalize the global tester by Iwama and Yoshida (ITCS 2014) of testing $k$-path freeness to testing the exclusion of any tree of order $k$. We then show how to simulate this algorithm in the CONGEST-model in $O(k^{k^2+1}\cdotε^{-k})$ rounds.

Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O~(poly(Delta/epsilon)n^{2/3}), where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanning subgraph of bounded stretch i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n * (Delta+log n)/epsilon) hops in the output that connects its endpoints.

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine whether a given edge e is in a specific spanning tree, without computing the whole spanning tree, but rather by inspecting the local neighborhood of e. The challenge is to maintain consistency. That is, to answer queries about different edges according to the same spanning tree. Since it is known that this problem cannot be solved without essentially viewing all the graph, we consider the relaxed version of finding a spanning subgraph with (1+c)n edges instead of n-1 edges (where n is the number of vertices and c is a given approximation/sparsity parameter). It is known that this relaxed problem requires inspecting order of n^{1/2} edges in general graphs (for any constant c), which motivates the study of natural restricted families of graphs. One such family is the family of graphs with an excluded minor (which in particular includes planar graphs). For this family there is an algorithm that achieves constant success probability, and inspects (d/c)^{poly(h)log(1/c)} edges (for each edge it is queried on), where d is the maximum degree in the graph and h is the size of the excluded minor. The distances between pairs of vertices in the spanning subgraph G' are at most a factor of poly(d, 1/c, h) larger than in G. In this work, we show that for an input graph that is H-minor free for any H of size h, this task can be performed by inspecting only poly(d, 1/c, h) edges in G. The distances between pairs of vertices in the spanning subgraph G' are at most a factor of h log(d)/c (up to poly-logarithmic factors) larger than in G. Furthermore, the error probability of the new algorithm is significantly improved to order of 1/n. This algorithm can also be easily adapted to yield an efficient algorithm for the distributed (message passing) setting.

Leskovec, Kleinberg and Faloutsos (2005) observed that many social networks exhibit properties such as shrinking (i.e. bounded) diameter, densification, and (power-law) heavy tail degree distributions. To explain these phenomena, they introduced a generative model, called the Forest Fire model, and using simulations showed that this model indeed exhibited these properties; however, proving this rigorously was left as an open problem. In this paper, we analyse one of these properties, shrinking diameter. We define a restricted version of their model that incorporates the main features that seem to contribute towards this property, and prove that the graphs generated by this model exhibit shrinking distance to the seed graph. We prove that an even simpler model, the random walk model, already exhibits this phenomenon.

No abstract available.

In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. This key aspect of LCAs generalizes various other models such as parallel algorithms, local filters and reconstructors. For graph problems, design techniques for LCAs and distributed algorithms are closely related and have been proven useful in each other's context. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. We consider the case where the parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in d and polylogarithmic in n; for constant eps > 0, a randomized LCA that provides a (1-ε)-approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.

Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient partition oracles . A partition oracle is a procedure that, given access to the incidence lists representation of a bounded-degree graph G = ( V,E ) and a parameter ϵ, when queried on a vertex v ∈ V , returns the part (subset of vertices) that v belongs to in a partition of all graph vertices. The partition should be such that all parts are small, each part is connected, and if the graph has certain properties, the total number of edges between parts is at most ϵ | V |. In this work, we give a partition oracle for graphs with excluded minors whose query complexity is quasi-polynomial in 1/ϵ, improving on the result of Hassidim et al. ( Proceedings of FOCS 2009 ), who gave a partition oracle with query complexity exponential in 1/ϵ. This improvement implies corresponding improvements in the complexity of testing planarity and other properties that are characterized by excluded minors as well as sublinear-time approximation algorithms that work under the promise that the graph has an excluded minor.

We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter and should reject collections that are relatively far from having this property. By “far” we mean that it is necessary to modify the distributions in a relatively significant manner (according to some predetermined distance measure) so as to obtain the property. We study this problem in two models. In the first model (the query model) the algorithm may ask for samples from any distribution of its choice, and in the second model (the sampling model) the distributions from which it gets samples are selected randomly. We provide upper and lower bounds in both models. In particular, in the query model, the complexity of the problem is polynomial in $1/\epsilon$ (where $\epsilon$ is the given distance parameter), while in the sampling model, the complexity grows roughly as $m^{1-{\rm poly}(\epsilon)}$, where $m$ is the number of distributions.

We present a simple adaptation of the Lempel Ziv 78' (LZ78) compression scheme that supports efficient random access to the input string. The compression algorithm is given as input a parameter ε > 0, and with very high probability increases the length of the compressed string by at most a factor of (1 + ε). The access time is O(log n + 1/ε2) in expectation, and O(log n/ε2) with high probability. The scheme relies on sparse transitive-closure spanners. Any (consecutive) substring of the input string can be retrieved at an additional additive cost in the running time of the length of the substring. The main benefit of the proposed scheme is that it preserves the online nature and simplicity of LZ78, and that for every input string, the length of the compressed string is only a small factor larger than that obtained by running LZ78.

A discrete distribution p, over [n], is a k histogram if its probability distribution function can be represented as a piece-wise constant function with k pieces. Such a function is represented by a list of k intervals and k corresponding values. We consider the following problem: given a collection of samples from a distribution p, find a k-histogram that (approximately) minimizes the l 2 distance to the distribution p. We give time and sample efficient algorithms for this problem.