Moritz Müller publications

Moritz Müller



Publications






On representations of intended structures in foundational theories.
N. Barton, M. Müller, M. Prunescu.
Submitted.

Typical forcing, NP search problems and an extension of a theorem of Riis.
M. Müller.
Submitted.

Automating Resolution is NP-hard.
A. Atserias, M. Müller.
Journal of the ACM 67 (5): Article 31, 2020.
Preliminary version: FOCS19 (best paper award)

Feasibly constructive proofs of succinct weak circuit lower bounds.
M. Müller, J. Pich.
Annals of Pure and Applied Logic 171 (2): Article 102735, 2020.

Polynomial time ultrapowers and the consistency of circuit lower bounds.
J. Bydzovsky, M. Müller.
Archive for Mathematical Logic 59 (1): 127-147, 2020.

The parameterized space complexity of model-checking bounded variable first-order logic.
Y. Chen, M. Elberfeld, M. Müller.
Logical Methods in Computer Science 15(3): 31:1-31:29, 2019.
Preliminary version: MFCS14.
Feasible set functions have small circuits.
A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen.
Computability 8 (1): 67-98, 2019.

A remark on pseudo proof systems and hard instances of the satisfiability problem.
J. Maly, M. Müller.
Mathematical Logic Quarterly 64 (6): 418-428, 2018.

A parameterized halting problem, the linear time hierarchy, and the MRDP theorem.
Y. Chen, M. Müller, K. Yokoyama.
33rd ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 235-244, 2018.

One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries.
H. Chen, M. Müller.
ACM Transactions on Computational Logic 18 (4): Article No. 29, 2017.
Preliminary version: CSL-LICS14.

The parameterized space complexity of embedding along a path.
H. Chen, M. Müller.
Theory of Computing Systems 61 (3): 851-870, 2017.

Cobham recursive set functions and weak set theories.
A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen.
Sets and Computations, Lecture Notes Series 33, IMS NUS, World Scientific, Chapter 5, pp. 55-116, 2017.

The treewidth of proofs.
M. Müller, S. Szeider
Information and Computation 255 (1): 147-164, 2017.
Preliminary versions: MFCS13, ECCC TR13-113.
Cobham recursive set functions.
A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen.
Annals of Pure and Applied Logic 167 (3): 335-369, 2016.

Proofs and Constraints.
M. Müller.
Habilitation Thesis, Universität Wien, 2016.

The fine classification of conjunctive queries and parameterized logarithmic space.
H. Chen, M. Müller.
ACM Transactions on Computation Theory 7 (2): Article No. 7, 2015.
Preliminary versions: PODS13.
Lower bounds for DNF-refutations of a relativized weak pigeonhole principle.
A. Atserias, M. Müller, S. Oliva.
The Journal of Symbolic Logic 80 (2): 450-476, 2015.
Preliminary versions: CCC13, ECCC TR13-116.
Topological dynamics of unordered Ramsey structures.
M. Müller, A. Pongrácz.
Fundamenta Mathematicae 230 (1): 77-98, 2015.

Partially definable forcing and bounded arithmetic.
A. Atserias, M. Müller.
Archive for Mathematical Logic 54 (1): 1-33, 2015.

Hard instances of algorithms and proof systems.
Y. Chen, J. Flum, M. Müller.
ACM Transactions on Computation Theory 6 (2): Article No. 7, 2014.
Preliminary versions: CiE12, ECCC TR11-085.
Parameterized logarithmic space and fine structure of FPT.
M. Müller.
FPT News: The Parameterized Complexity Newsletter Vol. 10 No. 2, September 2014.

Consistency, optimality and incompleteness.
Y. Chen, J. Flum, M. Müller.
Annals of Pure and Applied Logic 164 (12): 1224-1235, 2013.
Preliminary version: CiE11.
An algebraic preservation theorem for Aleph_0 categorical quantified constraint satisfaction.
H. Chen, M. Müller.
Logical Methods in Computer Science 9 (1:15), 2013.
Preliminary version: LICS12.
Parameterized random complexity.
J.-A. Montoya, M. Müller.
Theory of Computing Systems 52 (2): 221-270, 2013.
Preliminary versions: IWPEC08, IWPEC06, ECCC TR08-063.
Some definitorial suggestions for parameterized proof complexity.
J. Flum, M. Müller.
7th International Symposium on Parameterized and Exact Computation (IPEC), Springer LNCS 7535, pp. 73-84, 2012.

On optimal probabilistic algorithms for SAT.
Y. Chen, J. Flum, M. Müller.
The Infinity Project, A 2009 - 2011 Research Programme, CRM Publications, pp. 225-230, 2012.
Preliminary version: Logical Approaches to Barriers in Computing and Complexity, Greifswald, 2010.

Strong isomorphism reductions in complexity theory.
S. Buss, Y. Chen, J. Flum, S.-D. Friedman, M. Müller.
The Journal of Symbolic Logic 76 (4): 1381-1402, 2011.

Lower bounds for kernelizations and other preprocessing procedures.
Y. Chen, J. Flum, M. Müller.
Theory of Computing Systems 48 (4): 803-839, 2011.
Preliminary versions: CiE09, ECCC TR07-137.
A comparison of two aesthetic principles (in german).
M. Müller.
In F. Bomski, S. Suhr (eds.), Fiktum versus Faktum? Nicht-mathematische Dialoge mit der Mathematik, Erich Schmidt Verlag, 2011.

W-hierarchies defined by symmetric gates.
M. Fellows, J. Flum, D. Hermelin, M. Müller, F. Rosamond.
Theory of Computing Systems 46 (2): 311-339, 2010.
Preliminary versions: IWPEC08, ACiD07
Similarity as tractable transformation.
M. Müller, I. van Rooij, T. Wareham.
31th Annual Conference of the Cognitive Science Society (CogSci), 2009.

Parameterized Randomization.
M. Müller.
PhD Thesis, Albert-Ludwigs Universität Freiburg i.Br., 2008.

Computational complexity analysis can help, but first we need a theory.
I. van Rooij, T. Wareham, M. Müller.
Behavioral and Brain Sciences 31 (4): 399-400, 2008.

Identifying sources of intractability in cognitive models: an illustration using analogical structure mapping.
I. van Rooij, P. Evans, M. Müller. J. Gedge, T. Wareham.
30st Annual Conference of the Cognitive Science Society (CogSci), 2008.