Trace bound for the hereditary discrepancy

Bernard Chazelle, Alexey Lvov

Research output: Contribution to conferencePaperpeer-review

8 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 - 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