Bernard Chazelle, Princeton University and NECI
October 17, 4:30 PM, Rutgers Univ. CORE building Room 430
Abstract.
We prove a general lower bound for the
hereditary discrepancy of a set system
in terms of the traces of various matrices
derived from it. The advantage of this
bound is that the traces in question have combinatorial
meaning and in many cases it is quite
easy to approximate them. This allows us
to prove new discrepancy bounds (and rederive
old ones much more easily).
For example, we can show that the discrepancy
of n points and n lines is about n^{1/6},
as opposed to n^{1/4} for points and triangles.
We also derive new bounds for boxes and points
when the dimension is not fixed.
By using a variant of the spectral lemma
for linear circuits, we can use these discrepancy
results to prove lower bounds on the complexity
of various range searching problems.
(This is joint work with Alexey Lvov)