Search results
- 1.0546771 - MÚ 2022 RIV DE eng C - Conference Paper (international conference)
de Rezende, Susanna F. - Lauria, M. - Nordström, J. - Sokolov, D.
The power of negative reasoning.
36th Computational Complexity Conference (CCC 2021). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2021 - (Kabanets, V.), č. článku 40. Leibniz International Proceedings in Informatics, 200. ISBN 978-3-95977-193-1. ISSN 1868-8969.
[36th Computational Complexity Conference (CCC 2021). Toronto (CA), 20.07.2021-23.07.2021]
Institutional support: RVO:67985840
Keywords : proof complexity * polynomial calculus * nullstellensatz * sums-of-squares * Sherali-Adams
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://dx.doi.org/10.4230/LIPIcs.CCC.2021.40
Permanent Link: http://hdl.handle.net/11104/0323158File Download Size Commentary Version Access deRezende2.pdf 0 699.8 KB Publisher’s postprint open-access - 2.0543415 - MÚ 2022 RIV US eng C - Conference Paper (international conference)
de Rezende, Susanna F. - Göös, M. - Nordström, J. - Pitassi, T. - Robere, R. - Sokolov, D.
Automating algebraic proof systems is NP-hard.
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. New York: ACM, 2021 - (Khuller, S.; Vassilevska Williams, V.), s. 209-222. ISBN 978-1-4503-8053-9.
[53rd Annual ACM SIGACT Symposium on Theory of Computing. Virtual (IT), 21.06.2021-25.06.2021]
Institutional support: RVO:67985840
Keywords : proof complexity * automatability * pigeonhole principle * algebraic proof systems * lower bounds
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.1145/3406325.3451080
Permanent Link: http://hdl.handle.net/11104/0320627File Download Size Commentary Version Access deRezende1.pdf 0 1 MB Publisher’s postprint open-access