A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma

DOI10.4230/LIPIcs.ITCS.2018.56zbMath1462.68063OpenAlexW2785698234MaRDI QIDQ4993326

Greg Yang

Publication date: 15 June 2021

Full work available at URL: https://dblp.uni-trier.de/db/conf/innovations/innovations2018.html#Yang18

zbMATH Keywords

Stanley-Reisner ringVC-dimensionhomologycellular resolutionhomological Farkas lemma

Mathematics Subject Classification ID

Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Singular homology and cohomology theory (55N10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computation of Hilbert functions
• The expressive power of voting polynomials
• Unifying known lower bounds via geometric complexity theory
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Algebrization
• The topological structure of asynchronous computability
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Lectures on Polytopes
• Homotopy Type Theory: Univalent Foundations of Mathematics
• Decision tree complexity and Betti numbers
• Natural proofs

This page was built for publication: A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma