Free resolutions of function classes via order complexes
This work provides theoretical insights into function classes in learning theory, but it is incremental as it builds on prior algebraic frameworks.
The paper tackles the problem of understanding algebraic properties of ideals associated with intersection-closed function classes, showing that their multigraded Betti numbers are pure and given combinatorially by Möbius functions, and applies this to derive bounds on the VC dimension for families in learning theory.
Function classes are collections of Boolean functions on a finite set, which are fundamental objects of study in theoretical computer science. We study algebraic properties of ideals associated to function classes previously defined by the third author. We consider the broad family of intersection-closed function classes, and describe cellular free resolutions of their ideals by order complexes of the associated posets. For function classes arising from matroids, polyhedral cell complexes, and more generally interval Cohen-Macaulay posets, we show that the multigraded Betti numbers are pure, and are given combinatorially by the Möbius functions. We then apply our methods to derive bounds on the VC dimension of some important families of function classes in learning theory.