Hardness magnification near state-of-the-art lower bounds IC Oliveira, J Pich, R Santhanam https://eccc.weizmann.ac.il/report/2018/158/, 2018 | 47 | 2018 |
Beyond natural proofs: Hardness magnification and locality L Chen, S Hirahara, IC Oliveira, J Pich, N Rajgopal, R Santhanam ACM Journal of the ACM (JACM) 69 (4), 1-49, 2022 | 38 | 2022 |
Feasibly constructive proofs of succinct weak circuit lower bounds M Müller, J Pich Annals of Pure and Applied Logic, 2019 | 33 | 2019 |
Reasons for hardness in QBF proof systems O Beyersdorff, L Hinde, J Pich ACM Transactions on Computation Theory (TOCT) 12 (2), 1-27, 2020 | 28 | 2020 |
Understanding Gentzen and Frege systems for QBF O Beyersdorff, J Pich Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer …, 2016 | 27 | 2016 |
Circuit lower bounds in bounded arithmetics J Pich Annals of Pure and Applied Logic 166 (1), 29-45, 2015 | 25 | 2015 |
Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic J Pich Logical Methods in Computer Science 11 (2), 2015 | 18 | 2015 |
Frege systems for quantified Boolean logic O Beyersdorff, I Bonacina, L Chew, J Pich Journal of the ACM (JACM) 67 (2), 1-36, 2020 | 17 | 2020 |
Why are proof complexity lower bounds hard? J Pich, R Santhanam 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019 | 16 | 2019 |
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly J Pich, R Santhanam Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021 | 10 | 2021 |
NisanWigderson generators in proof systems with forms of interpolation J Pich Mathematical Logic Quarterly 57 (4), 379-383, 2011 | 9 | 2011 |
Complexity theory in feasible mathematics J Pich Charles University in Prague, 2014 | 8 | 2014 |
Learning algorithms from circuit lower bounds J Pich arXiv preprint arXiv:2012.14095, 2020 | 6 | 2020 |
Learning algorithms versus automatability of Frege systems J Pich, R Santhanam arXiv preprint arXiv:2111.10626, 2021 | 4 | 2021 |
A note on natural proofs and intuitionism K Ghasemloo, J Pich available at karlin. mff. cuni. cz/∼ pich/natcons. pdf, 2013 | 3 | 2013 |
Hard tautologies J Pich Charles University in Prague, 2011 | 2 | 2011 |
Localizability of the approximation method J Pich arXiv preprint arXiv:2212.09285, 2022 | 1 | 2022 |
Provability of weak circuit lower bounds M Müller, J Pich unpublished, available from the second author’s homepage, 2017 | 1 | 2017 |
Towards PNP from Extended Frege lower bounds J Pich, R Santhanam arXiv preprint arXiv:2312.08163, 2023 | | 2023 |
Research Statement JÁN PICH | | 2022 |