5 papers · 1 filter
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 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…
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…