42 citations · 46 across the 4 of their papers we have counts for
7 papers
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…
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…
Localizability of the approximation method
Jan Pich
We use the approximation method of Razborov to analyze the locality barrier which arose from the investigation of the hardness magnification approach to complexity lower bounds. Ad…
Learning algorithms versus automatability of Frege systems
Ján Pich, Rahul Santhanam
We connect learning algorithms and algorithms automating proof search in propositional proof systems: for every sufficiently strong, well-behaved propositional proof system , we…
Learning algorithms from circuit lower bounds
Ján Pich
We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or…
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira +3
Hardness magnification reduces major complexity separations (such as ) to proving lower bounds for some natural problem against…
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…