activity
20142024
most citedLogical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

42 citations · 46 across the 4 of their papers we have counts for

collaborators
Showing math.LOShow all

2 papers · 1 filter

math.LO2023

Towards PNP from Extended Frege lower bounds

Jan Pich, Rahul Santhanam

We prove that if conditions I-II (below) hold and there is a sequence of Boolean functions hard to approximate by p-size circuits such that p-size circuit lower bounds for $f…

math.LO2014★ 42 cited

Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

Ján Pich

We present several known formalizations of theorems from computational complexity in bounded arithmetic and formalize the PCP theorem in the theory PV1 (no formalization of this th…