Entropy, Randomization, Derandomization, and Discrepancy

Michael Gnewuch

Entropy, Randomization, Derandomization, and Discrepancy
Gnewuch, Michael
Technical reports
Computer Science
Persistent URL:
Columbia University Computer Science Technical Reports
Part Number:
Department of Computer Science, Columbia University
Publisher Location:
New York
The star discrepancy is a measure of how uniformly distributed a finite point set is in the d-dimensional unit cube. It is related to high-dimensional numerical integration of certain function classes as expressed by the Koksma-Hlawka inequality. A sharp version of this inequality states that the worst-case error of approximating the integral of functions from the unit ball of some Sobolev space by an equal-weight 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 high-dimensional 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 n-point 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.
Computer science
Item views
text | xml
Suggested Citation:
Michael Gnewuch, 2011, Entropy, Randomization, Derandomization, and Discrepancy, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:10678.

Center for Digital Research and Scholarship at Columbia University Libraries | Policies