Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
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
