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).

Abstract An ( n , R )-covering sequence is a cyclic sequence whose consecutive n -tuples form a code of length n and covering radius R . Using several construction methods improvements of the upper bounds on the length of such sequences for $$n \le 20$$ n ≤ 20 and $$1 \le R \le 3$$ 1 ≤ R ≤ 3 , are obtained. The definition is generalized in two directions. An ( n , m , R )-covering sequence code is a set of cyclic sequences of length m whose consecutive n -tuples form a code of length n and covering radius R . The definition is also generalized to arrays in which the $$m \times n$$ m × n sub-matrices form a covering code with covering radius R . We prove that asymptotically there are covering sequences that attain the sphere-covering bound up to a constant factor.

Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon $in$\mathrm {poly}(1/\epsilon, \text {input dimension})$time, compared to the$\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.

An$(m, n, R)-\mathbf{de}$Bruijn covering array (dBCA) is a doubly periodic$M\times N$array over an alphabet of size$q$such that the set of all its$m\times n$windows form a covering code with radius$R$. An upper bound of the smallest array area of an$(m, n, R)-\mathbf{dBCA}$is provided using a probabilistic technique which is similar to the one that was used for an upper bound on the length of a de Bruijn covering sequence. A folding technique to construct a dBCA from a de Bruijn covering sequence or de Bruijn covering sequences code is presented. Several new constructions that yield shorter de Bruijn covering sequences and$(m, n, R)-\mathbf{dBCAs}$with smaller areas are also provided. These constructions are mainly based on sequences derived from cyclic codes, self-dual sequences, primitive polynomials, an interleaving technique, folding, and mutual shifts of sequences with the same covering radius. Finally, constructions of de Bruijn covering sequences codes are also discussed.

In this paper, we study the asymptotic nonnegative rank of matrices, which characterizes the asymptotic growth of the nonnegative rank of fixed nonnegative matrices under the Kronecker product. This quantity is important since it governs several notions in information theory such as the so-called exact Renyi common information and the amortized communication complexity. By using the theory of asymptotic spectra of V. Strassen (J. Reine Angew. Math. 1988), we define formally the asymptotic spectrum of nonnegative matrices and give a dual characterization of the asymptotic nonnegative rank. Comple-mentary to the nonnegative rank, we introduce the notion of the sub rank of a nonnegative matrix and show that it is exactly equal to the size of the maximum induced matching of the bipartite graph defined on the support of the matrix (therefore, independent of the value of entries). Finally, we show that two matrix parameters, namely rank and fractional cover number, belong to the asymptotic spectrum of nonnegative matrices.

Graph Neural Networks (GNNs), known as spectral graph filters, find a wide range of applications in web networks. To bypass eigendecomposition, polynomial graph filters are proposed to approximate graph filters by leveraging various polynomial bases for filter training. However, no existing studies have explored the diverse polynomial graph filters from a unified perspective for optimization.

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.

The de Bruijn based timing and synchronization (dBTS) system has been proposed and studied recently for some channels require reliable synchronization, such as quantum communication. To avoid a long period of no-pulse in the dBTS system, we propose to study the run length limited de Bruijn sequences which not only are run length limited sequences but also can be used to locate the location of any sub-string. Such subjects are expected to have various applications and they also present some interesting theoretical questions in combinatorics, algorithms and coding theory.In this paper, we are the first to provide an explicit formula of the maximal length of the run length limited de Bruijn sequences. Besides that, using Lyndon words, we present an efficient construction of a run length limited de Bruijn sequence with the maximal length. Furthermore, we also provide a sub-linear decoding algorithm which can locate the position of an arbitrary sub-string.