Výsledky vyhledávání
- 1.0575139 - MÚ 2024 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Chatterjee, Prerona - Hrubeš, Pavel
New lower bounds against homogeneous non-commutative circuits.
38th Computational Complexity Conference (CCC 2023). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2023 - (Ta-Shma, A.), č. článku 13. Leibniz International Proceedings in Informatics, 264. ISBN 978-3-95977-282-2. ISSN 1868-8969.
[38th Computational Complexity Conference (CCC 2023). Warwick (GB), 17.07.2023-20.07.2023]
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: algebraic circuit complexity * non-commutative circuits * homogeneous computation * lower bounds against algebraic circuits
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.2023.13
Trvalý link: https://hdl.handle.net/11104/0344997Název souboru Staženo Velikost Komentář Verze Přístup Hrubes1.pdf 1 716.8 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.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 - 4.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 - 5.0531552 - MÚ 2021 RIV CH eng J - Článek v odborném periodiku
Hrubeš, Pavel
On ϵ-sensitive monotone computations.
Computational Complexity. Roč. 29, č. 2 (2020), č. článku 6. ISSN 1016-3328. E-ISSN 1420-8954
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: arithmetic circuit complexity * extension complexity * nonnegative rank
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 1.353, rok: 2020
Způsob publikování: Omezený přístup
https://doi.org/10.1007/s00037-020-00196-6
Trvalý link: http://hdl.handle.net/11104/0310182Název souboru Staženo Velikost Komentář Verze Přístup Hrubes1.pdf 3 365.1 KB Vydavatelský postprint vyžádat - 6.0499289 - MÚ 2020 RIV NL eng J - Článek v odborném periodiku
Beckmann, A. - Buss, S. - Friedman, S.-D. - Müller, M. - Thapen, Neil
Feasible set functions have small circuits.
Computability. Roč. 8, č. 1 (2019), s. 67-98. ISSN 2211-3568
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: computational complexity * primitive recursive set functions * circuit complexity * Cobham recursive set functions
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
http://dx.doi.org/10.3233/COM-180096
Trvalý link: http://hdl.handle.net/11104/0291518Název souboru Staženo Velikost Komentář Verze Přístup Thapen1.pdf 1 310.7 KB Vydavatelský postprint vyžádat - 7.0489470 - MÚ 2019 RIV NL eng J - Článek v odborném periodiku
Smal, A.V. - Talebanfard, Navid
Prediction from partial information and hindsight, an alternative proof.
Information Processing Letters. Roč. 136, August (2018), s. 102-104. ISSN 0020-0190. E-ISSN 1872-6119
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: certificate complexity * circuit complexity * computational complexity
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.914, rok: 2018
https://www.sciencedirect.com/science/article/pii/S0020019018300917?via%3Dihub
Trvalý link: http://hdl.handle.net/11104/0283879Název souboru Staženo Velikost Komentář Verze Přístup Talebanfard.pdf 3 195.9 KB Vydavatelský postprint vyžádat - 8.0353280 - MÚ 2011 RIV NL eng J - Článek v odborném periodiku
Jeřábek, Emil
On theories of bounded arithmetic for NC1.
Annals of Pure and Applied Logic. Roč. 162, č. 4 (2011), s. 322-340. ISSN 0168-0072. E-ISSN 1873-2461
Grant CEP: GA AV ČR IAA1019401; GA MŠMT(CZ) 1M0545
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: bounded arithmetic * circuit complexity * propositional translation
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.450, rok: 2011
http://www.sciencedirect.com/science/article/pii/S0168007210001260
Trvalý link: http://hdl.handle.net/11104/0192570Název souboru Staženo Velikost Komentář Verze Přístup Jerabek1.pdf 1 361 KB Vydavatelský postprint vyžádat - 9.0352607 - MÚ 2011 RIV US eng J - Článek v odborném periodiku
Allender, E. - Koucký, Michal - Ronneburger, D. - Roy, S.
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.
Journal of Computer and System Sciences. Roč. 77, č. 1 (2011), s. 14-40. ISSN 0022-0000. E-ISSN 1090-2724
Grant CEP: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Circuit complexity * Distinguishing complexity * FewEXP * Formula size * Kolmogorov complexity
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.157, rok: 2011
http://www.sciencedirect.com/science/article/pii/S0022000010000887
Trvalý link: http://hdl.handle.net/11104/0192081Název souboru Staženo Velikost Komentář Verze Přístup Koucky.pdf 1 404.2 KB Vydavatelský postprint vyžádat - 10.0352511 - MÚ 2011 RIV US eng J - Článek v odborném periodiku
Allender, E. - Koucký, Michal
Amplifying lower bounds by means of self-reducibility.
Journal of the ACM. Roč. 57, č. 3 (2010), s. 1-36. ISSN 0004-5411. E-ISSN 1557-735X
Grant CEP: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Circuit Complexity * Lower Bounds * Natural Proofs * Self-Reducibility * Time-Space Tradeoffs
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 3.375, rok: 2010
http://dl.acm.org/citation.cfm?doid=1706591.1706594
Trvalý link: http://hdl.handle.net/11104/0192003Název souboru Staženo Velikost Komentář Verze Přístup Koucky.pdf 1 249.6 KB Autorský postprint vyžádat