2019/01/01 by Mika Göös, Pritish Kamath, Robert Robere +1 · 1 voice · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #semigroups and automata theory #Machine Learning and Algorithms
paper · doi:10.4230/lipics.itcs.2019.38
Separations: We introduce a monotone variant of Xor-Sat and show it has exponential monotone circuit complexity. Since Xor-Sat is in NC2, 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 F2 (resp. Nullstellensatz degree over F2). Previously, it was known that communication FP captures formulas (Karchmer - Wigderson, 1988) and that communication PLS captures circuits (Razborov, 1995).