Hardness magnification near state-of-the-art lower bounds IC Oliveira, J Pich, R Santhanam
https://eccc.weizmann.ac.il/report/2018/158/, 2018
49 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
47 2022 Feasibly constructive proofs of succinct weak circuit lower bounds M Müller, J Pich
Annals of Pure and Applied Logic, 2019
40 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
33 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
29 2016 Circuit lower bounds in bounded arithmetics J Pich
Annals of Pure and Applied Logic 166 (1), 29-45, 2015
28 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
25 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
23 2020 Why are proof complexity lower bounds hard? J Pich, R Santhanam
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019
21 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
15 2021 Complexity theory in feasible mathematics J Pich
Charles University in Prague, 2014
9 2014 Nisan‐Wigderson generators in proof systems with forms of interpolation J Pich
Mathematical Logic Quarterly 57 (4), 379-383, 2011
9 2011 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
5 2021 From proof complexity to circuit complexity via interactive protocols N Arteche, E Khaniki, J Pich, R Santhanam
arXiv preprint arXiv:2405.02232, 2024
4 2024 Towards P J Pich, R Santhanam
arXiv preprint arXiv:2312.08163, 2023
4 2023 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
computational complexity 33 (2), 12, 2024
1 2024 Provability of weak circuit lower bounds M Müller, J Pich
unpublished, available from the second author’s homepage, 2017
1 2017 
Rahul SanthanamUniversity of OxfordE-mail megerősítve itt: cs.ox.ac.uk