LIPIcs.ICALP.2018.82.pdf
- Filesize: 477 kB
- 13 pages
Document
Generalized Comparison Trees for Point-Location Problems
Authors
Daniel M. Kane 
,
Shachar Lovett ,
Shay Moran
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
File
Document Identifiers
Author Details
- Department of Computer Science and Engineering/Department of Mathematics, University of California, San Diego
Cite As Get BibTex
Daniel M. Kane, Shachar Lovett, and Shay Moran. Generalized Comparison Trees for Point-Location Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 82:1-82:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.82
Abstract
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 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.
Subject Classification
ACM Subject Classification
- Theory of computation
Keywords
- linear decision trees
- comparison queries
- point location problems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Franck Barthe. On a reverse form of the Brascamp-Lieb inequality. Inventiones mathematicae, 134(2):335-361, 1998.
-
Jean Cardinal, John Iacono, and Aurélien Ooms. Solving k-sum using few linear queries. arXiv preprint arXiv:1512.06678, 2015.
-
Esther Ezra and Micha Sharir. A nearly quadratic bound for the decision tree complexity of k-sum. In 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, pages 41:1-41:15, 2017.
- Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci., 65(4):612-625, 2002. URL: http://dx.doi.org/10.1016/S0022-0000(02)00019-3.
-
Michael L Fredman. How good is the information theory bound in sorting? Theoretical Computer Science, 1(4):355-361, 1976.
-
Daniel Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on. IEEE, 2017.
- Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k-sum and related problems. CoRR, abs/1705.01720, 2017. URL: http://arxiv.org/abs/1705.01720.
-
Daniel M. Kane, Shachar Lovett, and Shay Moran. Generalized comparison trees for point-location problems. Electronic Colloquium on Computational Complexity (ECCC), 2018.
-
Stefan Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106(2):286-303, 1993.
-
Friedhelm Meyer auf der Heide. A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM (JACM), 31(3):668-676, 1984.
- Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389-434, 2012. URL: http://dx.doi.org/10.1007/s10208-011-9099-z.
-
VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability &Its Applications, 16(2):264-280, 1971.