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