Fetching the paper…
Reading the bibliography…
Given a finite set $X \subset \mathbb{R}^d$ and a binary linear classifier $c: \mathbb{R}^d \to \{0,1\}$, how many queries of the form $c(x)$ are required to learn the label of every point in $X$? Known as \textit{point location}, this problem has inspired over 35 years of research in the pursuit of an optimal algorithm.
Time bounds for selection
Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan · 1973
Earlier work this paper cites.
Theory of pattern recognition, 1974
Vladimir Vapnik and Alexey Chervonenkis · 1974
Earlier work this paper cites.
Multidimensional searching problems
David Dobkin and Richard J Lipton · 1976
Earlier work this paper cites.
A polynomial linear search algorithm for the n-dimensional knapsack problem
Friedhelm Meyer auf der Heide · 1983
Earlier work this paper cites.
A theory of the learnable
Leslie G Valiant · 1984
Earlier work this paper cites.
Queries and concept learning
Dana Angluin · 1988
Earlier work this paper cites.
Point location in arrangements of hyperplanes
Stefan Meiser · 1993
Earlier work this paper cites.
Selective sampling using the query by committee algorithm
Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby · 1997
Earlier work this paper cites.
On a reverse form of the Brascamp-Lieb inequality
Franck Barthe · 1998
Cited alongside, same era.
A linear lower bound on the unbounded error probabilistic communication complexity
Jürgen Forster · 2002
Cited alongside, same era.
Coarse sample complexity bounds for active learning
Sanjoy Dasgupta · 2006
Cited alongside, same era.
Margin based active learning
Maria-Florina Balcan, Andrei Broder, and Tong Zhang · 2007
Cited alongside, same era.
Active and passive learning of linear separators under log-concave distributions
Maria-Florina Balcan and Phil Long · 2013
Cited alongside, same era.
Breaking the quadratic barrier for 3-LCCs over the reals
Zeev Dvir, Shubhangi Saraf, and Avi Wigderson · 2014
Cited alongside, same era.
An introduction to matrix concentration inequalities
Joel A Tropp et al · 2015
Later among the works it cites.
The optimal sample complexity of pac learning
Steve Hanneke · 2016
Later among the works it cites.
Active classification with comparison queries
Daniel M Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang · 2017
Later among the works it cites.
Sample and computationally efficient learning algorithms under s-concave distributions
Maria-Florina F Balcan and Hongyang Zhang · 2017
Later among the works it cites.
Near-optimal active learning of halfspaces via query synthesis in the noisy setting
Lin Chen, Hamed Hassani, and Amin Karbasi · 2017
Later among the works it cites.
A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
Esther Ezra and Micha Sharir · 2019
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jean Cardinal, John Iacono, and Aurélien Ooms · 2015
Cited alongside, same era.
Efficient active learning of halfspaces via query synthesis
Ibrahim Alabdulmohsin, Xin Gao, and Xiangliang Zhang · 2015
Cited alongside, same era.
Generalized comparison trees for point-location problems
Daniel Kane, Shachar Lovett, and Shay Moran
Cited in the paper.
Near-optimal linear decision trees for k-SUM and related problems
Daniel M Kane, Shachar Lovett, and Shay Moran
Cited in the paper.
Learnability and the Vapnik-Chervonenkis dimension
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth
Cited in the paper.
Learnability and the Vapnik-Chervonenkis dimension
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth
Cited in the paper.
Later among the works it cites.
The power of comparisons for actively learning linear classifiers
Max Hopkins, Daniel M Kane, and Shachar Lovett · 2019
Later among the works it cites.
Noise-tolerant, reliable active classification with comparison queries
Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan · 2020
Closest in time.