Distribution testing lower bounds via reductions from communication complexity
DOI10.1145/3305270zbMATH Open1440.68323OpenAlexW2914834722WikidataQ128489827 ScholiaQ128489827MaRDI QIDQ5205791FDOQ5205791
Authors: Eric Blais, Clement L. Canonne, Tom Gur 
Publication date: 16 December 2019
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7536/
Recommendations
- Distribution testing lower bounds via reductions from communication complexity
- Property testing lower bounds via communication complexity
- Testing \(k\)-modal distributions: optimal algorithms via reductions
- Sample-optimal identity testing with high probability
- Which Distribution Distances are Sublinearly Testable?
Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication complexity, information complexity (68Q11)
Cited In (12)
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Minimax optimal conditional independence testing
- Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
- Sparse signal detection in heteroscedastic Gaussian sequence models: sharp minimax rates
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Testing Data Binnings
- Distribution-free testing for monomials with a sublinear number of queries
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Lifting uniform learners via distributional decomposition
- Topics and Techniques in Distribution Testing: A Biased but Representative Sample
- Which Distribution Distances are Sublinearly Testable?
- Distribution testing lower bounds via reductions from communication complexity
This page was built for publication: Distribution testing lower bounds via reductions from communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205791)
