Ján Pich

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

Royal Society University Research Fellow

Area: Mathematical Logic & Complexity Theory

CV       Research Statement       Open Positions


Papers:

From proof complexity to circuit complexity via interactive protocols, with N.Arteche, E.Khaniki & R.Santhanam, ICALP 2024.

Towards P≠NP from Extended Frege lower bounds, with Rahul Santhanam, Dec 2023.

Localizability of the approximation method, cc'24, preprint: Dec 2022.

Learning algorithms versus automatability of Frege systems, with Rahul Santhanam, Oct 2021.

Learning algorithms from circuit lower bounds, Nov 2020.

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly, with Rahul Santhanam, STOC 2021.

Beyond natural proofs: hardness magnification and locality, with L.Chen, S.Hirahara, I.C.Oliveira, N.Rajgopal & R.Santhanam, JACM'22, Nov 2019.

Why are proof complexity lower bounds hard? with Rahul Santhanam, FOCS 2019.

Hardness magnification near state-of-the-art lower bounds, with Igor C.Oliveira & Rahul Santhanam, CCC'19, preprint: Sep 2018. [slides]

Feasibly constructive proofs of succinct weak circuit lower bounds, with Moritz Müller, APAL'19, different version: Sep 2017. [slides]

Understanding Gentzen and Frege systems for QBF, with Olaf Beyersdorff, LICS 2016.

+ publications from 2009-2014           + all publications

Poetry: Mathesis universalis, Literis, 2016, preprint: Dec 2015.