2 papers
cs.CC2024
From Proof Complexity to Circuit Complexity via Interactive Protocols
Noel Arteche, Erfan Khaniki, Ján Pich +1
Folklore in complexity theory suspects that circuit lower bounds against or , currently out of reach, are a necessary step towards p…
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…