9 papers
Nonstandard combinatorial ultrafilters and a new local witness model
Johannes Heil, Moritz Müller
A central object in the theory of proof complexity generators is Krajicek's local witness model. We construct a new such model as a definable ultrapower using a definable version o…
Model-checking in the Foundations of Algorithmic Law and the Case of Regulation 561
Moritz Müller, Joost J. Joosten
We discuss model-checking problems as formal models of algorithmic law. Specifically, we ask for an algorithmically tractable general purpose model-checking problem that naturally…
On the Consistency of Circuit Lower Bounds for Non-Deterministic Time
Albert Atserias, Sam Buss, Moritz Müller
We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory…
Automating Resolution is NP-Hard
Albert Atserias, Moritz Müller
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is n…
The parameterized space complexity of model-checking bounded variable first-order logic
Yijia Chen, Michael Elberfeld, Moritz Müller
The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational stru…
The parameterized space complexity of embedding along a path
Hubie Chen, Moritz Müller
The embedding problem is to decide, given an ordered pair of structures, whether or not there is an injective homomorphism from the first structure to the second. We study this pro…
Topological dynamics of unordered Ramsey structures
Moritz Müller, András Pongrácz
In this paper we investigate the connections between Ramsey properties of Fraisse classes K and the universal minimal flow M(G_K) of the automorphism group G_K of their Fraisse lim…
One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries
Hubie Chen, Moritz Müller
We study the problem of conjunctive query evaluation relative to a class of queries; this problem is formulated here as the relational homomorphism problem relative to a class of s…
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
Hubie Chen, Moritz Müller
We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of boolean conjunctive q…