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.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.