1 Search Results for "Yang, Greg"

Document
DOI: 10.4230/LIPIcs.ITCS.2018.56
A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma

Authors: Greg Yang

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
In computational complexity, a complexity class is given by a set of problems or functions, and a basic challenge is to show separations of complexity classes A != B especially when A is known to be a subset of B. In this paper we introduce a homological theory of functions that can be used to establish complexity separations, while also providing other interesting consequences. We propose to associate a topological space S_A to each class of functions A, such that, to separate complexity classes A from a superclass B', it suffices to observe a change in "the number of holes", i.e. homology, in S_A as a subclass B of B' is added to A. In other words, if the homologies of S_A and S_{A union B} are different, then A != B'. We develop the underlying theory of functions based on homological commutative algebra and Stanley-Reisner theory, and prove a "maximal principle" for polynomial threshold functions that is used to recover Aspnes, Beigel, Furst, and Rudich's characterization of the polynomial threshold degree of symmetric functions. A surprising coincidence is demonstrated, where, roughly speaking, the maximal dimension of "holes" in S_A upper bounds the VC dimension of A, with equality for common computational cases such as the class of polynomial threshold functions or the class of linear functionals over the finite field of 2 elements, or common algebraic cases such as when the Stanley-Reisner ring of S_A is Cohen-Macaulay. As another interesting application of our theory, we prove a result that a priori has nothing to do with complexity separation: it characterizes when a vector subspace intersects the positive cone, in terms of homological conditions. By analogy to Farkas' result doing the same with linear conditions, we call our theorem the Homological Farkas Lemma.
Cite as

Greg Yang. A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{yang:LIPIcs.ITCS.2018.56,
  author =	{Yang, Greg},
  title =	{{A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{56:1--56:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.56},
  URN =		{urn:nbn:de:0030-drops-83436},
  doi =		{10.4230/LIPIcs.ITCS.2018.56},
  annote =	{Keywords: Homology, Stanley-Reisner, Cellular resolution, VC dimension, Homological Farkas}
}
  • Refine by Author
  • 1 Yang, Greg

  • Refine by Classification

  • Refine by Keyword
  • 1 Cellular resolution
  • 1 Homological Farkas
  • 1 Homology
  • 1 Stanley-Reisner
  • 1 VC dimension

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact