Jan Pich

(I moved to Oxford)



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)]