The discrepancy method

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

1 Scopus citations

Abstract

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
Pages1-3
Number of pages3
ISBN (Print)3540653856, 9783540653851
DOIs
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

Other

Other9th Annual International Symposium on Algorithms and Computation, ISAAC'98
CountryKorea, Republic of
CityTaejon
Period12/14/9812/16/98

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Chazelle, B. (1998). The discrepancy method. In Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings (pp. 1-3). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1533 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-49381-6_1