6 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…
A Note on the Subcubes of the -Cube
Hans Ulrich Simon
In the year 1990, Béla Bollobás, Imre Leader and Andrew Radcliffe considered the following combinatorial problem: given three parameters k, n and q, find a set of k vertices in the…
Greedy Matchings in Bipartite Graphs with Ordered Vertex Sets
Hans U. Simon
We define and study greedy matchings in vertex-ordered bipartite graphs. It is shown that each vertex-ordered bipartite graph has a unique greedy matching. The proof uses (a weak f…