Follow
Ján Pich
Title
Cited by
Cited by
Year
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
https://eccc.weizmann.ac.il/report/2018/158/, 2018
472018
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
382022
Feasibly constructive proofs of succinct weak circuit lower bounds
M Müller, J Pich
Annals of Pure and Applied Logic, 2019
322019
Reasons for hardness in QBF proof systems
O Beyersdorff, L Hinde, J Pich
ACM Transactions on Computation Theory (TOCT) 12 (2), 1-27, 2020
282020
Understanding Gentzen and Frege systems for QBF
O Beyersdorff, J Pich
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer …, 2016
272016
Circuit lower bounds in bounded arithmetics
J Pich
Annals of Pure and Applied Logic 166 (1), 29-45, 2015
242015
Frege systems for quantified Boolean logic
O Beyersdorff, I Bonacina, L Chew, J Pich
Journal of the ACM (JACM) 67 (2), 1-36, 2020
172020
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
172015
Why are proof complexity lower bounds hard?
J Pich, R Santhanam
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019
162019
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
92021
Nisan‐Wigderson generators in proof systems with forms of interpolation
J Pich
Mathematical Logic Quarterly 57 (4), 379-383, 2011
92011
Complexity theory in feasible mathematics
J Pich
Charles University in Prague, 2014
82014
Learning algorithms from circuit lower bounds
J Pich
arXiv preprint arXiv:2012.14095, 2020
62020
Learning algorithms versus automatability of Frege systems
J Pich, R Santhanam
arXiv preprint arXiv:2111.10626, 2021
42021
A note on natural proofs and intuitionism
K Ghasemloo, J Pich
available at karlin. mff. cuni. cz/∼ pich/natcons. pdf, 2013
22013
Hard tautologies
J Pich
Charles University in Prague, 2011
22011
Localizability of the approximation method
J Pich
arXiv preprint arXiv:2212.09285, 2022
12022
Provability of weak circuit lower bounds
M Müller, J Pich
unpublished, available from the second author’s homepage, 2017
12017
Towards PNP from Extended Frege lower bounds
J Pich, R Santhanam
arXiv preprint arXiv:2312.08163, 2023
2023
Research Statement
JÁN PICH
2022
The system can't perform the operation now. Try again later.
Articles 1–20