Distribution testing lower bounds via reductions from communication complexity

DOI10.4230/LIPICS.CCC.2017.28MaRDI QIDQ5111158zbMATH OpenFDO

Authors Eric Blais, Clement L. Canonne, Tom Gur

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.28

zbMATH Keywords

communication complexitydistribution testingfunctional analysislower boundssimultaneous message passing

Mathematics Subject Classification ID

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

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

(8)

• Distribution-free testing for monomials with a sublinear number of queries
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Which Distribution Distances are Sublinearly Testable?
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Distribution testing lower bounds via reductions from communication complexity
• Testing isomorphism in the bounded-degree graph model
• On the complexity of estimating the effective support size
• Local goodness-of-fit testing for Hölder-continuous densities: minimax rates

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 Q5111158)