Trace bound for the hereditary discrepancy

Bernard Chazelle, Alexey Lvov

Research output: Contribution to conferencePaper

6 Scopus citations

Abstract

A trace bound is proven for the hereditary discrepancy for a set system. This trace bound allows to resolve discrepancy-type questions for spectral methods had previously failed. In conjunction with the spectral lemma for linear circuits, new complexity bounds for range searching are also derived.

Original languageEnglish (US)
Pages64-69
Number of pages6
StatePublished - Jan 1 2000
Event16th Annual Symposium on Computational Geometry - Hong Kong, Hong Kong
Duration: Jun 12 2000Jun 14 2000

Other

Other16th Annual Symposium on Computational Geometry
CityHong Kong, Hong Kong
Period6/12/006/14/00

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Trace bound for the hereditary discrepancy'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Lvov, A. (2000). Trace bound for the hereditary discrepancy. 64-69. Paper presented at 16th Annual Symposium on Computational Geometry, Hong Kong, Hong Kong, .