2019/09/05 by Justin Chen, Christopher Eur, Chen, Justin +5
Computer Science · Mathematics · #05B35 #05E40 #06A12 #13D02 #68Q32 #Algebraic number #Betti number #Boolean function #Combinatorics #Combinatorics (math.CO) #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #Computer science #Dimension (graph theory) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Function (biology) #Intersection (aeronautics) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Mathematics #Matroid #Order (exchange) #Partially ordered set #Pure mathematics #Set (abstract data type) #Topological and Geometric Data Analysis #cs.LG #math.AC #math.CO #msc:05B35 #msc:05E40 #msc:06A12 #msc:13D02 #msc:68Q32
paper · pdf · doi:10.48550/arxiv.1909.02159
18 pages with figures. Final journal version, to appear in Advances in Applied Mathematics
openalex publication_date 2019/09/05 · arxiv created 2020/06/16 · arxiv updated 2020/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.