We establish nearly optimal upper and lower bounds for approximating decision tree splits in data streams. For regression with labels in the range {0,1,…,M}, we give a one-pass algorithm using 𝒪̃(M²/ε) space that outputs a split within additive ε error of the optimal split, improving upon the two-pass algorithm of Pham et al. (ISIT 2025). Furthermore, we provide a matching one-pass lower bound showing that Ω(M²/ε) space is indeed necessary. For classification, we also obtain a one-pass algorithm using 𝒪̃(1/ε) space for approximating the optimal Gini split, improving upon the previous 𝒪̃(1/ε²)-space algorithm. We complement these results with matching space lower bounds: Ω(1/ε) for Gini impurity and Ω(1/ε) for misclassification (which matches the upper bound obtained by sampling). Our algorithms exploit the Lipschitz property of the loss functions and use reservoir sampling along with Count-Min sketches with range queries. Our lower bounds follow from careful reductions from the Index problem.

In this work, we present data stream algorithms to compute optimal splits for decision tree learning. In particular, given a data stream of observations$x_{i}$and their corresponding labels$y_{i}$, without the i.i.d. assumption, the objective is to identify the optimal split j that partitions the data into two sets, minimizing the mean squared error (for regression) or the misclassification rate and Gini impurity (for classification). We propose several efficient streaming algorithms that require sublinear space and use a small number of passes to solve these problems. Our work, while not directly comparable, complements the seminal work of Domingos-Hulten (KDD 2000) and Hulten-Spencer-Domingos (KDD 2001).

We revisit the maximum satisfiability problem (Max-SAT) in the data stream model. In this problem, the stream consists of m clauses that are disjunctions of literals drawn from n Boolean variables. The objective is to find an assignment to the variables that maximizes the number of satisfied clauses. Chou et al. (FOCS 2020) showed that Ω(n) space is necessary to yield a 2/2+ε approximation of the optimum value; they also presented an algorithm that yields a 2/2−ε approximation of the optimum value using O(ε−2log⁡n) space. In this paper, we not only focus on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear o(mn) space. We present randomized single-pass algorithms that w.h.p.1 yield: A 1−ε approximation using O˜(n/ε3) space and exponential post-processing time A 3/4−ε approximation using O˜(n/ε) space and polynomial post-processing time. We also consider the related minimum satisfiability problem (Min-SAT), introduced by Kohli et al. (SIAM J. Discrete Math. 1994), that asks to find an assignment that minimizes the number of satisfied clauses. For this problem, we give a O˜(n2/ε2) space algorithm, which is sublinear when m=ω(n), that yields an α+ε approximation where α is the approximation guarantee of the offline algorithm. If each variable appears in at most f clauses, we show that a 2fn approximation using O˜(n) space is possible. Finally, for the Max-AND-SAT problem where clauses are conjunctions of literals, we show that any single-pass algorithm that approximates the optimal value up to a factor better than 1/2 with success probability at least 2/3 must use Ω(mn) space.

We revisit the problem of finding small ε-separation keys introduced by Motwani and Xu (2008). In this problem, the input is a data set consisting of m-dimensional tuples {x1,x2,...,xn}. The goal is to find a small subset of coordinates that separates at least (1-ε)(n2) pairs of tuples. When n is large, they provided a fast algorithm that runs on Θ(m/ε) tuples sampled uniformly at random. We show that the sample size can be improved to Θ(m/√ε). Our algorithm also enjoys a faster running time.

Abstract. Given a graph [Formula: see text] with arboricity [Formula: see text], we study the problem of decomposing the edges of [Formula: see text] into [Formula: see text] disjoint forests in the distributed [Formula: see text] model. Here [Formula: see text] may be a simple graph or multigraph. While there is a polynomial time centralized algorithm for [Formula: see text]-forest decomposition (e.g., [H. Imai, J. Oper. Res. Soc. Japan, 26 (1983), pp. 186–211]), it remains an open question how close we can get to this exact decomposition in the [Formula: see text] model. Barenboim and Elkin [L. Barenboim and M. Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Distrib. Comput., 22 (2010), pp. 363–379] developed a [Formula: see text] algorithm to compute a [Formula: see text]-forest decomposition in [Formula: see text] rounds. Ghaffari and Su [ Proc. 28 th ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2505–2523] made further progress by computing a [Formula: see text]-forest decomposition in [Formula: see text] rounds when [Formula: see text]; i.e., the limit of their algorithm is an [Formula: see text]-forest decomposition. This algorithm, based on a combinatorial construction of Alon, McDiarmid, and Reed [ Combinatorica, 12 (1992), pp. 375–380], in fact provides a decomposition of the graph into star-forests, i.e., each forest is a collection of stars. Our main goal is to reduce the threshold of [Formula: see text] in [Formula: see text]-forest decomposition. We obtain a number of results with different parameters; some notable examples are the following: (1) An [Formula: see text]-round algorithm when [Formula: see text] in multigraphs, where [Formula: see text] is any arbitrary constant; (2) an [Formula: see text]-round algorithm when [Formula: see text] in multigraphs; (3) an [Formula: see text]-round algorithm when [Formula: see text] in multigraphs (this also covers an extension of the forest-decomposition problem to list-edge-coloring); (4) an [Formula: see text]-round algorithm for star-forest decomposition for [Formula: see text] in simple graphs (when [Formula: see text], this also covers a list-coloring variant). Our techniques also give an algorithm for [Formula: see text]-outdegree-orientation in [Formula: see text] rounds, which is the first algorithm with linear dependency on [Formula: see text]. At a high level, the first three results come from a combination of network decomposition, load balancing, and a new structural result on local augmenting sequences. The fourth result uses a more careful probabilistic analysis for the construction of Alon, McDiarmid, and Reed; the bounds on star-forest decomposition were not previously known even non constructively.

In submodular k-secretary problem, the goal is to select k items in a randomly ordered input so as to maximize the expected value of a given monotone submodular function on the set of selected items. In this paper, we introduce a relaxation of this problem, which we refer to as submodular k-secretary problem with shortlists. In the proposed problem setting, the algorithm is allowed to choose more than k items as part of a shortlist. Then, after seeing the entire input, the algorithm can choose a subset of size k from the bigger set of items in the shortlist. We are interested in understanding to what extent this relaxation can improve the achievable competitive ratio for the submodular k-secretary problem. In particular, using an O(k) sized shortlist, can an online algorithm achieve a competitive ratio close to the best achievable offline approximation factor for this problem? We answer this question affirmatively by giving a polynomial time algorithm that achieves a 1-1/e-epsilon-O(k^{-1}) competitive ratio for any constant epsilon>0, using a shortlist of size eta_epsilon(k)=O(k). This is especially surprising considering that the best known competitive ratio (in polynomial time) for the submodular k-secretary problem is (1/e-O(k^{-1/2}))(1-1/e) [Thomas Kesselheim and Andreas Tönnis, 2017]. The proposed algorithm also has significant implications for another important problem of submodular function maximization under random order streaming model and k-cardinality constraint. We show that our algorithm can be implemented in the streaming setting using a memory buffer of size eta_epsilon(k)=O(k) to achieve a 1-1/e-epsilon-O(k^{-1}) approximation. This result substantially improves upon [Norouzi-Fard et al., 2018], which achieved the previously best known approximation factor of 1/2 + 8 x 10^{-14} using O(k log k) memory; and closely matches the known upper bound for this problem [McGregor and Vu, 2017].

Given a graph G=(V,E) with arboricity a, we study the problem of decomposing the edges of G into (1+ε)a disjoint forests in the distributed LOCAL model. While there is a polynomial time centralized algorithm for a-forest decomposition (e.g. [Imai, J. Operation Research Soc. of Japan '83]), it remains an open question how close we can get to this exact decomposition in the LOCAL model.

The densest subgraph problem, introduced in the 80s by Picard and Queyranne as well as Goldberg, is a classic problem in combinatorial optimization with a wide range of applications. The lowest outdegree orientation problem is known to be its dual problem. We study both the problem of finding dense subgraphs and the problem of computing a low outdegree orientation in the distributed settings. Suppose $G=(V,E)$ is the underlying network as well as the input graph. Let $D$ denote the density of the maximum density subgraph of $G$. Our main results are as follows. Given a value $\tilde{D} \leq D$ and $0 < ε< 1$, we show that a subgraph with density at least $(1-ε)\tilde{D}$ can be identified deterministically in $O((\log n) / ε)$ rounds in the LOCAL model. We also present a lower bound showing that our result for the LOCAL model is tight up to an $O(\log n)$ factor. In the CONGEST model, we show that such a subgraph can be identified in $O((\log^3 n) / ε^3)$ rounds with high probability. Our techniques also lead to an $O(diameter + (\log^4 n)/ε^4)$-round algorithm that yields a $1-ε$ approximation to the densest subgraph. This improves upon the previous $O(diameter /ε\cdot \log n)$-round algorithm by Das Sarma et al. [DISC 2012] that only yields a $1/2-ε$ approximation. Given an integer $\tilde{D} \geq D$ and $Ω(1/\tilde{D}) < ε< 1/4$, we give a deterministic, $\tilde{O}((\log^2 n) /ε^2)$-round algorithm in the CONGEST model that computes an orientation where the outdegree of every vertex is upper bounded by $(1+ε)\tilde{D}$. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in $\tilde{O}((\log^6 n)/ ε^4)$ rounds and $\tilde{O}((\log^3 n) /ε^3)$ rounds respectively and only work in the LOCAL model.

Vizing showed that it suffices to color the edges of a simple graph using Δ + 1 colors, where Δ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Δ + Θ(√Δ))-edge-coloring algorithm that runs in (n) rounds by Chang et al. [SODA 2018] and the deterministic (Δ + (n))-edge-coloring algorithm that runs in (Δ, logn) rounds by Ghaffari et al. [STOC 2018].

We study distributed algorithms for some fundamental problems in data summarization. Given a communication graph $G$ of $n$ nodes each of which may hold a value initially, we focus on computing $\sum_{i=1}^N g(f_i)$, where $f_i$ is the number of occurrences of value $i$ and $g$ is some fixed function. This includes important statistics such as the number of distinct elements, frequency moments, and the empirical entropy of the data. In the CONGEST model, a simple adaptation from streaming lower bounds shows that it requires $\tildeΩ(D+ n)$ rounds, where $D$ is the diameter of the graph, to compute some of these statistics exactly. However, these lower bounds do not hold for graphs that are well-connected. We give an algorithm that computes $\sum_{i=1}^{N} g(f_i)$ exactly in $τ_G \cdot 2^{O(\sqrt{\log n})}$ rounds where $τ_G$ is the mixing time of $G$. This also has applications in computing the top $k$ most frequent elements. We demonstrate that there is a high similarity between the GOSSIP model and the CONGEST model in well-connected graphs. In particular, we show that each round of the GOSSIP model can be simulated almost-perfectly in $\tilde{O}(τ_G $ rounds of the CONGEST model. To this end, we develop a new algorithm for the GOSSIP model that $1\pm ε$ approximates the $p$-th frequency moment $F_p = \sum_{i=1}^N f_i^p$ in $\tilde{O}(ε^{-2} n^{1-k/p})$ rounds, for $p \geq2$, when the number of distinct elements $F_0$ is at most $O\left(n^{1/(k-1)}\right)$. This result can be translated back to the CONGEST model with a factor $\tilde{O}(τ_G)$ blow-up in the number of rounds.

We study the classic NP-Hard problem of finding the maximum k -set coverage in the data stream model: given a set system of m sets that are subsets of a universe \(\{1,\ldots ,n \}\) , find the k sets that cover the most number of distinct elements. The problem can be approximated up to a factor \(1-1/e\) in polynomial time. In the streaming-set model, the sets and their elements are revealed online. The main goal of our work is to design algorithms, with approximation guarantees as close as possible to \(1-1/e\) , that use sublinear space \(o(mn)\) . Our main results are: Two \((1-1/e-\epsilon )\) approximation algorithms: One uses \(O(\epsilon ^{-1})\) passes and \(\tilde {O}(\epsilon ^{-2} k)\) space whereas the other uses only a single pass but \(\tilde {O}(\epsilon ^{-2} m)\) space. \(\tilde {O}(\cdot )\) suppresses polylog factors. We show that any approximation factor better than \((1-(1-1/k)^{k})\approx 1-1/e\) in constant passes requires \({\Omega }(m)\) space for constant k even if the algorithm is allowed unbounded processing time. We also demonstrate a single-pass , \((1-\epsilon )\) approximation algorithm using \(\tilde {O}\left (\epsilon ^{-2} m \cdot \min (k,\epsilon ^{-1})\right )\) space. We also study the maximum k -vertex coverage problem in the dynamic graph stream model. In this model, the stream consists of edge insertions and deletions of a graph on N vertices. The goal is to find k vertices that cover the most number of distinct edges. We show that any constant approximation in constant passes requires \({\Omega }(N)\) space for constant k whereas \(\tilde {O}(\epsilon ^{-2}N)\) space is sufficient for a \((1-\epsilon )\) approximation and arbitrary k in a single pass. For regular graphs, we show that \(\tilde {O}(\epsilon ^{-3}k)\) space is sufficient for a \((1-\epsilon )\) approximation in a single pass. We generalize this to a \((\kappa -\epsilon )\) approximation when the ratio between the minimum and maximum degree is bounded below by \(\kappa \) .

Modern data streams typically have high dimensionality. For example, digital analytics streams consist of user online activities (e.g., web browsing activity, commercial site activity, apps and social behavior, and response to ads). An important problem is to find frequent joint values (heavy hitters) of subsets of dimensions.

We present space-efficient data stream algorithms for approximating the number of triangles in a graph up to a factor 1+ε. While it can be shown that determining whether a graph is triangle-free is not possible in sub-linear space, a large body of work has focused on minimizing the space required in terms of the number of triangles T (or a lower bound on this quantity) and other parameters including the number of nodes n and the number of edges m. Two models are important in the literature: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order and the adjacency list order model in which all edges incident to the same node appear consecutively. We improve over the state of the art results in both models. For the adjacency list order model, we show that ~O(ε-2m/√T) space is sufficient in one pass and ~O(ε-2m3/2/T) space is sufficient in two passes where the ~O(·) notation suppresses log factors. For the arbitrary order model, we show that ~O(ε-2m/√T) space suffices given two passes and that ~O(ε-2m3/2/T) space suffices given three passes and oracle access to the degrees. Finally, we show how to efficiently implement the "wedge sampling" approach to triangle estimation in the arbitrary order model. To do this, we develop the first algorithm for lp sampling such that multiple independent samples can be generated with O(polylog n) update time; this primitive is widely applicable and this result may be of independent interest.