Výsledky vyhledávání
- 1.0543415 - MÚ 2022 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
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]
Institucionální podpora: RVO:67985840
Klíčová slova: proof complexity * automatability * pigeonhole principle * algebraic proof systems * lower bounds
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.1145/3406325.3451080
Trvalý link: http://hdl.handle.net/11104/0320627Název souboru Staženo Velikost Komentář Verze Přístup deRezende1.pdf 0 1 MB Vydavatelský postprint povolen - 2.0539558 - MÚ 2021 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
de Rezende, Susanna F. - Meir, O. - Norström, J. - Pitassi, T. - Robere, R. - Vinyals, M.
Lifting with simple gadgets and applications to circuit and proof complexity.
2020 IEEE 61st Annual Symposium on Foundations of Computer Science. Los Alamitos: IEEE, 2020, s. 24-30. ISBN 978-1-7281-9622-0.
[61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. Durham (US), 16.11.2020-19.11.2020]
Institucionální podpora: RVO:67985840
Klíčová slova: circuit complexity * communication complexity * cutting planes
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.1109/FOCS46700.2020.00011
Trvalý link: http://hdl.handle.net/11104/0317277Název souboru Staženo Velikost Komentář Verze Přístup deRezende2.pdf 0 209.6 KB Vydavatelský postprint vyžádat - 3.0539556 - MÚ 2021 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
de Rezende, Susanna F. - Meir, O. - Norström, J. - Pitassi, T. - Robere, R.
Krw composition theorems via lifting.
2020 IEEE 61st Annual Symposium on Foundations of Computer Science. Los Alamitos: IEEE, 2020, s. 43-49. ISBN 978-1-7281-9622-0.
[61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. Durham (US), 16.11.2020-19.11.2020]
Institucionální podpora: RVO:67985840
Klíčová slova: circuit complexity * circuit lower bounds * communication complexity
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.1109/FOCS46700.2020.00013
Trvalý link: http://hdl.handle.net/11104/0317276Název souboru Staženo Velikost Komentář Verze Přístup deRezende1.pdf 0 223.9 KB Vydavatelský postprint vyžádat - 4.0174806 - MU-W 990013 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Krajíček, Jan - Pudlák, Pavel - Beame, P. - Impagliazzo, R. - Pitassi, T.
Lower bounds on Hilbert's nullstellensatz and propositional proofs.
Annual Symposium on Foundation of Computer Science. Santa Fe: IEEE Computer Scientific Press, 1994, s. 794-806.
[Annual Symposium on Foundation of Computer Science. Santa Fe (US), 20.11.1994-22.11.1994]
Kód oboru RIV: BA - Obecná matematika
Trvalý link: http://hdl.handle.net/11104/0071805Název souboru Staženo Velikost Komentář Verze Přístup Krajicek.pdf 1 1.1 MB Vydavatelský postprint vyžádat