Jan Pich

(I moved to Oxford)

I am interested in Mathematical Logic and Complexity Theory. In particular, in Proof Complexity.


Complexity Theory in Feasible Mathematics, PhD thesis, August 2014

Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic, Logical Methods in Computer Science, 11(2), 2015; (preprint June 2014)

A PV-proof of the PCP theorem.

Circuit Lower Bounds in Bounded Arithmetics, Annals of Pure and Applied Logic, 166(1), 2015; (preprint May 2013)

Theories weaker than PV cannot prove polynomial circuit lower bounds on SAT unless p-size circuits can be approximated by weaker computational models.

Hard tautologies, MSc thesis, May 2011

Nisan-Wigderson generators in proof systems with forms of interpolation, Mathematical Logic Quarterly, 57(4), 2011; (preprint March 2010)

This shows that Razborov's conjecture about NW-generators holds for systems admitting feasible interpolation, i.e. suitable NW-generators based on hard functions are hard for such systems.

Bounded arithmetic and theory of Razborov and Rudich, Bc thesis, May 2009

[blog (2008-2010)] [poetry (2012)] [mathesis universalis (print, preprint)]