DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.42

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams

Authors: Hoang Ta and Hoa T. Vu

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Hoang Ta and Hoa T. Vu. Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ta_et_al:LIPIcs.ESA.2026.42,
  author =	{Ta, Hoang and Vu, Hoa T.},
  title =	{{Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.42},
  URN =		{urn:nbn:de:0030-drops-271785},
  doi =		{10.4230/LIPIcs.ESA.2026.42},
  annote =	{Keywords: Decision trees, Streaming algorithms, Lower bounds}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2022.48

Larger Corner-Free Sets from Combinatorial Degenerations

Authors: Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model. Versions of this problem and the NOF connection have seen much interest (and progress) in recent works of Linial, Pitassi and Shraibman (ITCS 2019) and Linial and Shraibman (CCC 2021). We introduce and study a general algebraic method for lower bounding the Shannon capacity of directed hypergraphs via combinatorial degenerations, a combinatorial kind of "approximation" of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which play an important role there) but which we use in a novel way. Using the combinatorial degeneration method, we make progress on the corner problem by explicitly constructing a corner-free subset in F₂ⁿ × F₂ⁿ of size Ω(3.39ⁿ/poly(n)), which improves the previous lower bound Ω(2.82ⁿ) of Linial, Pitassi and Shraibman (ITCS 2019) and which gets us closer to the best upper bound 4^{n - o(n)}. Our new construction of corner-free sets implies an improved NOF protocol for the Eval problem. In the Eval problem over a group G, three players need to determine whether their inputs x₁, x₂, x₃ ∈ G sum to zero. We find that the NOF communication complexity of the Eval problem over F₂ⁿ is at most 0.24n + 𝒪(log n), which improves the previous upper bound 0.5n + 𝒪(log n).

Cite as

Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam. Larger Corner-Free Sets from Combinatorial Degenerations. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{christandl_et_al:LIPIcs.ITCS.2022.48,
  author =	{Christandl, Matthias and Fawzi, Omar and Ta, Hoang and Zuiddam, Jeroen},
  title =	{{Larger Corner-Free Sets from Combinatorial Degenerations}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{48:1--48:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.48},
  URN =		{urn:nbn:de:0030-drops-156441},
  doi =		{10.4230/LIPIcs.ITCS.2022.48},
  annote =	{Keywords: Corner-free sets, communication complexity, number on the forehead, combinatorial degeneration, hypergraphs, Shannon capacity, eval problem}
}

Search Results

Documents authored by Ta, Hoang

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams

Abstract

Cite as

Larger Corner-Free Sets from Combinatorial Degenerations

Abstract

Cite as

Thanks for your feedback!

Could not send message