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
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10131/
Go to the corresponding LIPIcs Volume Portal

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

Adventures in Monotone Complexity and TFNP

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

Abstract

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

@InProceedings{gs_et_al:LIPIcs:2018:10131,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2018/10131},
  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