15 citations · 82 across the 26 of their papers we have counts for
4 papers · 1 filter
A learning problem that is independent of the set theory ZFC axioms
Shai Ben-David, Pavel Hrubes, Shay Moran +2
We consider the following statistical estimation problem: given a family F of real valued functions over some domain X and an i.i.d. sample drawn from an unknown distribution P ove…
Active classification with comparison queries
Daniel M. Kane, Shachar Lovett, Shay Moran +1
We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For…
Near-optimal linear decision trees for k-SUM and related problems
Daniel M. Kane, Shachar Lovett, Shay Moran
We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant , we construct linear de…
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski +3
In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of t…