IEEE - Institute of Electrical and Electronics Engineers, Inc. - Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)

Author(s): Ilias Diakonikolas ; Daniel M. Kane ; Vladimir Nikishkin
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 October 2015
Conference Location: Berkeley, CA, USA
Conference Date: 17 October 2015
Page(s): 1,183 - 1,202
ISBN (Electronic): 978-1-4673-8191-8
ISSN (Paper): 0272-5428
DOI: 10.1109/FOCS.2015.76
Regular:

We give a general unified method that can be used for L1 closeness testing of a wide range of univariate structured distribution families. More specifically, we design a sample optimal... View More

Advertisement