15 citations · 83 across the 28 of their papers we have counts for
4 papers · 1 filter
The entropy of lies: playing twenty questions with a liar
Yuval Dagan, Yuval Filmus, Daniel Kane +1
`Twenty questions' is a guessing game played by two players: Bob thinks of an integer between and , and Alice's goal is to recover it using a minimal number of Yes/No questi…
On the Perceptron's Compression
Shay Moran, Ido Nachum, Itai Panasoff +1
We study and provide exposition to several phenomena that are related to the perceptron's compression. One theme concerns modifications of the perceptron algorithm that yield bette…
Private PAC learning implies finite Littlestone dimension
Noga Alon, Roi Livni, Maryanthe Malliaris +1
We show that every approximately differentially private learning algorithm (possibly improper) for a class with Littlestone dimension~ requires exam…
Generalized comparison trees for point-location problems
Daniel M Kane, Shachar Lovett, Shay Moran
Let be an arbitrary family of hyper-planes in -dimensions. We show that the point-location problem for can be solved by a linear decision tree that only uses a special t…