Sample compression schemes were defined by Littlestone and Warmuth (1986) as an
abstraction of the structure underlying many learning algorithms. Roughly speaking, a …

Formal models of learning from teachers need to respect certain criteria to avoid collusion.
The most commonly accepted notion of collusion-avoidance was proposed by Goldman and …

We introduce a new model of teaching named" preference-based teaching" and a
corresponding complexity parameter--the preference-based teaching dimension (PBTD) …

We examine connections between combinatorial notions that arise in machine learning and
topological notions in cubical/simplicial geometry. These connections enable to export …

A hypothesis class admits a sample compression scheme, if for every sample labeled by a
hypothesis from the class, it is possible to retain only a small subsample, using which the …

It is a long-standing open problem whether there exists a compression scheme whose size
is of the order of the Vapnik-Chervonienkis (VC) dimension d. Recently compression …

Formal models of learning from teachers need to respect certain criteria to avoid collusion.
The most commonly accepted notion of collusion-freeness was proposed by Goldman and …

This work studies distributed learning in the spirit of Yao's model of communication
complexity: consider a two-party setting, where each of the players gets a list of labelled …

We give an algorithmically efficient version of the learner-to-compression scheme
conversion in Moran and Yehudayoff (2016). We further extend this technique to real-valued …

We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid
certain sub-structures. In particular, we characterize the classical and parameterized …