Ján Pich

Department of Computer Science
University of Oxford
jan.pich@cs.ox.ac.uk

I am a Marie Curie research fellow at the Algorithms and Complexity Theory Group.

Research interests: Mathematical Logic and Complexity Theory. In particular, Proof Complexity.

Publications:

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly, with Rahul Santhanam
to appear in Symposium on Theoretical Computer Science (STOC) 2021.

Frege systems for quantified Boolean logic, with Olaf Beyersdorff, Ilario Bonacina and Leroy Chew
Journal of the ACM (JACM) 2020.

Beyond natural proofs: hardness magnification and locality, with L.Chen, S.Hirahara, I.C.Oliveira, N.Rajgopal and R.Santhanam
Innovations in Theoretical Computer Science (ITCS) 2020.

Reasons for hardness in QBF proof systems, with Olaf Beyersdorff and Luke Hinde
ACM Transactions on Computation Theory (TOCT) 2020.

Why are proof complexity lower bounds hard? with Rahul Santhanam
Symposium on Foundations of Computer Science (FOCS) 2019.

Hardness magnification near state-of-the-art lower bounds, with Igor C.Oliveira and Rahul Santhanam
Computational Complexity Conference (CCC) 2019,
Invited to Special Issue of Theory of Computing (to appear).

Feasibly constructive proofs of succinct weak circuit lower bounds, with Moritz Müller
Annals of Pure and Applied Logic (APAL) 2019.

Understanding Gentzen and Frege systems for QBF, with Olaf Beyersdorff
Symposium on Logic in Computer Science (LICS) 2016.

Circuit lower bounds in bounded arithmetics
Annals of Pure and Applied Logic (APAL) 2015.

Hard tautologies
MSc thesis, Charles University, 2011.