4 citations · 4 across the 1 of their papers we have counts for
3 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…
cs.CC2020
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…
cs.CC2019★ 4 cited
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…