Entropy, Randomization, Derandomization, and Discrepancy
 Title:

Entropy, Randomization, Derandomization, and Discrepancy
 Author(s):

Gnewuch, Michael
 Date:

2011
 Type:

Technical reports
 Department(s):

Computer Science
 Persistent URL:

http://hdl.handle.net/10022/AC:P:10678
 Series:

Columbia University Computer Science Technical Reports
 Part Number:

CUCS02011
 Publisher:

Department of Computer Science, Columbia University
 Publisher Location:

New York
 Abstract:

The star discrepancy is a measure of how uniformly distributed a finite point set is in the ddimensional unit cube. It is related to highdimensional numerical integration of certain function classes as expressed by the KoksmaHlawka inequality. A sharp version of this inequality states that the worstcase error of approximating the integral of functions from the unit ball of some Sobolev space by an equalweight cubature is exactly the star discrepancy of the set of sample points. In many applications, as, e.g., in physics, quantum chemistry or finance, it is essential to approximate highdimensional integrals. Thus with regard to the Koksma Hlawka inequality the following three questions are very important: (i) What are good bounds with explicitly given dependence on the dimension d for the smallest possible discrepancy of any npoint set for moderate n? (ii) How can we construct point sets efficiently that satisfy such bounds? (iii) How can we calculate the discrepancy of given point sets efficiently? We want to discuss these questions and survey and explain some approaches to tackle them relying on metric entropy, randomization, and derandomization.
 Subject(s):

Computer science
 Item views
 274
 Metadata:

text  xml
 Suggested Citation:
 Michael Gnewuch, 2011, Entropy, Randomization, Derandomization, and Discrepancy, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:10678.