Showing cs.CCShow all
3 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 , 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 or , currently out of reach, are a necessary step towards p…
cs.CC2024
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…