Sublinear algorithms for testing monotone and unimodal distributions

DOI10.1145/1007352.1007414zbMATH Open1192.68345OpenAlexW2129311580MaRDI QIDQ3580983FDOQ3580983

Authors: Tuğkan Batu, Ravi Kumar, Ronitt Rubinfeld 

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007414

Recommendations

• Testing monotone high‐dimensional distributions
• Testing monotone high-dimensional distributions
• Testing \(k\)-modal distributions: optimal algorithms via reductions
• Learning \(k\)-modal distributions via testing
• Learning \(k\)-modal distributions via testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (26)

• Improving and extending the testing of distributions for shape-restricted properties
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Hypothesis testing for high-dimensional multinomials: a selective review
• Testing monotone high-dimensional distributions
• Testing monotone high‐dimensional distributions
• Testing probability distributions using conditional samples
• Testing monotone continuous distributions on high-dimensional real cubes
• Testing monotone continuous distributions on high-dimensional real cubes
• Linear time algorithms for Abelian group isomorphism and related problems
• Testing closeness of discrete distributions
• Sampling correctors
• Distribution-free testing for monomials with a sublinear number of queries
• A chasm between identity and equivalence testing with conditional queries
• Sampling correctors
• Testing permutation properties through subpermutations
• Invariance in property testing
• Recovering structured probability matrices
• Learning \(k\)-modal distributions via testing
• Sample-based high-dimensional convexity testing
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Which Distribution Distances are Sublinearly Testable?
• Testing shape restrictions of discrete distributions
• Learning \(k\)-modal distributions via testing
• Testing \(k\)-modal distributions: optimal algorithms via reductions
• The geometry of hypothesis testing over convex cones: generalized likelihood ratio tests and minimax radii
• Big data on the rise? Testing monotonicity of distributions

This page was built for publication: Sublinear algorithms for testing monotone and unimodal distributions

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