Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-163 | 18th September 2018 16:53

Adventures in Monotone Complexity and TFNP

RSS-Feed




TR18-163
Authors: Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
Publication: 18th September 2018 17:49
Downloads: 218
Keywords: 


Abstract:

$\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).



ISSN 1433-8092 | Imprint