1 citations · 1 across the 4 of their papers we have counts for
5 papers
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 , stating " has small Resolution refutations", does not…
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…
Not all Kripke models of are locally
Erfan Khaniki
Let be an arbitrary Kripke model of Heyting Arithmetic, . For every node in , we can view the classical structure of , as a mo…
The provably total recursive functions and the MRDP theorem in Basic Arithmetic and its extensions
Mohammad Ardeshir, Erfan Khaniki, Mohsen Shahriari
We study Basic Arithmetic, BA introduced by W. Ruitenburg. BA is an arithmetical theory based on basic logic which is weaker than intuitionistic logic. We show that the class of th…
New relations and separations of conjectures about incompleteness in the finite domain
Erfan Khaniki
Our main results are in the following three sections: 1. We prove new relations between proof complexity conjectures that are discussed in \cite{pu18}. 2. We investigate the existe…