Publication at Faculty of Mathematics and Physics |
2010
Abstract
Discrepancy theory is the study of irregularities of distributions. A typical question is: given a “complicated” distribution, find a “simple” one that approximates it well.
As it turns out, many questions in complexity theory can be reduced to problems of that type. This raises the possibility that the deep mathematical techniques of discrepancy theory might be of utility to theoretical computer scientists.
As will be discussed in this talk this is, indeed, the case. We will give several examples of breakthroughs derived through the application of the “discrepancy method.” Revised 2nd printing.