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 -