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 2011Nisan-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
|