Shattered sets and the Hilbert function

DOI10.4230/LIPICS.MFCS.2016.70zbMATH Open1398.90216arXiv1511.08245OpenAlexW2963511026MaRDI QIDQ4608633FDOQ4608633

Authors: Shay Moran, Cyrus Rashtchian 

Publication date: 21 March 2018

Abstract: We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result applies to a stronger regime in which the hyperplanes are fixed and only the directions of the inequalities are given as input to the circuit. We derive this result by proving that a rich class of extremal functions in VC theory cannot be approximated by low-degree polynomials. We also present applications of algebra to combinatorics. We provide a new algebraic proof of the Sandwich Theorem, which is a generalization of the well-known Sauer-Perles-Shelah Lemma. Finally, we prove a structural result about downward-closed sets, related to the Chv'{a}tal conjecture in extremal combinatorics.

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

Recommendations

• A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma
• On the Hilbert function of complementary set families
• Representations of monotone Boolean functions by linear programs
• Representations of monotone Boolean functions by linear programs
• Shattering news

zbMATH Keywords

linear programmingHilbert functionpolynomial methodVC dimensionsandwich theoremshattered setsChvàtal's conjecturedownward-closed sets

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Extremal combinatorics (05D99)

Cited In (6)

• A Sauer-Shelah-Perles lemma for lattices
• Exploring implications of trace (inversion) formula and Artin algebras in extremal combinatorics
• On the Hilbert function of complementary set families
• A Sauer-Shelah-Perles lemma for sumsets
• A uniform version of a theorem by Dvir and Moran
• A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma

This page was built for publication: Shattered sets and the Hilbert function

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