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.ITCS.2019.38
URN: urn:nbn:de:0030-drops-101316
Go to the corresponding LIPIcs Volume Portal

Göös, Mika ; Kamath, Pritish ; Robere, Robert ; Sokolov, Dmitry

Adventures in Monotone Complexity and TFNP

LIPIcs-ITCS-2019-38.pdf (0.8 MB)


Separations: We introduce a monotone variant of Xor-Sat and show it has exponential monotone circuit complexity. Since Xor-Sat is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite fields. These results can be interpreted as separating subclasses of TFNP in communication complexity.
Characterizations: We show that the communication (resp. query) analogue of PPA (subclass of TFNP) captures span programs over F_2 (resp. Nullstellensatz degree over F_2). Previously, it was known that communication FP captures formulas (Karchmer - Wigderson, 1988) and that communication PLS captures circuits (Razborov, 1995).

BibTeX - Entry

  author =	{Mika G{\"o}{\"o}s and Pritish Kamath and Robert Robere and Dmitry Sokolov},
  title =	{{Adventures in Monotone Complexity and TFNP}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{38:1--38:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-101316},
  doi =		{10.4230/LIPIcs.ITCS.2019.38},
  annote =	{Keywords: TFNP, Monotone Complexity, Communication Complexity, Proof Complexity}

Keywords: TFNP, Monotone Complexity, Communication Complexity, Proof Complexity
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

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