The Power of Linear Estimators

DOI10.1109/FOCS.2011.81MaRDI QIDQ5494980zbMATH OpenOpenAlexFDO

Authors Gregory Valiant, Paul Valiant

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2011.81

Mathematics Subject Classification ID

Foundational topics in statistics (62A99) Statistical aspects of information-theoretic topics (62B10) Randomized algorithms (68W20) Measures of information, entropy (94A17)

Cited in

(21)

• Testing shape restrictions of discrete distributions
• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• Sample complexity of the distinct elements problem
• Optimal rates of entropy estimation over Lipschitz balls
• Analysis of COVID-19 evolution based on testing closeness of sequential data
• Estimation of Wasserstein distances in the spiked transport model
• An automatic inequality prover and instance optimal identity testing
• Sampling correctors
• A chasm between identity and equivalence testing with conditional queries
• Recovering structured probability matrices
• Optimal stopping rules for sequential hypothesis testing
• Approximate profile maximum likelihood
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Lifting uniform learners via distributional decomposition
• Public coin interactive proofs for label-invariant distribution properties
• Complexity of high-dimensional identity testing with coordinate conditional sampling
• Learning and testing irreducible Markov chains via the k-cover time
• Testing product distributions: a closer look
• Sample efficient identity testing and independence testing of quantum states
• Testing cluster structure of graphs
• On estimation of L_r-norms in Gaussian white noise models

This page was built for publication: The Power of Linear Estimators

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