Výsledky vyhledávání
- 1.0559957 - MÚ 2023 RIV US eng J - Článek v odborném periodiku
Khaniki, Erfan
On proof complexity of resolution over polynomial calculus.
ACM Transactions on Computational Logic. Roč. 23, č. 3 (2022), č. článku 16. ISSN 1529-3785. E-ISSN 1557-945X
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: lower bounds * modular counting * Polynomial Calculus * propositional pigeonhole principle
Obor OECD: Pure mathematics
Impakt faktor: 0.5, rok: 2022
Způsob publikování: Omezený přístup
https://doi.org/10.1145/3506702
Trvalý link: https://hdl.handle.net/11104/0333080Název souboru Staženo Velikost Komentář Verze Přístup Khaniki2.pdf 2 302.2 KB Vydavatelský postprint vyžádat - 2.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 - 3.0542699 - MÚ 2022 RIV DE eng J - Článek v odborném periodiku
Buss, S. - Thapen, Neil
DRAT and propagation redundancy proofs without new variables.
Logical Methods in Computer Science. Roč. 17, č. 2 (2021), č. článku 12. ISSN 1860-5974. E-ISSN 1860-5974
Grant CEP: GA ČR(CZ) GA19-05497S
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: DRAT * extension * pigeonhole principle * proof logging
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.591, rok: 2021
Způsob publikování: Open access
https://dx.doi.org/10.23638/LMCS-17(2:12)2021
Trvalý link: http://hdl.handle.net/11104/0320071Název souboru Staženo Velikost Komentář Verze Přístup Thapen.pdf 3 499.7 KB Vydavatelský postprint povolen - 4.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 - 5.0507203 - ÚI 2020 DE eng J - Článek v odborném periodiku
Pich, Ján
Logical Strength of Complexity Theory and a Formalization of the PCP Theorem in Bounded Arithmetic.
Logical Methods in Computer Science. Roč. 11, č. 2 (2015), č. článku 8. ISSN 1860-5974. E-ISSN 1860-5974
Klíčová slova: weak pigeonhole principle * provability * hardness * np * Bounded arithmetic * Complexity theory * Formalizations
Impakt faktor: 0.569, rok: 2015
Trvalý link: http://hdl.handle.net/11104/0298247 - 6.0465189 - MÚ 2017 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
de Oliveira Oliveira, Mateus
Satisfiability via smooth pictures.
Theory and Applications of Satisfiability Testing – SAT 2016. Cham: Springer, 2016 - (Creignou, N.; Le Berre, D.), s. 13-28. Lecture Notes in Computer Science, 9710. ISBN 978-3-319-40969-6. ISSN 0302-9743.
[19th International Conference on Theory and Applications of Satisfiability Testing (SAT 2016). Bordeaux (FR), 05.07.2016-08.07.2016]
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: smooth pictures * bounded frege proof systems * pigeonhole principle
Kód oboru RIV: BA - Obecná matematika
http://link.springer.com/chapter/10.1007/978-3-319-40970-2_2
Trvalý link: http://hdl.handle.net/11104/0263852Název souboru Staženo Velikost Komentář Verze Přístup deOliveiraOliveira5.pdf 1 394.8 KB Vydavatelský postprint vyžádat - 7.0369680 - MÚ 2012 RIV GB eng J - Článek v odborném periodiku
Skelley, A. - Thapen, Neil
The provably total search problems of bounded arithmetic.
Proceedings of the London Mathematical Society. Roč. 103, č. 1 (2011), s. 106-138. ISSN 0024-6115. E-ISSN 1460-244X
Grant CEP: GA MŠMT LC505
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Pigeonhole principle * polynomial hierarchy * local search
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.324, rok: 2011
http://plms.oxfordjournals.org/content/103/1/106
Trvalý link: http://hdl.handle.net/11104/0203689Název souboru Staženo Velikost Komentář Verze Přístup Thapen2.pdf 6 329.4 KB Vydavatelský postprint vyžádat - 8.0175032 - MU-W 20025079 RIV PL eng J - Článek v odborném periodiku
Krajíček, Jan
On the weak pigeonhole principle.
Fundamenta Mathematicae. Roč. 170, 1-3 (2001), s. 123-140. ISSN 0016-2736. E-ISSN 1730-6329
Grant CEP: GA AV ČR IAA1019901
Klíčová slova: bounded arithmetic%weak pigeonhole principle
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.300, rok: 2001
Trvalý link: http://hdl.handle.net/11104/0072023Název souboru Staženo Velikost Komentář Verze Přístup Krajicek1.pdf 1 181.1 KB Vydavatelský postprint vyžádat - 9.0106825 - MU-W 20040032 RIV US eng J - Článek v odborném periodiku
Krajíček, Jan
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds.
[Duální slabý princip PHP, pseudosurjektivní funkce a dokazatelnost spodních odhadů pro obvody.]
Journal of Symbolic Logic. Roč. 69, č. 1 (2004), s. 265-286. ISSN 0022-4812. E-ISSN 1943-5886
Grant CEP: GA AV ČR IAA1019901
Výzkumný záměr: CEZ:AV0Z1019905
Klíčová slova: pseudo-surjective functions * pigeonhole principle
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.331, rok: 2004
Trvalý link: http://hdl.handle.net/11104/0013999Název souboru Staženo Velikost Komentář Verze Přístup Krajicek3.pdf 1 2.6 MB Vydavatelský postprint vyžádat - 10.0106824 - MU-W 20040031 RIV US eng J - Článek v odborném periodiku
Krajíček, Jan
Approximate Euler characteristic, dimension, and weak pigeonhole principles.
[Přibližná Eulerova charakteristika, dimenze a slabé principy PHP.]
Journal of Symbolic Logic. Roč. 69, č. 1 (2004), s. 201-214. ISSN 0022-4812. E-ISSN 1943-5886
Grant CEP: GA AV ČR IAA1019901; GA MŠMT LN00A056
Výzkumný záměr: CEZ:AV0Z1019905
Klíčová slova: Euler characteristic * dimension function * weak pigeonhole principle
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.331, rok: 2004
Trvalý link: http://hdl.handle.net/11104/0013998Název souboru Staženo Velikost Komentář Verze Přístup Krajicek.pdf 1 1.4 MB Vydavatelský postprint vyžádat