Erfan Khaniki

activity

20192025

most citedThe provably total recursive functions and the MRDP theorem in Basic Arithmetic and its extensions

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

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2025

The Proof Analysis Problem

Noel Arteche, Albert Atserias, Susanna F. de Rezende +1

Atserias and Müller (JACM, 2020) proved that for every unsatisfiable CNF formula $φ$ , the formula $Ref (φ)$ , stating " $φ$ has small Resolution refutations", does not…

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 $NC^{1}$ or $P / poly$ , currently out of reach, are a necessary step towards p…