Geometric discrepancy revisited

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

10 Scopus citations

Abstract

Discrepancy theory addresses the general issue of approximating one measure by another one. Besides providing the theoretical foundation for sampling, it holds some of the keys to understanding the computational power of randomization. The contribution of this work is two-fold: we give elementary algorithms for estimating the discrepancy between various measures arising in practice, and we present a general techniques for proving discrepancy lower bounds.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundatons of Computer Science (Proceedings)
Editors Anon
PublisherPubl by IEEE
Pages392-399
Number of pages8
ISBN (Print)0818643706
StatePublished - Dec 1 1993
EventProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 3 1993Nov 5 1993

Publication series

NameAnnual Symposium on Foundatons of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 34th Annual Symposium on Foundations of Computer Science
CityPalo Alto, CA, USA
Period11/3/9311/5/93

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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

  • Cite this

    Chazelle, B. (1993). Geometric discrepancy revisited. In Anon (Ed.), Annual Symposium on Foundatons of Computer Science (Proceedings) (pp. 392-399). (Annual Symposium on Foundatons of Computer Science (Proceedings)). Publ by IEEE.