Search results
- 1.0575139 - MÚ 2024 RIV DE eng C - Conference Paper (international conference)
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]
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : algebraic circuit complexity * non-commutative circuits * homogeneous computation * lower bounds against algebraic circuits
OECD category: 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
Permanent Link: https://hdl.handle.net/11104/0344997File Download Size Commentary Version Access Hrubes1.pdf 1 716.8 KB Publisher’s postprint open-access - 2.0574198 - MÚ 2024 RIV US eng J - Journal Article
Folwarczný, Lukáš
On protocols for monotone feasible interpolation.
ACM Transactions on Computation Theory. Roč. 15, 1-2 (2023), č. článku 2. ISSN 1942-3454
Institutional support: RVO:67985840
Keywords : circuit complexity * communication complexity * proof complexity
OECD category: Pure mathematics
Impact factor: 0.7, year: 2022
Method of publishing: Limited access
https://doi.org/10.1145/3583754
Permanent Link: https://hdl.handle.net/11104/0344548File Download Size Commentary Version Access Folwarczny1.pdf 1 492.8 KB Publisher’s postprint require - 3.0539558 - MÚ 2021 RIV US eng C - Conference Paper (international conference)
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]
Institutional support: RVO:67985840
Keywords : circuit complexity * communication complexity * cutting planes
OECD category: 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
Permanent Link: http://hdl.handle.net/11104/0317277File Download Size Commentary Version Access deRezende2.pdf 0 209.6 KB Publisher’s postprint require - 4.0539556 - MÚ 2021 RIV US eng C - Conference Paper (international conference)
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]
Institutional support: RVO:67985840
Keywords : circuit complexity * circuit lower bounds * communication complexity
OECD category: 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
Permanent Link: http://hdl.handle.net/11104/0317276File Download Size Commentary Version Access deRezende1.pdf 0 223.9 KB Publisher’s postprint require - 5.0531552 - MÚ 2021 RIV CH eng J - Journal Article
Hrubeš, Pavel
On ϵ-sensitive monotone computations.
Computational Complexity. Roč. 29, č. 2 (2020), č. článku 6. ISSN 1016-3328. E-ISSN 1420-8954
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : arithmetic circuit complexity * extension complexity * nonnegative rank
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 1.353, year: 2020
Method of publishing: Limited access
https://doi.org/10.1007/s00037-020-00196-6
Permanent Link: http://hdl.handle.net/11104/0310182File Download Size Commentary Version Access Hrubes1.pdf 3 365.1 KB Publisher’s postprint require - 6.0499289 - MÚ 2020 RIV NL eng J - Journal Article
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
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : computational complexity * primitive recursive set functions * circuit complexity * Cobham recursive set functions
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Method of publishing: Limited access
http://dx.doi.org/10.3233/COM-180096
Permanent Link: http://hdl.handle.net/11104/0291518File Download Size Commentary Version Access Thapen1.pdf 1 310.7 KB Publisher’s postprint require - 7.0489470 - MÚ 2019 RIV NL eng J - Journal Article
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
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : certificate complexity * circuit complexity * computational complexity
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.914, year: 2018
https://www.sciencedirect.com/science/article/pii/S0020019018300917?via%3Dihub
Permanent Link: http://hdl.handle.net/11104/0283879File Download Size Commentary Version Access Talebanfard.pdf 3 195.9 KB Publisher’s postprint require - 8.0353280 - MÚ 2011 RIV NL eng J - Journal Article
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
R&D Projects: GA AV ČR IAA1019401; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : bounded arithmetic * circuit complexity * propositional translation
Subject RIV: BA - General Mathematics
Impact factor: 0.450, year: 2011
http://www.sciencedirect.com/science/article/pii/S0168007210001260
Permanent Link: http://hdl.handle.net/11104/0192570File Download Size Commentary Version Access Jerabek1.pdf 1 361 KB Publisher’s postprint require - 9.0352607 - MÚ 2011 RIV US eng J - Journal Article
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
R&D Projects: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : Circuit complexity * Distinguishing complexity * FewEXP * Formula size * Kolmogorov complexity
Subject RIV: BA - General Mathematics
Impact factor: 1.157, year: 2011
http://www.sciencedirect.com/science/article/pii/S0022000010000887
Permanent Link: http://hdl.handle.net/11104/0192081File Download Size Commentary Version Access Koucky.pdf 1 404.2 KB Publisher’s postprint require - 10.0352511 - MÚ 2011 RIV US eng J - Journal Article
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
R&D Projects: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : Circuit Complexity * Lower Bounds * Natural Proofs * Self-Reducibility * Time-Space Tradeoffs
Subject RIV: BA - General Mathematics
Impact factor: 3.375, year: 2010
http://dl.acm.org/citation.cfm?doid=1706591.1706594
Permanent Link: http://hdl.handle.net/11104/0192003File Download Size Commentary Version Access Koucky.pdf 1 249.6 KB Author’s postprint require