Ján Pich

Candidate Bio:

I completed my PhD in the area of Proof Complexity under supervision of Jan Krajíček. Afterwards, I held a postdoctoral position at the University of Toronto hosted by Stephen Cook, Toniann Pitassi and Alasdair Urquhart, a postdoctoral position at the University of Leeds hosted by Olaf Beyersdorff, and then relocated to the University of Vienna where I worked with Moritz Muller on an FWF project “Complexity Theory in Feasible Mathematics”. Later I continued my research at the University of Oxford hosted by Rahul Santhanam. Since September 2019 I am back in Prague at the Czech Academy of Sciences.

Research Summary:

I am interested in Mathematical Logic and Complexity Theory. In particular, in my research I focus on proof complexity of circuit lower bounds, a research direction initiated by Razborov with a proof-theoretic formulation of the natural proofs barrier. I proved, for example, that first-order theories strictly below Cook's theory PV, which formalizes polynomial-time reasoning, cannot separate P and NP unless standard hardness assumptions break. Complementing this lower bound I showed that PV is strong enough to prove the PCP theorem. More recently, these investigations led me to a co-development of a theory of hardness magnification, an approach to strong complexity lower bounds avoiding some of the earlier formal barriers in Complexity Theory. In particular, hardness magnification establishes that a slight improvement over many known circuit lower bounds for natural problems would imply breakthrough separations such as P\ne NP or the non-existence of efficient learning algorithms.

Teaching Aims:

"I have a broad background in Mathematics and Theoretical Computer Science and I would be happy to teach standard courses in these subjects, e.g. Calculus, Algebra, Logic, Algorithms. Regarding more advanced courses, I would enjoy teaching various topics in Complexity Theory and Mathematical Logic, e.g. Cryptography, Learning Theory, Circuit Complexity, Model Theory. I would be also happy to organize seminars focusing on the latest advances on the most fundamental open problems in these areas.
My general teaching philosophy is to attract students to think about important problems by making advanced and emerging research areas accessible, in particular, by a proper motivation of abstract concepts and by highlighting key ideas. I want to keep lectures well-organized, with clear goals and rigorous proofs but also believe that students should feel comfortable to ask questions and discuss their ideas."

Keywords: proof complexity, circuit complexity, hardness magnification, bounded arithmetic

All Job Candidates