Buchumschlag

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ta, Hoang, Vu, Hoa T.
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Constructing Decision Trees from Data Streams
von: Pham, Huy, et al.
Veröffentlicht: (2024)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Near-Optimal Four-Cycle Counting in Graph Streams
von: Lüderssen, Sebastian, et al.
Veröffentlicht: (2026)

Nearly Optimal Bounds for Stochastic Online Sorting
von: Hu, Yang
Veröffentlicht: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
von: Karpov, Nikolai, et al.
Veröffentlicht: (2025)

High-Dimensional Geometric Streaming for Nearly Low Rank Data
von: Esfandiari, Hossein, et al.
Veröffentlicht: (2024)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
von: Black, Hadley
Veröffentlicht: (2023)

Streaming Maximal Matching with Bounded Deletions
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Fast and Simple Densest Subgraph with Predictions
von: Bui, Thai, et al.
Veröffentlicht: (2025)

Elastic Sketch under Random Stationary Streams: Limiting Behavior and Near-Optimal Configuration
von: Mazziane, Younes Ben, et al.
Veröffentlicht: (2026)

New Algorithms and Lower Bounds for Streaming Tournaments
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Fitting Tree Metrics and Ultrametrics in Data Streams
von: Carmel, Amir, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Nearly Optimal List Labeling
von: Bender, Michael A., et al.
Veröffentlicht: (2024)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
von: Hunkenschröder, Christoph, et al.
Veröffentlicht: (2025)

Efficient Approximation of Quantum Channel Fidelity Exploiting Symmetry
von: Chee, Yeow Meng, et al.
Veröffentlicht: (2023)

The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions
von: Zhao, Fuheng, et al.
Veröffentlicht: (2023)

Nearly Tight Bounds for the Online Sorting Problem
von: Azar, Yossi, et al.
Veröffentlicht: (2025)

Massively Parallel Maximum Coverage Revisited
von: Bui, Thai, et al.
Veröffentlicht: (2024)

Nearly Optimal Internal Dictionary Matching
von: Chen, Jingbang, et al.
Veröffentlicht: (2023)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
von: Bishnu, Arijit, et al.
Veröffentlicht: (2024)

Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
von: Staus, Luca Pascal, et al.
Veröffentlicht: (2024)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Transposition is Nearly Optimal for IID List Update
von: Coester, Christian
Veröffentlicht: (2026)

Near-Optimal Heaps and Dijkstra on Pointer Machines
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2026)

Near-Optimal Property Testers for Pattern Matching
von: Jin, Ce, et al.
Veröffentlicht: (2025)

Near-Optimal Directed Low-Diameter Decompositions
von: Bringmann, Karl, et al.
Veröffentlicht: (2025)

Near-Optimal Dimension Reduction for Facility Location
von: Huang, Lingxiao, et al.
Veröffentlicht: (2024)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
von: Chhabra, Adil, et al.
Veröffentlicht: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
von: Sulser, Aurelio L., et al.
Veröffentlicht: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
von: Das, Syamantak, et al.
Veröffentlicht: (2024)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

An Optimal Density Bound for Discretized Point Patrolling
von: Mishra, Ahan
Veröffentlicht: (2025)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
von: Kacham, Praneeth, et al.
Veröffentlicht: (2023)

Streaming Graph Algorithms in the Massively Parallel Computation Model
von: Czumaj, Artur, et al.
Veröffentlicht: (2025)

A Near-Optimal Kernel for a Coloring Problem
von: Haviv, Ishay, et al.
Veröffentlicht: (2025)