Support testing in the huge object model

DOI10.4230/LIPICS.APPROX/RANDOM.2024.46MaRDI QIDQ6920792zbMATH OpenFDO

Authors Tomer Adar, Eldar Fischer, Amit Levi

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.46

zbMATH Keywords

property testinghuge-object model

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 3238444 (Why is no real title available?)
• scientific article; zbMATH DE number 3261634 (Why is no real title available?)
• scientific article; zbMATH DE number 7650357 (Why is no real title available?)
• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Estimating the unseen, improved estimators for entropy and other properties
• Introduction to Property Testing
• On testing expansion in bounded-degree graphs
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing distributions of huge objects

Cited in

(1)

• Testing support size more efficiently than learning histograms

This page was built for publication: Support testing in the huge object model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6920792)