Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR18-163 | 18th September 2018 16:53

#### Adventures in Monotone Complexity and TFNP

TR18-163
Authors: Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
Publication: 18th September 2018 17:49
$\mathbf{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.
$\mathbf{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).