Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

**
Geometric Complexity and the Discrepancy Method
**

**
Bernard Chazelle, Princeton University and NEC Research Institute**

Discrepancy theory is the study of irregularities
of distributions. A typical question
in *discrepancy theory* is:
given a ``complicated'' distribution, find a ``simple'' one
that approximates it well.
Surprisingly, many important questions in complexity theory can be
formulated in that way.
As a result, the deep mathematical techniques
of discrepancy theory developed over this century
have become acutely relevant to theoretical computer scientists.
Nowhere is discrepancy theory more advanced
than in the geometric arena. Predictably,
computational geometry is the field of computer science
that has benefited the most from this
connection to classical mathematics.
This talk will give several examples of
breakthroughs derived via the ``discrepancy method.''

Back