Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Testing monotone continuous distributions on high-dimensional real cubes

Tools
- Tools
+ Tools

Czumaj, Artur, Adamaszek, Michał and Sohler, Christian (2010) Testing monotone continuous distributions on high-dimensional real cubes. In: 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10), Austin, Texas, 17-19 Jan 2010. Published in: SIAM pp. 56-65. doi:10.1007/978-3-642-16367-8_13

[img] Text
SODA10_006_adamaszekm.pdf
Embargoed item. Restricted access to Repository staff only

Download (699Kb)

Request Changes to record.

Abstract

We study the task of testing properties of probability
distributions. We consider a scenario in which we
have access to independent samples of an unknown
distribution D with infinite (perhaps even uncountable)
support. Our goal is to test whether D has a given
property or it is "-far from it (in the statistical distance,
with the L1-distance measure).
It is not difficult to see that for many natural dis-
tributions on infinite or uncountable domains, no test-
ing algorithm can exist and the central objective of our
study is to understand if there are any nontrivial dis-
tributions that can be efficiently tested. For example,
it is easy to see that there is no testing algorithm that
tests if a given probability distribution on [0; 1] is uni-
form. We show however, that if some additional infor-
mation about the input distribution is known, testing
uniform distribution is possible. We extend the recent
result about testing uniformity for monotone distribu-
tions on Boolean n-dimensional cubes by Rubinfeld and
Servedio (STOC'2005) to the case of continuous [0; 1]n
cubes. We show that if a distribution D on [0; 1]n is
monotone, then one can test if D is uniform with the
sample complexity O(n="2). This result is optimal up
to a polylogarithmic factor.

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
Journal or Publication Title: SIAM
Official Date: 17 January 2010
Dates:
DateEvent
17 January 2010Published
Page Range: pp. 56-65
DOI: 10.1007/978-3-642-16367-8_13
Status: Not Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access (Creative Commons)
Conference Paper Type: Paper
Title of Event: 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10)
Type of Event: Conference
Location of Event: Austin, Texas
Date(s) of Event: 17-19 Jan 2010
Related URLs:
  • http://www.siam.org/meetings/da10/

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us