20 citations · 164 across the 63 of their papers we have counts for
5 papers · 1 filter
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg +1
An important result in discrepancy due to Banaszczyk states that for any set of vectors in of norm at most and any convex body in …
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…
Probabilistic Existence of Large Sets of Designs
Shachar Lovett, Sankeerth Rao, Alexander Vardy
A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been recentlyintroduced by Kuperberg, Lovett, and Peled (STOC 2012). Us…
The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
Daniel Kane, Shachar Lovett, Sankeerth Rao
Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan…