2026-07-20T14:44:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10131 2024-03-06T10:45:27Z ddc:004 open_access

Adventures in Monotone Complexity and TFNP Göös, Mika Kamath, Pritish Robere, Robert Sokolov, Dmitry TFNP Monotone Complexity Communication Complexity Proof Complexity 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and Pritish Kamath and Robert Robere and Dmitry Sokolov 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.38 urn:nbn:de:0030-drops-101316 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.38 eng https://creativecommons.org/licenses/by/3.0/legalcode