Publications

M. Müller, J. Joosten. Model-checking in the foundations of algorithmic law and the case of Regulation 561. Submitted.	pdf
A. Atserias, S. Buss, M. Müller. On the consistency of circuit lower bounds for non-deterministic time. Journal of Mathematical Logic, to appear.	pdf	Preliminary version: STOC 2023
Y. Chen, M. Müller, K. Yokoyama. A parameterized halting problem, Δ₀ truth and the MRDP theorem. Submitted.	pdf	Preliminary version: LICS 2018
M. Müller. Review of Jan Krajícek, Proof Complexity. Encyclopedia of Mathematics and its Applications 170, 2019. Bulletin of Symbolic Logic 29 (2): 296-297, 2023.	pdf doi
Y. Chen, J. Flum, M. Müller. A surprising relationship between descriptive complexity and proof complexity. Bulletin of the EATCS 138: 145-152, 2022.	pdf here
N. Barton, M. Müller, M. Prunescu. On representations of intended structures in foundational theories. Journal of Philosophical Logic 51: 283-296, 2022.	pdf doi
M. Müller. Typical forcing, NP search problems and an extension of a theorem of Riis. Annals of Pure and Applied Logic 172 (4): 102930, 2021.	pdf doi
A. Atserias, M. Müller. Automating Resolution is NP-hard. Journal of the ACM 67 (5): Article 31, 2020.	pdf doi	Preliminary version: FOCS19 (best paper award)
M. Müller, J. Pich. Feasibly constructive proofs of succinct weak circuit lower bounds. Annals of Pure and Applied Logic 171 (2): Article 102735, 2020.	pdf doi
J. Bydzovsky, M. Müller. Polynomial time ultrapowers and the consistency of circuit lower bounds. Archive for Mathematical Logic 59 (1): 127-147, 2020.	pdf doi
Y. Chen, M. Elberfeld, M. Müller. The parameterized space complexity of model-checking bounded variable first-order logic. Logical Methods in Computer Science 15(3): 31:1-31:29, 2019.	pdf doi	Preliminary version: MFCS 2014
A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen. Feasible set functions have small circuits. Computability 8 (1): 67-98, 2019.	pdf doi
J. Maly, M. Müller. A remark on pseudo proof systems and hard instances of the satisfiability problem. Mathematical Logic Quarterly 64 (6): 418-428, 2018.	pdf doi
H. Chen, M. Müller. One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries. ACM Transactions on Computational Logic 18 (4): Article No. 29, 2017.	pdf doi	Preliminary version: CSL-LICS 2014
H. Chen, M. Müller. The parameterized space complexity of embedding along a path. Theory of Computing Systems 61 (3): 851-870, 2017.	pdf doi
A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen. Cobham recursive set functions and weak set theories. Sets and Computations, Lecture Notes Series 33, IMS NUS, World Scientific, Chapter 5, pp. 55-116, 2017.	pdf doi
M. Müller, S. Szeider The treewidth of proofs. Information and Computation 255 (1): 147-164, 2017.	pdf doi	Preliminary version: MFCS 2013
A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen. Cobham recursive set functions. Annals of Pure and Applied Logic 167 (3): 335-369, 2016.	pdf doi
M. Müller. Proofs and Constraints. Habilitationsschrift, Universität Wien, 2016.	pdf
H. Chen, M. Müller. The fine classification of conjunctive queries and parameterized logarithmic space. ACM Transactions on Computation Theory 7 (2): Article No. 7, 2015.	pdf doi	Preliminary version: PODS 2013
A. Atserias, M. Müller, S. Oliva. Lower bounds for DNF-refutations of a relativized weak pigeonhole principle. The Journal of Symbolic Logic 80 (2): 450-476, 2015.	pdf doi	Preliminary version: CCC 2013
M. Müller, A. Pongrácz. Topological dynamics of unordered Ramsey structures. Fundamenta Mathematicae 230 (1): 77-98, 2015.	pdf doi
A. Atserias, M. Müller. Partially definable forcing and bounded arithmetic. Archive for Mathematical Logic 54 (1): 1-33, 2015.	pdf doi
Y. Chen, J. Flum, M. Müller. Hard instances of algorithms and proof systems. ACM Transactions on Computation Theory 6 (2): Article No. 7, 2014.	pdf doi	Preliminary version: CiE 2012
M. Müller. Parameterized logarithmic space and fine structure of FPT. FPT News: The Parameterized Complexity Newsletter Vol. 10 No. 2, September 2014.	pdf
Y. Chen, J. Flum, M. Müller. Consistency, optimality and incompleteness. Annals of Pure and Applied Logic 164 (12): 1224-1235, 2013.	pdf doi	Preliminary version: CiE 2011
H. Chen, M. Müller. An algebraic preservation theorem for Aleph_0 categorical quantified constraint satisfaction. Logical Methods in Computer Science 9 (1:15), 2013.	pdf doi	Preliminary version: LICS 2012
J.-A. Montoya, M. Müller. Parameterized random complexity. Theory of Computing Systems 52 (2): 221-270, 2013.	pdf doi	Preliminary version: IWPEC 2006, 2008 ECCC 2008
J. Flum, M. Müller. Some definitorial suggestions for parameterized proof complexity. 7th Int. Symp. on Parameterized and Exact Computation (IPEC), Springer LNCS 7535, pp. 73-84, 2012.	pdf doi
Y. Chen, J. Flum, M. Müller. On optimal probabilistic algorithms for SAT. The Infinity Project, A 2009 - 2011 Research Programme, CRM Publications, pp. 225-230, 2012.	pdf
S. Buss, Y. Chen, J. Flum, S.-D. Friedman, M. Müller. Strong isomorphism reductions in complexity theory. The Journal of Symbolic Logic 76 (4): 1381-1402, 2011.	pdf doi
Y. Chen, J. Flum, M. Müller. Lower bounds for kernelizations and other preprocessing procedures. Theory of Computing Systems 48 (4): 803-839, 2011.	pdf doi	Preliminary version: CiE 2009
M. Müller. A comparison of two aesthetic principles (in german). In F. Bomski, S. Suhr (eds.), Fiktum versus Faktum? Erich Schmidt Verlag, 2011.	pdf here
M. Fellows, J. Flum, D. Hermelin, M. Müller, F. Rosamond. W-hierarchies defined by symmetric gates. Theory of Computing Systems 46 (2): 311-339, 2010.	pdf doi	Preliminary version: IWPEC 2008 ACiD 2007
M. Müller, I. van Rooij, T. Wareham. Similarity as tractable transformation. 31th Annual Conference of the Cognitive Science Society (CogSci), 2009.	pdf here
M. Müller. Parameterized Randomization. Doctoral Dissertation, Albert-Ludwigs Universität Freiburg i.Br., 2008.	pdf
I. van Rooij, T. Wareham, M. Müller. Computational complexity analysis can help, but first we need a theory. Behavioral and Brain Sciences 31 (4): 399-400, 2008.	pdf doi
I. van Rooij, P. Evans, M. Müller. J. Gedge, T. Wareham. Identifying sources of intractability in cognitive models: an illustration using analogical structure mapping. 30st Annual Conference of the Cognitive Science Society (CogSci), 2008.	pdf here

Mathematical Logic