Výsledky vyhledávání
- 1.0582265 - MÚ 2025 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Hubáček, Pavel - Khaniki, Erfan - Thapen, Neil
TFNP intersections through the lens of feasible disjunction.
15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2024 - (Guruswami, V.), č. článku 63. Leibniz International Proceedings in Informatics (LIPIcs), 287. ISBN 978-3-95977-309-6.
[15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Berkeley (US), 30.01.2024-02.02.2024]
Grant CEP: GA ČR(CZ) GX19-27871X; GA ČR(CZ) GA23-04825S
Institucionální podpora: RVO:67985840
Klíčová slova: TFNP * feasible disjunction * proof complexity * TFNP intersection classes
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Trvalý link: https://hdl.handle.net/11104/0350365Název souboru Staženo Velikost Komentář Verze Přístup Hubacek.pdf 0 785.4 KB Vydavatelský postprint povolen - 2.0574198 - MÚ 2024 RIV US eng J - Článek v odborném periodiku
Folwarczný, Lukáš
On protocols for monotone feasible interpolation.
ACM Transactions on Computation Theory. Roč. 15, 1-2 (2023), č. článku 2. ISSN 1942-3454
Institucionální podpora: RVO:67985840
Klíčová slova: circuit complexity * communication complexity * proof complexity
Obor OECD: Pure mathematics
Impakt faktor: 0.7, rok: 2022
Způsob publikování: Omezený přístup
https://doi.org/10.1145/3583754
Trvalý link: https://hdl.handle.net/11104/0344548Název souboru Staženo Velikost Komentář Verze Přístup Folwarczny1.pdf 1 492.8 KB Vydavatelský postprint vyžádat - 3.0560276 - MÚ 2024 RIV NL eng J - Článek v odborném periodiku
Jeřábek, Emil
On the proof complexity of logics of bounded branching.
Annals of Pure and Applied Logic. Roč. 174, č. 1 (2023), č. článku 103181. ISSN 0168-0072. E-ISSN 1873-2461
Grant CEP: GA ČR(CZ) GA19-05497S
Institucionální podpora: RVO:67985840
Klíčová slova: proof complexity * modal logic * intermediate logic * extended Frege system
Obor OECD: Pure mathematics
Impakt faktor: 0.8, rok: 2022
Způsob publikování: Omezený přístup
https://doi.org/10.1016/j.apal.2022.103181
Trvalý link: https://hdl.handle.net/11104/0333265Název souboru Staženo Velikost Komentář Verze Přístup Jerabek.pdf 0 789.5 KB Vydavatelský postprint vyžádat - 4.0559510 - MÚ 2023 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Khaniki, Erfan
Nisan-Wigderson generators in proof complexity: New lower bounds.
37th Computational Complexity Conference (CCC 2022). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2022 - (Lovett, S.), s. 1-15, č. článku 17. Leibniz International Proceedings in Informatics, 234. ISBN 978-3-95977-241-9. ISSN 1868-8969.
[37th Computational Complexity Conference (CCC 2022). Philadelphia (US), 20.07.2022-23.07.2022]
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: proof complexity * bounded arithmetic * bounded depth Frege * Nisan-Wigderson generators
Obor OECD: 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.2022.17
Trvalý link: https://hdl.handle.net/11104/0332787Název souboru Staženo Velikost Komentář Verze Přístup Khaniki1.pdf 2 703.9 KB Vydavatelský postprint povolen - 5.0549748 - MÚ 2022 NL eng J - Článek v odborném periodiku
Jalali Keshavarz, Raheleh
Proof complexity of substructural logics.
Annals of Pure and Applied Logic. Roč. 172, č. 7 (2021), č. článku 102972. ISSN 0168-0072. E-ISSN 1873-2461
Grant CEP: GA ČR(CZ) GA19-05497S
Institucionální podpora: RVO:67985840
Klíčová slova: proof complexity * subintuitionistic logics * substructural logics
Obor OECD: Pure mathematics
Impakt faktor: 0.776, rok: 2021
Způsob publikování: Omezený přístup
https://doi.org/10.1016/j.apal.2021.102972
Trvalý link: http://hdl.handle.net/11104/0325667Název souboru Staženo Velikost Komentář Verze Přístup Jalali.pdf 4 558.1 KB Vydavatelský postprint vyžádat - 6.0546771 - MÚ 2022 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
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]
Institucionální podpora: RVO:67985840
Klíčová slova: proof complexity * polynomial calculus * nullstellensatz * sums-of-squares * Sherali-Adams
Obor OECD: 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
Trvalý link: http://hdl.handle.net/11104/0323158Název souboru Staženo Velikost Komentář Verze Přístup deRezende2.pdf 0 699.8 KB Vydavatelský postprint povolen - 7.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 - 8.0540454 - MÚ 2022 RIV CH eng J - Článek v odborném periodiku
de Rezende, Susanna F. - Meir, O. - Norström, J. - Robere, R.
Nullstellensatz size-degree trade-offs from reversible pebbling.
Computational Complexity. Roč. 30, č. 1 (2021), č. článku 4. ISSN 1016-3328. E-ISSN 1420-8954
Institucionální podpora: RVO:67985840
Klíčová slova: nullstellensatz * pebbling * proof complexity * trade-offs
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.962, rok: 2021
Způsob publikování: Omezený přístup
https://doi.org/10.1007/s00037-020-00201-y
Trvalý link: http://hdl.handle.net/11104/0318083Název souboru Staženo Velikost Komentář Verze Přístup DeRezende.pdf 0 514.8 KB Vydavatelský postprint vyžádat - 9.0531886 - MÚ 2021 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
de Rezende, Susanna F. - Nordstöm, J. - Risse, K. - Sokolov, D.
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs.
35th Computational Complexity Conference (CCC 2020). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2020 - (Shubhangi, S.), č. článku 28. Leibniz International Proceedings in Informatics, 169. ISBN 978-3-95977-156-6. ISSN 1868-8969.
[35th Computational Complexity Conference (CCC 2020). Saarbrücken (DE), 28.07.2020-31.07.2020]
Institucionální podpora: RVO:67985840
Klíčová slova: proof complexity * resolution * weak pigeonhole principle * perfect matching * sparse graphs
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.4230/LIPIcs.CCC.2020.28
Trvalý link: http://hdl.handle.net/11104/0310520Název souboru Staženo Velikost Komentář Verze Přístup deRezende.pdf 0 643.9 KB Vydavatelský postprint povolen - 10.0523857 - MÚ 2021 RIV US eng J - Článek v odborném periodiku
Galesi, N. - Talebanfard, Navid - Torán, J.
Cops-Robber games and the resolution of Tseitin formulas.
ACM Transactions on Computation Theory. Roč. 12, č. 2 (2020), č. článku 9. ISSN 1942-3454
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: theory of computation * proof complexity * graph theory
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Způsob publikování: Omezený přístup
https://doi.org/10.1145/3378667
Trvalý link: http://hdl.handle.net/11104/0308136Název souboru Staženo Velikost Komentář Verze Přístup Talebanfard.pdf 2 422.9 KB Vydavatelský postprint vyžádat