Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-074 | 23rd April 2018 06:30

Generalized comparison trees for point-location problems


Authors: Daniel Kane, Shachar Lovett, Shay Moran
Publication: 23rd April 2018 09:28
Downloads: 443


Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$
can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from $H$; in particular, if all hyperplanes in $H$ are $k$-sparse then generalized comparisons are $2k$-sparse.
The depth of the obtained linear decision tree is polynomial in $d$ and logarithmic in $|H|$, which is comparable to previous results in the literature that use general linear queries.

This extends the study of comparison trees from a previous work by the authors [Kane {et al.}, FOCS 2017].
The main benefit is that using generalized comparison queries allows to overcome limitations that apply for the more restricted type of comparison queries.

Our analysis combines a seminal result of Forster
regarding sets in isotropic position [Forster, JCSS 2002],
the margin-based inference dimension analysis for comparison queries from [Kane {et al.}, FOCS 2017], and compactness arguments.

ISSN 1433-8092 | Imprint