Search results
- 1.0523269 - MÚ 2021 RIV DE eng C - Conference Paper (international conference)
Chen, L. - Hirahara, S. - Oliveira, I.C. - Pich, Ján - Rajgopal, N. - Santhanamz, R.
Beyond natural proofs: Hardness magnification and locality.
11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2020 - (Vidick, T.), č. článku 70. Leibniz International Proceedings in Informatics (LIPIcs), 151. ISBN 978-3-95977-134-4. ISSN 1868-8969.
[11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Seattle (US), 12.01.2020-14.01.2020]
R&D Projects: GA ČR(CZ) GA19-05497S
Institutional support: RVO:67985840
Keywords : hardness magnification * natural proofs * minimum circuit size problem * circuit lower bounds
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://drops.dagstuhl.de/opus/volltexte/2020/11755/
Permanent Link: http://hdl.handle.net/11104/0307638 - 2.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 - 3.0318523 - MÚ 2009 RIV US eng C - Conference Paper (international conference)
Allender, E. - Koucký, Michal
Amplifying Lower Bounds by Means of Self-Reducibility.
[Zesilování dolních odhadů pomocí dolů samopřevoditelnosti.]
Proceedings of IEEE Conference on Computational Complexity 2008. Maryland: IEEE Computer Society Press, 2008, s. 31-40. ISBN 978-0-7695-3169-4.
[IEEE Conference on Computational Complexity 2008. College Park (US), 23.06.2008-26.06.2008]
R&D Projects: GA ČR GP201/07/P276
Institutional research plan: CEZ:AV0Z10190503
Keywords : circuit complexity * lower bounds * natural proofs
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0167916File Download Size Commentary Version Access Koucky.pdf 1 414.3 KB Publisher’s postprint require