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 2023 · math.LOShow all

1 paper · 2 filters

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…