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 language | English (US) |
---|---|
Pages | 64-69 |
Number of pages | 6 |
State | Published - 2000 |
Event | 16th Annual Symposium on Computational Geometry - Hong Kong, Hong Kong Duration: Jun 12 2000 → Jun 14 2000 |
Other
Other | 16th Annual Symposium on Computational Geometry |
---|---|
City | Hong Kong, Hong Kong |
Period | 6/12/00 → 6/14/00 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics