Standard

Adventures in monotone complexity and TFNP. / Göös, Mika; Kamath, Pritish; Robere, Robert; Sokolov, Dmitry.

10th Innovations in Theoretical Computer Science, ITCS 2019. ed. / Avrim Blum. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 38 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 124).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Göös, M, Kamath, P, Robere, R & Sokolov, D 2019, Adventures in monotone complexity and TFNP. in A Blum (ed.), 10th Innovations in Theoretical Computer Science, ITCS 2019., 38, Leibniz International Proceedings in Informatics, LIPIcs, vol. 124, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 10th Innovations in Theoretical Computer Science, ITCS 2019, San Diego, United States, 10/01/19. https://doi.org/10.4230/LIPIcs.ITCS.2019.38

APA

Göös, M., Kamath, P., Robere, R., & Sokolov, D. (2019). Adventures in monotone complexity and TFNP. In A. Blum (Ed.), 10th Innovations in Theoretical Computer Science, ITCS 2019 [38] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 124). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2019.38

Vancouver

Göös M, Kamath P, Robere R, Sokolov D. Adventures in monotone complexity and TFNP. In Blum A, editor, 10th Innovations in Theoretical Computer Science, ITCS 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 38. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.ITCS.2019.38

Author

Göös, Mika ; Kamath, Pritish ; Robere, Robert ; Sokolov, Dmitry. / Adventures in monotone complexity and TFNP. 10th Innovations in Theoretical Computer Science, ITCS 2019. editor / Avrim Blum. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inproceedings{991ba7dee0854abb88447d44b8d76a5d,
title = "Adventures in monotone complexity and TFNP",
abstract = "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).",
keywords = "Communication complexity, Monotone complexity, Proof complexity, TFNP",
author = "Mika G{\"o}{\"o}s and Pritish Kamath and Robert Robere and Dmitry Sokolov",
year = "2019",
month = jan,
day = "1",
doi = "10.4230/LIPIcs.ITCS.2019.38",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Avrim Blum",
booktitle = "10th Innovations in Theoretical Computer Science, ITCS 2019",
address = "Germany",
note = "10th Innovations in Theoretical Computer Science, ITCS 2019 ; Conference date: 10-01-2019 Through 12-01-2019",

}

RIS

TY - GEN

T1 - Adventures in monotone complexity and TFNP

AU - Göös, Mika

AU - Kamath, Pritish

AU - Robere, Robert

AU - Sokolov, Dmitry

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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).

AB - 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).

KW - Communication complexity

KW - Monotone complexity

KW - Proof complexity

KW - TFNP

UR - http://www.scopus.com/inward/record.url?scp=85069538955&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2019.38

DO - 10.4230/LIPIcs.ITCS.2019.38

M3 - Conference contribution

AN - SCOPUS:85069538955

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 10th Innovations in Theoretical Computer Science, ITCS 2019

A2 - Blum, Avrim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 10th Innovations in Theoretical Computer Science, ITCS 2019

Y2 - 10 January 2019 through 12 January 2019

ER -

ID: 52048030