3 papers
cs.CC2026
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…
cs.CC2025
Quantum Automating -Frege Is LWE-Hard
Noel Arteche, Gaia Carenini, Matthew Gray
We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic as…
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…