Free resolutions of function classes via order complexes

DOI10.1016/J.AAM.2020.102074MaRDI QIDQ2197912zbMATH OpenOpenAlexFDO

Authors Justin Chen, Christopher Eur, Greg Yang, Mengyuan Zhang

Publication date 1 September 2020

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.02159

zbMATH Keywords

VC dimensionStanley-Reisner idealorder complexessuboplexesMöbius function

Mathematics Subject Classification ID

Computational learning theory (68Q32) Combinatorics of partially ordered sets (06A07) Syzygies, resolutions, complexes and commutative rings (13D02) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Abstract: 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"obius functions. We then apply our methods to derive bounds on the VC dimension of some important families of function classes in learning theory.

Recommendations

• A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• VC Dimension Bounds for Analytic Algebraic Computations
• Some new maximum VC classes
• VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions

Cites work

• scientific article; zbMATH DE number 4027488 (Why is no real title available?)
• scientific article; zbMATH DE number 3771666 (Why is no real title available?)
• scientific article; zbMATH DE number 67609 (Why is no real title available?)
• scientific article; zbMATH DE number 3586175 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 2190625 (Why is no real title available?)
• Cohen-Macaulay quotients of polynomial rings
• Lectures on Polytopes
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Poset topology: tools and applications
• Resolutions of Stanley-Reisner rings and Alexander duality
• Shellable Decompositions of Cells and Spheres.
• Shellable Nonpure Complexes and Posets. I
• Shellable and Cohen-Macaulay Partially Ordered Sets
• The Geometry of Syzygies

Cited in

(1)

• A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma

Describes a project that uses

Uses Software

• Macaulay2

This page was built for publication: Free resolutions of function classes via order complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197912)