License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.70
URN: urn:nbn:de:0030-drops-64814
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6481/
Go to the corresponding LIPIcs Volume Portal

Moran, Shay ; Rashtchian, Cyrus

Shattered Sets and the Hilbert Function

pdf-format:
LIPIcs-MFCS-2016-70.pdf (0.8 MB)

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 demonstrates that a large and natural family of 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 Chvatal conjecture in extremal combinatorics.

BibTeX - Entry

@InProceedings{moran_et_al:LIPIcs:2016:6481,
  author =	{Shay Moran and Cyrus Rashtchian},
  title =	{{Shattered Sets and the Hilbert Function}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6481},
  URN =		{urn:nbn:de:0030-drops-64814},
  doi =		{10.4230/LIPIcs.MFCS.2016.70},
  annote =	{Keywords: VC dimension, shattered sets, sandwich theorem, Hilbert function, polynomial method, linear programming, Chvatal's conjecture, downward-closed sets}
}

Keywords: VC dimension, shattered sets, sandwich theorem, Hilbert function, polynomial method, linear programming, Chvatal's conjecture, downward-closed sets
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI