The Library
Proofs of proximity for distribution testing
Tools
Chiesa, Alessandro and Gur, Tom (2018) Proofs of proximity for distribution testing. In: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Published in: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 94 53:1-53:14. ISBN 9783959770606. doi:10.4230/LIPIcs.ITCS.2018.53 ISSN 1868-8969.
|
PDF
WRAP-proofs-proximity-distribution-testing-Gur-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (547Kb) | Preview |
Official URL: http://drops.dagstuhl.de/opus/volltexte/2018/8311
Abstract
Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large number of samples to test, which motivates the question of whether there are natural settings wherein fewer samples suffice. We initiate a study of proofs of proximity for properties of distributions. In their basic form, these proof systems consist of a tester that not only has sample access to a distribution but also explicit access to a proof string that depends on the distribution. We refer to these as NP distribution testers, or MA distribution testers if the tester is a probabilistic algorithm. We also study the more general notion of IP distribution testers, in which the tester interacts with an all-powerful untrusted prover. We investigate the power and limitations of proofs of proximity for distributions and chart a landscape that, surprisingly, is significantly different from that of proofs of proximity for functions. Our main results include showing that MA distribution testers can be quadratically stronger than standard distribution testers, but no stronger than that; in contrast, IP distribution testers can be exponentially stronger than standard distribution testers, but when restricted to public coins they can be at best quadratically stronger.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Distribution (Probability theory) | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) | ||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
Place of Publication: | Dagstuhl, Germany | ||||||
ISBN: | 9783959770606 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 5 January 2018 | ||||||
Dates: |
|
||||||
Volume: | 94 | ||||||
Page Range: | 53:1-53:14 | ||||||
DOI: | 10.4230/LIPIcs.ITCS.2018.53 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 11 April 2019 | ||||||
Date of first compliant Open Access: | 11 April 2019 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) | ||||||
Type of Event: | Conference |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year