An Automatic Inequality Prover and Instance Optimal Identity Testing

DOI10.1137/151002526zbMath1362.62107OpenAlexW2592411267MaRDI QIDQ2968159

Gregory Valiant, Paul Valiant

Publication date: 10 March 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/151002526

zbMATH Keywords

Hölder's inequalitychi-squared testproperty testinginstance optimalityidentity testinginequality prover

Mathematics Subject Classification ID

Related Items (25)

Hypothesis testing for high-dimensional multinomials: a selective review ⋮ Local minimax rates for closeness testing of discrete distributions ⋮ Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models ⋮ Analysis of COVID-19 evolution based on testing closeness of sequential data ⋮ The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution ⋮ Goodness-of-fit testing for Hölder continuous densities under local differential privacy ⋮ Geometric reduction for identity testing of reversible Markov chains ⋮ On the \(\alpha\)-lazy version of Markov chains in estimation and testing problems ⋮ From Gauss to Kolmogorov: localized measures of complexity for ellipses ⋮ Testing shape restrictions of discrete distributions ⋮ On the power of conditional samples in distribution testing ⋮ Recovering Structured Probability Matrices ⋮ Proofs of Proximity for Distribution Testing ⋮ Quantum spectrum testing ⋮ Testing Data Binnings ⋮ Multinomial goodness-of-fit based on \(U\)-statistics: high-dimensional asymptotic and minimax optimality ⋮ Minimax optimal conditional independence testing ⋮ Hypothesis testing for densities and high-dimensional multinomials: sharp local minimax rates ⋮ Improving and extending the testing of distributions for shape-restricted properties ⋮ Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint ⋮ Unnamed Item ⋮ Optimal Stopping Rules for Sequential Hypothesis Testing ⋮ Testing Probability Distributions using Conditional Samples ⋮ Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample

Cites Work

• On Testing Expansion in Bounded-Degree Graphs
• Testing Symmetric Properties of Distributions
• Estimating Entropy on<tex>$m$</tex>Bins Given Fewer Than<tex>$m$</tex>Samples
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• Streaming and sublinear approximation of entropy and information distances
• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
• Estimation of Entropy and Mutual Information
• Sampling algorithms
• Instance optimal learning of discrete distributions
• Testing Identity of Structured Distributions
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Testing Closeness of Discrete Distributions
• Estimating the unseen
• Probability and Computing
• The Power of Linear Estimators
• The Complexity of Approximating the Entropy

This page was built for publication: An Automatic Inequality Prover and Instance Optimal Identity Testing