TY - GEN

T1 - The discrepancy method

AU - Chazelle, Bernard

PY - 1998

Y1 - 1998

N2 - 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".

AB - 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".

UR - http://www.scopus.com/inward/record.url?scp=84864684259&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864684259&partnerID=8YFLogxK

U2 - 10.1007/3-540-49381-6_1

DO - 10.1007/3-540-49381-6_1

M3 - Conference contribution

AN - SCOPUS:84864684259

SN - 3540653856

SN - 9783540653851

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 3

BT - Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings

PB - Springer Verlag

T2 - 9th Annual International Symposium on Algorithms and Computation, ISAAC'98

Y2 - 14 December 1998 through 16 December 1998

ER -