Trace bound for the hereditary discrepancy

Bernard Chazelle, Alexey Lvov

Research output: Contribution to conferencePaperpeer-review

7 Scopus citations


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)
Number of pages6
StatePublished - 2000
Event16th Annual Symposium on Computational Geometry - Hong Kong, Hong Kong
Duration: Jun 12 2000Jun 14 2000


Other16th Annual Symposium on Computational Geometry
CityHong Kong, Hong Kong

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


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

Cite this