Moritz Müller publications

Moritz Müller

moritz.mueller@univie.ac.at


Publications





Full papers

20. Feasibly constructive proofs of succinct weak circuit lower bounds.
      J. Pich, M. Müller.
      submitted.here
19. Pseudo proof systems and hard instances of SAT.
      J. Maly, M. Müller.
      submitted. pdf
18. The parameterized space complexity of model-checking bounded variable first-order logic.
      Y. Chen, M. Elberfeld, M. Müller.
      submitted. pdf
17. Subset-bounded recursion and a circuit model for Cobham recursive set functions.
      A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen.
      submitted. pdf
16. 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.here
15. The parameterized space complexity of embedding along a path.
      H. Chen, M. Müller.
      Theory of Computing Systems 61 (3): 851-870, 2017. here
14. 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, Institute for Mathematical Sciences, National University of Singapore, World Scientific, Chapter 5, pp. 55-116, 2017. pdf
13. The treewidth of proofs.
      M. Müller, S. Szeider
      Information and Computation 255 (1): 147-164, 2017.pdf
12. 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. pdf
11. 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. pdf
10. 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.pdf
9. Topological dynamics of unordered Ramsey structures.
      M. Müller, A. Pongrácz.
      Fundamenta Mathematicae 230 (1): 77-98, 2015.pdf
8. Partially definable forcing and bounded arithmetic.
      A. Atserias, M. Müller.
      Archive for Mathematical Logic 54 (1): 1-33, 2015.pdf
7. 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.pdf
6. Consistency, optimality and incompleteness.
      Y. Chen, J. Flum, M. Müller.
      Annals of Pure and Applied Logic 164 (12): 1224-1235, 2013.pdf
5. 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. here
4. Parameterized random complexity.
      J.-A. Montoya, M. Müller.
      Theory of Computing Systems 52 (2): 221-270, 2013. pdf
3. 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.pdf
2. Lower bounds for kernelizations and other preprocessing procedures.
      Y. Chen, J. Flum, M. Müller.
      Theory of Computing Systems 48 (4): 803-839, 2011. pdf
1. 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. pdf


Extended abstracts

Bounded variable logic, parameterized logarithmic space and Savitch's theorem.
Y. Chen, M. Müller.
39th Mathematical Foundations of Computer Science (MFCS), Springer LNCS 8634, pp. 183-195, 2014. pdf
Full paper 18
One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries.
H. Chen, M. Müller.
Joint 23rd EACSL Computer Science Logic and 29th ACM/IEEE Symposium Logic in Computer Science (CSL-LICS), pp. 32:1-32:10, 2014.
Full paper 16 pdf
Revisiting space in proof complexity: treewidth and pathwidth.
M. Müller, S. Szeider.
38th Mathematical Foundations of Computer Science (MFCS), Springer LNCS 8087, pp. 704-716, 2013.
Electronic Colloquium on Computational Complexity, TR13-113, 2013.
Full paper 13 here
The fine classification of conjunctive queries and parameterized logarithmic space complexity.
H. Chen, M. Müller.
32th ACM Symposium on Principles of Database Systems (PODS), pp. 309-320, 2013.
Full paper 11here
Lower bounds for DNF-refutations of a relativized weak pigeonhole principle.
A. Atserias, M. Müller, S. Oliva.
28th IEEE Conference on Computational Complexity (CCC), IEEE Computer Society, pp. 109-120, 2013.
Electronic Colloquium on Computational Complexity, TR13-116, 2013.
Full paper 10here
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.
Electronic Colloquium on Computational Complexity, TR12-018, 2012. here
An algebraic preservation theorem for Aleph_0 categorical quantified constraint satisfaction.
H. Chen, M. Müller.
27th ACM/IEEE Symposium Logic in Computer Science (LICS), pp. 215-224, 2012.
Full paper 5here
Hard instances of algorithms and proof systems.
Y. Chen, J. Flum, M. Müller.
8th Computability in Europe (CiE), Springer LNCS 7318, pp. 119-129, 2012.
Electronic Colloquium on Computational Complexity, TR11-085, 2011.
Full paper 7here
Consistency and optimality.
Y. Chen, J. Flum, M. Müller.
7th Computability in Europe (CiE), Springer LNCS 6735, pp. 61-70, 2011.
Full paper 6pdf
On optimal probabilistic algorithms for SAT.
Y. Chen, J. Flum, M. Müller.
Logical Approaches to Barriers in Computing and Complexity, Greifswald, 2010.pdf
Lower bounds for kernelizations and other preprocessing procedures.
Y. Chen, J. Flum, M. Müller.
5th Computability in Europe (CiE), Springer LNCS 5635: 118-128, 2009.
Full paper 2here
Similarity as tractable transformation.
M. Müller, I. van Rooij, T. Wareham.
31th Annual Conference of the Cognitive Science Society (CogSci), 2009. pdf
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. here
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. pdf
A purely democratic characterization of W[1].
M. Fellows, D. Hermelin, M. Müller, F. Rosamond.
3rd International Workshop on Parameterized and Exact Computation (IWPEC), Springer LNCS 5018, pp. 103-114, 2008.
Full paper 1 pdf
Parameterized derandomization.
M. Müller
3rd International Workshop on Parameterized and Exact Computation (IWPEC), Springer LNCS 5018, pp. 148-159, 2008.
Full paper 4here
Randomized approximations of parameterized counting problems.
M. Müller.
2nd International Workshop on Parameterized and Exact Computation (IWPEC), Springer LNCS 4169, pp. 50-59, 2006.
Full paper 4 here


Others (not peer-reviewed)

Parameterized logarithmic space and fine structure of FPT.
M. Müller.
FPT News: The Parameterized Complexity Newsletter Vol. 10 No. 2, September 2014.here
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. pdf
Valiant-Vazirani lemmata for various logics.
M. Müller.
Electronic Colloquium on Computational Complexity, TR08-063, 2008.
Full paper 4 here
Parameterized complexity via combinatorial circuits.
M. Fellows, J. Flum, D. Hermelin, M. Müller, F. Rosamond.
3rd Algorithms and Complexity in Durham (ACiD), Texts in Algorithmics 9, College Publications, London, 2007.
Full paper 1 pdf
New results.
M. Müller, I. Razgon, F. Rosamond and S. Saurabh.
FPT News: The Parameterized Complexity Newsletter Vol. 3, May 2008. here


Theses

Proofs and Constraints
Habilitation Thesis, 2016. pdf
Parameterized Randomization
PhD Thesis, 2009. URN: urn:nbn:de:bsz:25-opus-64017 here
Construction Problems in Model-Checking (in german)
Diploma Thesis, 2004.