Manuel Bodirsky

Publications

This list is no longer maintained; for new publications of Manuel Bodirsky, please visit new site at TU Dresden. Also see Google Scholar, the DBLP database, and the MathSciNet database.

2014+

• The 42 reducts of the random ordered graph (with Michael Pinsker and András Pongrácz). Preprint, arXiv:1309.2165.
• Reducts of structures and maximal-closed permutation groups (with Dugald Machpherson). Preprint, arXiv:1310.6393.
• Reconstructing the topology of clones (with Michael Pinsker and András Pongrácz). Preprint, arXiv:1312.7699.
• Topological Birkhoff (with Michael Pinsker). To appear in the Transactions of the AMS.
• New Ramsey Classes from Old. Electronic Journal of Combinatorics 21(2): P2.22. arXiv:1204.3258.
• Minimal functions on the random graph (with Michael Pinsker). Accepted for publication in Israel Journal of Mathematics, arXiv:1003.4030.

2013

• Decidability of Definability (with Michael Pinsker and Todor Tsankov). Journal of Symbolic Logic, Volume 78, Issue 4, pages 1036-1054. ArXiv:1012.2381.
• Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets (with Dugald Macpherson and Johan Thapper). ACM Transactions on Computational Logic, 14(4): 30.
• Complexity of Existential Positive First-Order Logic (with Miki Hermann and Florian Richoux). Journal of Logic and Computation, 23:753-760. An extended abstract appeared in In the proceedings of Computing in Europe (CiE'09). Download.
• Datalog and Constraint Satisfaction with Infinite Templates (with Víctor Dalmau). Journal on Computer and System Sciences 79:79-100 (this will be my last publication with Elsevier, unless they change their policy). Abstract, download, and additional information. An earlier version appeared in the proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS06).

2012

• Complexity Classification in Infinite-Domain Constraint Satisfaction. Mémoire HDR à l'Université Paris 7, arXiv:1201.0856.
• On the complexity of MMSNP (with Hubie Chen and Tomas Feder). SIAM Journal on Discrete Mathematics (SIDMA), 26(1): 404-414.
• The Complexity of Surjective Homomorphism Problems -- a Survey (with Barnaby Martin and Jan Kára). Discrete Applied Mathematics, 160(12): 1680-1690.
• Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction (with Peter Jonsson and Timo von Oertzen). Journal of Logic and Computation, 22(3): 643-660.
• Essential Convexity and Complexity of Semi-algebraic Constraints (with Peter Jonsson and Timo von Oertzen). Logical Methods in Computer Science 8(4). A preliminary conference version appeared in the proceedings of ICALP'09 under the title of `Semi-linear Program Feasibility'.
• Equivalence Constraint Satisfaction Problems (with Michal Wrona). Proceedings of Computer Science Logic (CSL'12), 122-136.
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction (with Martin Hils and Barnaby Martin). Logical Methods in Computer Science (LMCS), 8(3:13). A preliminary version of this paper appeared in the proceedings of LICS'10.
• Tractable Set Constraints (with Martin Hils). Journal of Artificial Intelligence Research (JAIR), 45:731-759. An extended abstract appeared in the proceedings of IJCAI'11, Barcelona.

2011

• Schaefer's Theorem for Graphs (with Michael Pinsker). Proceedings of STOC'11, San Jose.
• Boltzmann Samplers, Polya Theory, and Cycle Pointing (with Eric Fusy, Mihyun Kang, and Stefan Vigerske). SIAM Journal on Computing, 40(3):721-769. Preprint in arXiv:1003.4546. An extended abstract of a preliminary version of this paper appeared at SODA'07.
• Decidability of Definability (with Michael Pinsker and Todor Tsankov). ArXiv:1012.2381. Proceedings of LICS'11, Toronto.
• Rooted Phylogeny Problems (with Jens Mueller). Logical Methods in Computer Science (LMCS), 7(4). A preliminary version of the paper appeared in the proceedings of ICDT'10, Lausanne.
• RCC8 is tractable on instances of bounded treewidth (with Stefan Woelfl). Proceedings of IJCAI'11, Barcelona.
• Reducts of Ramsey structures (with Michael Pinsker). Survey. Book chapter in "Model Theoretic Methods in Finite Combinatorics", AMS Contemporary Mathematics.
• Limit Behavior of Locally Consistent Constraint Satisfaction Problems (with Daniel Král'). SIAM Journal on Discrete Mathematics (SIDMA), 25(2):916-933.
• Aleph_0-categorical structures: interpretations and endomorphisms (with Markus Junker). Algebra Universalis, 64(3), 403-417.

2010

• The Complexity of Temporal Constraint Satisfaction Problems (with Jan Kára). Journal of the ACM, 57(2). An extended abstract appeared in the proceedings of STOC'08. Abstract, conference version, long version, comments.
• The reducts of equality up to primitive positive definability (with Hubie Chen and Michael Pinsker). Journal of Symbolic Logic (JSL), 75(4): 1249-1292.
• A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning (with Jan Kára). ACM Transactions on Computational Logic (ACM ToCL), 11(3).
• Quantified Equality Constraints (with Hubie Chen). SIAM Journal on Computing, 39(8). An extended abstract appeared in the proceedings of the Annual IEEE Symposium of Logic in Computer Science (LICS07). Abstract and additional information.
• Distance Constraint Satisfaction Problems (with Víctor Dalmau, Barnaby Martin, and Michael Pinsker). In the proceedings of MFCS'10, Brno, arXiv:1004.3842.
• Finite trees are Ramsey under topological embeddings (with Diana Piguet). Unpublished technical report, arXiv:1002:1557.
• Peek Arc Consistency (with Hubie Chen). Theoretical Computer Science, 411(2): 445-453.
• Rooted Phylogeny Problems (with Jens Mueller). In the proceedings of the 13th International Conference on Database Theory (ICDT'10), 165-173, Lausanne. See journal version to appear in Logical Methods in Computer Science (LMCS).
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction (with Martin Hils and Barnaby Martin). In the proceedings of LICS'10. See journal version to appear in Logical Methods in Computer Science (LMCS).

2009

• Qualitative Temporal and Spatial Reasoning Revisited (with Hubie Chen). Journal of Logic and Computation, 19(6):1359-1383.
• Maximal Infinite-valued Constraint Languages (with Hubie Chen, Jan Kára, and Timo von Oertzen). Theoretical Computer Science, 410(18): 1684-1693. Abstract, download, and additional information.
• Relatively Quantified Constraint Satisfaction (with Hubie Chen). Constraints, Volume 14, Issue 1, 3-15.
• Semilinear program feasibility (with Peter Jonsson and Timo von Oertzen). In the proceedings of ICALP'09, 79-90. Journal version, comments.
• All reducts of the random graph are model-complete (with Michael Pinsker). Unpublished technical report, arXiv:0810.2270.
• Complexity of Existential Positive First-Order Logic (with Miki Hermann and Florian Richoux). In the proceedings of Computing in Europe (CiE'09), 31-36. Long version.
• Integer Programming with 2-Variable Equations and 1-Variable Inequalities (with Gustav Nordh and Timo von Oertzen). Information Processing Letters 109(11): 572-575. Presented at the Cologne-Twente Workshop on Graphs and Combinatorial Optimization, June 2-4, 2009, Paris.

2008

• The Complexity of Temporal Constraint Satisfaction Problems. In the proceedings of STOC'08 (with Jan Kára), 29-38. Abstract, conference version, long version, comments.
• Non-dichotomies in Constraint Satisfaction Complexity. In the proceedings of ICALP'08 (with Martin Grohe), 184-196. Abstract, download.
• Constraint Satisfaction Problems with Infinite Templates. Survey, in LNCS 5250, Complexity of Constraints - An Overview of Current Research Themes, Creignou, N., Kolaitis, P.G., Vollmer, H. (Eds.), 196-228, 2008, ISBN 978-3-540-92799-0.
• The Complexity of Equality Constraint Languages, Theory of Computing Systems 43(2), 136-158 (with Jan Kára). Abstract and additional information.
• Generating Cubic Planar Graphs Uniformly at Random. Random Structures and Algorithms (RSA), 34: 157-180 (with Clemens Gröpl and Mihyun Kang). Abstract and additional information.

2007

• Determining the Consistency of Partial Tree Descriptions, Artificial Intelligence, 171: 185-196 (with Martin Kutz).
• Cores of Countably Categorical Structures, Logical Methods in Computer Science, 3(1:2). Abstract and download.
• Oligomorphic Clones. Algebra Universalis, 57(1), 109-125 (with Hubie Chen). Postprint download and additional information.
• Quantified Equality Constraints. In the proceedings of the Annual IEEE Symposium of Logic in Computer Science (LICS07) (with Hubie Chen). Journal version available.
• Maximal Infinite-valued Constraint Languages (with Hubie Chen, Jan Kára, and Timo von Oertzen). In the proceedings of the International Colloquium on Colloquium on Automata, Languages and Programming (ICALP07). Abstract, journal version, and additional information.
• Qualitative Temporal and Spatial Reasoning Revisited. In the proceedings of the 16th EACSL Annual Conference on Computer Science and Logic (CSL07) (with Hubie Chen). Abstract and additional information.
• Enumeration and limit laws of series-parallel graphs, European Journal on Combinatorics, 28, 2091-2105 (with Omer Gimenez, Mihyun Kang, and Marc Noy).
• Enumeration of Unlabeled Outerplanar Graphs. Electronic Journal of Combinatorics, 14, R66 (with Eric Fusy, Mihyun Kang, and Stefan Vigerske). Abstract and additional information.
• Generating Labeled Planar Graphs Uniformly at Random, Theoretical Computer Science, 3, 377-386 (with Clemens Gröpl and Mihyun Kang). Abstract and additional information.
• A direct decomposition of 3-connected planar graphs, Séminaire Lotharingien de Combinatoire, 54A: Article B54Ak, 15 pp. (with Clemens Gröpl, Daniel Johannsen, and Mihyun Kang). Abstract and additional information.
• Random cubic planar graphs, Random Structures and Algorithms, 30: 78-94 (with Mihyun Kang, Mike Löffler, and Colin McDiarmid). Abstract and additional information.
• An unbiased pointing operator for unlabeled structures, with applications to counting and sampling. In the proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA07), 356-365 (with Eric Fusy, Mihyun Kang, and Stefan Vigerske). Abstract and additional information.

2006

• Datalog and Constraint Satisfaction with Infinite Templates. In the proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS06), Marseille, LNCS 3884, 646-659. Springer Verlag (with Víctor Dalmau). Abstract, download, and additional information.
• The Complexity of Equality Constraint Languages. In the proceedings of the International Computer Science Symposium in Russia (CSR06), LNCS 3967, 114-126. Springer Verlag (with Jan Kára). A link to the journal version.
• Constraint Satisfaction with Countable Homogeneous Templates, Journal of Logic and Computation (JLC), 16(3): 359-373 (with Jaroslav Nešetřil). Abstract and additional information.
• Collapsibility in Infinite-Domain Quantified Constraint Satisfaction. In: Computer Science Logic (CSL06), LNCS 4207, 197-211, Szeged, Hungary (with Hubie Chen). Abstract and additional information.
• Generating outerplanar graphs uniformly at random, Combinatorics, Probability and Computing, 15: 333-343 (with Mihyun Kang). Abstract and additional information.

2005

• The Core of a Countably Categorical Structure. In the proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS05), volume LNCS 3404, 110-120, Stuttgart. Springer. Here is a link to the journal version.
• Locally Consistent Constraint Satisfaction Problems with Binary Constraints. In the proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG05), LNCS 3787, 295 - 306. Springer Verlag (with Daniel Král').
• Well-nested Drawings as Models of Syntactic Structure. In the proceedings of the 10th conference on Formal Grammer and the 9th Meeting on Mathematics of Language (FG-MOL05), Edinburgh (with Marco Kuhlmann and Matthias Möhl).
• Sampling unlabeled biconnected planar graphs. In the proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC05), LNCS 3827, 593-603. Springer Verlag (with Clemens Gröpl and Mihyun Kang). Abstract and additional information.
• On the number of series-parallel and outerplanar graphs. In the proceedings of European Conference on Combinatorics, Graph Theory, and Applications (EuroComb05), DMTCS Proceedings Series, 383 - 388 (with Omer Gimenez, Mihyun Kang, and Marc Noy).
• A direct decomposition of 3-connected planar graphs. In the proceedings of the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC05). Here is a link to the journal version.

2004

• Constraint Satisfaction with Infinite Domains. PhD thesis, Humboldt-Universität zu Berlin. Abstract and additional information.
• A new algorithm for normal dominance constraints. In the proceedings of the Symposium on Discrete Algorithms (SODA04), 59-67 (with Denys Duchier, Sebastian Miehle, and Joachim Niehren). Abstract and additonal information.
• Efficiently Computing the Limit Density of Regular Languages (with Tobias Gärtner, Timo von Oertzen, and Jan Schwinghammer). In the proceedings of Latin American Informatics (LATIN'04), LNCS 2976, 262-270, Buenos Aires.

2003

• Constraint Satisfaction with Countable Homogeneous Templates. In the proceedings of Computer Science Logic (CSL03), LNCS 2803, 44-57, Vienna. Springer Verlag (with Jaroslav Nešetřil).
• Generating Labeled Planar Graphs Uniformly at Random. In the proceedings of the Thirtieth International Colloquium on Automata, Languages and Programming (ICALP'03), LNCS 2719, 1095-1107, Springer Verlag (with Clemens Gröpl and Mihyun Kang). Here is a link to the journal version.
• Generating outerplanar graphs uniformly at random. Presented at the 1st workshop on Algorithms for Listing, Counting, and Enumeration (ALICE03) (with Mihyun Kang). Here is a link to the journal version.

2002

• Pure Dominance Constraints. In the proceedings of the 19th Symposium on Theoretical Aspects of Computer Science (STACS02), LNCS 2285, 287-298, Antibes - Juan le Pins. Springer Verlag (with Martin Kutz). Here is a link to the journal version.

Copyright Notice

All content on this website (including the referenced articles distributed by this server) has been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. For some documents the publisher might have reserved some rights. Otherwise the copyright follows a Creative Commons License.