15 citations · 82 across the 23 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2019
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
Mark Braverman, Gillat Kol, Shay Moran +1
We study the Convex Set Disjointness (CSD) problem, where two players have input sets taken from an arbitrary fixed domain~ of size . T…
cs.DS2018
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…
cs.DS2012
Shattering, Graph Orientations, and Connectivity
Laszlo Kozma, Shay Moran
We present a connection between two seemingly disparate fields: VC-theory and graph theory. This connection yields natural correspondences between fundamental concepts in VC-theory…