3 papers
math.LO2026
From Gödel incompleteness to the consistency of circuit lower bounds
Albert Atserias, Moritz Müller
We prove that the bounded arithmetic theory is consistent with EXP P/poly. More generally, we show that certain separations of from a theory imp…
cs.CC2025
Simple general magnification of circuit lower bounds
Albert Atserias, Moritz Müller
We introduce a technically and conceptually simple approach to magnification of circuit and formula lower bounds. Central to the method are so-called distinguishers, sparse matrice…
cs.CC2022
A parameterized halting problem, truth and the MRDP theorem
Yijia Chen, Moritz Müller, Keita Yokoyama
We study the parameterized complexity of the problem to decide whether a given natural number satisfies a given -formula ; the parameter is the size of . This par…