Distribution testing lower bounds via reductions from communication complexity

DOI10.1145/3305270MaRDI QIDQ5205791zbMATH OpenOpenAlexWikidataFDO

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/

zbMATH Keywords

lower boundscommunication complexityproperty testingK-functionaldistribution testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication complexity, information complexity (68Q11)

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?

Cited in

(12)

• Distribution testing lower bounds via reductions from communication complexity
• 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?

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)