The discrepancy method

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings
PublisherSpringer Verlag
Number of pages3
ISBN (Print)3540653856, 9783540653851
StatePublished - 1998
Event9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of
Duration: Dec 14 1998Dec 16 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1533 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th Annual International Symposium on Algorithms and Computation, ISAAC'98
Country/TerritoryKorea, Republic of

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The discrepancy method'. Together they form a unique fingerprint.

Cite this