4 papers
Formal Models of Active Learning from Contrastive Examples
Farnam Mansouri, Hans U. Simon, Adish Singla +2
Machine learning can greatly benefit from providing learning algorithms with pairs of contrastive training examples -- typically pairs of instances that differ only slightly, yet h…
The Word Problem for Products of Symmetric Groups
Hans U. Simon
The word problem for products of symmetric groups (WPPSG) is a well-known NP-complete problem. An input instance of this problem consists of ``specification sets'' $X_1,\ldots,X_m…
The Hierarchy of Saturating Matching Numbers
Hans U. Simon, Jan Arne Telle
In this paper, we study three matching problems all of which came up quite recently in the field of machine teaching. The cost of a matching is defined in such a way that, for some…
RTD-Conjecture and Concept Classes Induced by Graphs
Hans U. Simon
It is conjectured that the recursive teaching dimension of any finite concept class is upper-bounded by the VC-dimension of this class times a universal constant. In this paper, we…