12 problems

Let $H$ be a hypergraph of VC-dimension $d$. A sample compression scheme for $H$ consists of a compression map and reconstruction map that encode every finite sample from $H$ using…

Let $F4F1\mathcal{F}\subseteq\{0,1\}^n$ be a $d$-maximum class, and consider its one-inclusion graph. The Peeling algorithm repeatedly removes a vertex of minimum degree and record…

A complex of oriented matroids (COM) is a set system arising from the covectors of a complex of oriented matroids; an ample class is a set system with the corresponding shattering…

Let a set system be a family of subsets of a domain, and let its VC-dimension be $d$. A labeled sample compression scheme of size $k$ compresses every labeled sample to a labeled s…

Let a complex of oriented matroids (COM) be a set family equipped with its VC-dimension, and let an ample partial cube be a partial cube with the ample property. A completion of a…

Let a complex of oriented matroids (COM) be a set family of VC-dimension $d$, and let an ample completion be an ample partial cube containing it. COM ample-completion conjecture. A…

Kuzmin–Warmuth corner conjecture. Every maximum class has a corner.

Let textup{{textsf{GKN}}} be the earlier gamma-net-based classification algorithm described in the paper, which removes a minimum vertex cover so that the remaining sample is gamma…

Let $C_1$ and $C_2$ be extremal classes with $C_1\subseteq C_2$ and $|C_2\setminus C_1|\geq 2$. Intermediate extremal-class conjecture. There exists an extremal class $C$ such that…

Let $C$ be an extremal class. A concept $c\in C$ is a corner of $C$ if $C\setminus\{c\}$ is extremal. Corner-peeling conjecture. Every nonempty extremal class $C$ has at least one…

Let a simple linear arrangement be a finite collection of hyperplanes in general position in $\mathbb{R}^d$, and let its cells define the associated maximum concept class. A hyperp…

Let $C$ be a maximum concept class of VC dimension $d$, represented by its one-inclusion graph. An unlabeled $d$-compression scheme assigns to each concept a subset of the domain o…