Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Publications

2017 and forthcoming

Conference Papers

[P61]László Kozma and Tobias Mömke
Maximum Scatter TSP in Doubling Metrics.
SODA, 2017.
[P60]Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou
To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack.
SODA, 2017.

Journal Articles

[J31]Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Víctor Verdugo, and Andreas Wiese
Semidefinite and linear programming integrality gaps for scheduling identical machines.
Mathematical Programming, 2017.
[J30]Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke
Complexity and Approximability of Parameterized MAX-CSPs.
Algorithmica, 2017.
[J29]Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, Tobias Mömke
Online Algorithms with Advice: the Tape Model.
Information and Computation, 254(1):59-83, 2017.

2016

Conference Papers

[P59]Markus Bläser, Vladimir Lysikov
On Degeneration of Tensors and Algebras.
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) in LIPIcs 58:19:1-19:11. Dagstuhl Publishing, 2016.
PDF
[P58]Adam Kurpisz, Monaldo Mastrolilli , Claire Mathieu, Tobias Mömke, Victor Verdugo, and Andreas Wiese
Semidefinite and linear programming integrality gaps for scheduling identical machines.
IPCO, 2016.
[P57]Anna Adamaszek, Antonios Antoniadis and Tobias Mömke
Airports and Railways: Facility Location Meets Network Design.
STACS in LIPIcs 47:6:1-6:14. Dagstuhl Publishing, 2016.
[P56]Stefan Dobrev, Juraj Hromkovic, Dennis Komm, Richard Kralovic, Rastislav Kralovic and Tobias Mömke
The Complexity of Paging under a Probabilistic Adversary.
SOFSEM in LNCS 9587:265-276. Springer, 2016.

Journal Articles

[J28]Tobias Mömke and Ola Svensson
Removing and Adding Edges for the Traveling Salesman Problem.
Journal of the ACM (JACM), 63(1), 2016.

2015

Conference Papers

[P55]Keshav Goyal and Tobias Mömke
Robust Reoptimization of Steiner Trees.
FSTTCS, 2015.
[P54]Holger Dell, Eunjung Kim, Michael Lampis, Valia Mitsou and Tobias Mömke
Complexity and Approximability for Parameterized CSPs.
IPEC, 2015.
[P53]Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, Laszlo Kozma and Thatchaphol Saranurak
Greedy Is an Almost Optimal Deque.
WADS, 2015.
[P52]Tobias Mömke, Andreas Wiese
A (2+epsilon)-Approximation Algorithm for the Storage Allocation Problem.
42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) in LNCS 9134:973-984. Springer, 2015.
[P51]Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai and Thatchaphol Saranurak
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.
STOC, 2015.
[P50]Christian Engels
Dichotomy Theorems for Homomorphism Polynomials of Graph Classes.
Workshop on Algorithms and Computation (WALCOM 2015), 2015.
[P49]Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese
New Approximation Schemes for Unsplittable Flow on a Path.
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

Journal Articles

[J27]Tobias Mömke
An Improved Approximation Algorithm for the Traveling Salesman Problem with Relaxed Triangle Inequality.
Information Processing Letters, 115:866-871, 2015.
PDF

2014

Conference Papers

[P48]Radu Curticapean, Dániel Marx
Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts.
55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014), 2014.
[P47]Dennis Komm, Rasitislav Královic, Richard Královic, Tobias Mömke
Randomized Online Algorithms with High Probability Guarantees.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), 2014.

Book Chapters

[B3]Markus Bläser
Explicit Tensors.
Perspectives in Computational Complexity in Progress in Computer Science and Applied Logic 26:117-131. Springer, 2014.
PDF

2013

Conference Papers

[P46]Radu Curticapean, Marvin Künnemann
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
European Symposium on Algorithms (ESA), 2013.
[P45]Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems.
Mathematical Foundations of Computer Science (MFCS), 8087:219-230, 2013.
[P44]Radu Curticapean
Counting Matchings of Size k is #W[1]-hard.
40th International Colloquium on Automata, Languages and Programming (ICALP), 2013.
[P43]Markus Bläser
Noncommutativity Makes Determinants Hard.
40th Int. Coll. on Automata, Languages, and Programming (ICALP 2013) in LNCS 7965:172-183. Springer, 2013.
PDF

Journal Articles

[J26]Markus Bläser
Fast Matrix Multiplication.
Theory of Computing, Graduate Surveys, 5:1-60, 2013.
[J25]Hans-Joachim Böckenhauer, Tobias Mömke, Monika Steinová
Improved Approximations for TSP with Simple Precedence Constraints.
Journal of Discrete Algorithms (JDA), 21:32-40, Elsevier, 2013.
[J24]Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
Algorithmica, 66(2):397-418, 2013.
PDF

2012

Conference Papers

[P42]Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs.
Mathematical Foundations of Computer Science (MFCS), 2012.
PDF
[P41]Markus Bläser, Radu Curticapean
Weighted Counting of k-Matchings is #W[1]-hard.
7th International Symposium on Parameterized and Exact Computation (IPEC), 2012.
[P40]Markus Bläser, Konstantinos Panagiotou, B. V. Raghavendra Rao
A Probabilistic Analysis of Christofides' Algorithm.
13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), 2012.
[P39]Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray
Counting crossing-free structures.
28. Symposium on Computational Geometry 2012: Chapel Hill, NC, USA (SoCG 2012), 2012.
[P38]Markus Bläser, Bodo Manthey
Smoothed Complexity Theory.
37th Int. Symp. on Mathematical Foundations of Computer Science (MFCS 2012), 2012.
PDF
[P37]Markus Bläser, Bekhan Chokaev
Algebras of Minimal Multiplicative Complexity.
IEEE Conference on Computational Complexity, 2012.
PDF

Journal Articles

[J23]Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
Counting classes and the fine structure between NC1 and L.
Theoretical Computer Science, 417, 2012.
[J22]Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, B. V. Raghavendra Rao
Faster algorithms for finding and counting subgraphs.
Journal of Computer and System Sciences, 2012.
[J21]Markus Bläser, Holger Dell, Mahmoud Fouz
Complexity and Approximability of the Cover Polynomial.
computational complexity, 21(3):359-419, Springer, 2012.
PDF

2011

Conference Papers

[P36]Raghavendra Rao B. V. and Jayalal Sarma M. N.
Isomorphism Testing of Read-once Functions and Polynomials.
Foundations of Software Technology and Theoretical Computer Science (2011), 13:115-126, 2011.
PDF
[P35]Markus Bläser, Radu Curticapean
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree.
36. International Symposium on Mathematical Foundations of Computer Science (MFCS), 6907:96-107, 2011.
[P34]Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
Algorithms and Data Structures Symposium (WADS), 12:110-121, 2011.
[P33]Alexey Pospelov
Faster Polynomial Multiplication via Discrete Fourier Transforms.
International Computer Science Symposium in Russia (CSR), 6:91-104, 2011.
[P32]Alexey Pospelov
Fast Fourier Transforms over Poor Fields.
International Symposium on Symbolic and Algebraic Computation (ISSAC), 36:289-296, 2011.
[P31]Benjamin Doerr, Mahmoud Fouz, Tobias Friedrich
Social Networks Spread Rumors in Sublogarithmic Time.
ACM Symposium on Theory of Computing (STOC), 43:21-30, 2011.
[P30]Alexey Pospelov
Group-theoretic Lower Bounds for the Complexity of Matrix Multiplication.
Conference on Theory and Applications of Models of Computation (TAMC), 8:2-13, 2011.
[P29]Markus Bläser, Christian Engels
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals.
Symposium on Theoretical Aspects of Computer Science (STACS), 9:555-566, 2011.

Journal Articles

[J20]B. V. Raghavendra Rao, Jayalal M. N. Sarma:
On the Complexity of Matroid Isomorphism Problem.
Theory of Computing Systems, 49(2), 2011.
[J19]Markus Bläser and Christian Hoffmann
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
Algorithmica, 61(1):3-35, 2011.
[J18]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Privacy in Non-private Environments.
Theory Comput. Syst., 48(1):211-245, 2011.

2010

Conference Papers

[P28]Khaled Elbassioni, Mahmoud Fouz, Chaitanya Swamy
Approximation Algorithms for Non-Single-minded Profit-Maximization Problems with Limited Supply.
Workshop on Internet & Networking (WINE), 6:462-472, 2010.
[P27]George Christodoulou,Khaled Elbassioni, Mahmoud Fouz
Truthful Mechanisms for Exhibitions.
Workshop on Internet & Networking (WINE), 6:170-181, 2010.
[P26]Christian Hoffmann
Exponential Time Complexity of Weighted Counting of Independent Sets.
International Symposium on Parameterized and Exact Computation (IPEC), 5:180-191, 2010.
[P25]Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, and Heribert Vollmer
Counting classes and the fine structure between NC1 and L.
International Symposium on Mathematical Foundations of Computer Science (MFCS) in Lecture Notes in Computer Science .
PDF
[P24]Benjamin Doerr, Mahmoud Fouz, Carsten Schmitt
Quasirandom Evolutionary Algorithms.
Genetic and Evolutionary Computation Conference (GECCO), 2010.

Journal Articles

[J17]Benjamin Doerr, Mahmoud Fouz
Quasi-Random Rumor Spreading: Reducing Randomness Can Be Costly.
Information Processing Letters, 111:227-230, 2010.
[J16]Markus Bläser, Holger Dell, Johann Makowsky
Complextiy of the Bollobas-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory of Computing Systems, 46(4):690-706, 2010.
PDF
[J15]Christian Hoffmann
A Most General Edge Elimination Polynomial - Thickening of Edges.
Fundamenta Informaticae, 98(4):373-378, 2010.
PDF

2009

Conference Papers

[P23]Bodo Manthey, Heiko Röglin
Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.
International Symposium on Algorithms and Computation (ISAAC) in Lecture Notes in Computer Science 5878:1024-1033. Springer, 2009.
[P22]David Arthur, Bodo Manthey, Heiko Röglin
k-Means has Polynomial Smoothed Complexity.
IEEE Symposium on Foundations of Computer Science (FOCS), 2009.
[P21]Bodo Manthey
Multi-Criteria TSP: Min and Max Combined.
International Workshop on Approximation and Online Algorithms (WAOA) in Lecture Notes in Computer Science 5893:205-2162009.
[P20]Benjamin Doerr, Mahmoud Fouz, Martin Schmitt, Magnus Wahlström
BBOB: Nelder-Mead with Resize and Halfruns.
Conference on Genetic and Evolutionary Computation Conference (GECCO), 2009.
[P19]Benjamin Doerr, Mahmoud Fouz
A Time-Randomness Tradeoff for Quasi-Random Rumor Spreading.
European Conference on Combinatorics, Graph Theory and Applications (EuroComb), 2009.
[P18]Markus Bläser, Christian Hoffmann
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
European Symposium on Algorithms (ESA) in Lecture Notes in Computer Science 5757:623-6342009.
PDF
[P17]Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi
On Smoothed Analysis of Quicksort and Hoare's Find.
International Computing and Combinatorics Conference (COCOON) in Lecture Notes in Computer Science 5609:158-167. Springer, 2009.
[P16]Bodo Manthey
On Approximating Multi-Criteria TSP.
International Symposium on Theoretical Aspects of Computer Science (STACS), 2009.
[P15]Bodo Manthey, Heiko Röglin
Improved Smoothed Analysis of the k-Means Method.
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.

Journal Articles

[J14]Markus Bläser, Andreas Meyer de Voltaire
Semisimple algebras of almost minimal rank over the reals.
Theoretical Computer Science, 410(50):5202-5214, 2009.
PDF
[J13]Markus Bläser, L. Shankar Ram, Maxim Sviridenko
Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems.
Operations Research Letters, 37(3):176-180, 2009.
PDF
[J12]Bodo Manthey
Minimum-weight Cycle Covers and Their Approximability.
Discrete Applied Mathematics, 157(7):176-180, 2009.
[J11]Christian Engels, Bodo Manthey
Average-Case Approximation Ratio of the 2-Opt Algorithm for the TSP.
Operations Research Letters, 37(2):83-84, 2009.
[J10]Jan Arpe, Bodo Manthey
Approximability of Minimum AND-Circuits.
Algorithmica, 53(3):337-357, 2009.
[J9]Bodo Manthey, L. Shankar Ram
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems.
Algorithmica, 53(1):69-88, 2009.
[J8]Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi
Deterministically Testing Sparse Polynomial Identities of Unbounded Degree.
Information Processing Letters, 109(3):187-192, 2009.
PDF

Research Reports

[R9]Markus Bläser, Christian Hoffmann
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
arXiv:0902.1693 [cs.DS], 2009.
[R8]David Arthur, Bodo Manthey, Heiko Röglin
k-Means has Polynomial Smoothed Complexity.
arXiv:0904.1113 [cs.DS], 2009.
[R7]Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi
Smoothed Analysis of Quicksort and Hoare's Find.
arXiv:0904:3898 [cs.DS], 2009.

2008

Conference Papers

[P14]Markus Bläser, Bodo Manthey, Oliver Putz
Approximating Multi-Criteria Max-TSP.
European Symposium on Algorithms (ESA) in Lecture Notes in Computer Science 5193:185-197. Springer, 2008.
[P13]Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
Mathematical Foundations of Computer Science (MFCS) in Lecture Notes in Computer Science 5162:467-478. Springer, 2008.
[P12]Markus Bläser, Moritz Hardt, David Steurer
Asymptotically Optimal Hitting Sets Against Polynomials.
International Colloquium on Automata, Languages and Programming (ICALP) in Lecture Notes in Computer Science 5125:345-356. Springer, 2008.
PDF
[P11]Markus Bläser, Holger Dell, Johann A. Makowsky
Complexity of the Bollobás-Riordan Polynomial.
International Computer Science Symposium in Russia (CSR) in Lecture Notes in Computer Science 5010:86-98. Springer, 2008.
PDF
[P10]Markus Bläser, Elias Vicari
Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity.
Symposium on Algorithmic Game Theory (SAGT) in Lecture Notes in Computer Science 4997:206-2017. Springer, 2008.
PDF
[P9]Markus Bläser, Christian Hoffmann
On the Complexity of the Interlace Polynomial.
Symposium on Theoretical Aspects of Computer Science (STACS), 2008.

Book Chapters

[B2]Markus Bläser
Metric TSP.
Encyclopedia of Algorithms, 2008.

Journal Articles

[J7]Markus Bläser
A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality.
ACM Transactions on Algorithms, 4(4), 2008.
PDF
[J6]Bodo Manthey
On Approximating Restricted Cycle Covers.
SIAM Journal on Computing, 38(1):181-206, 2008.
[J5]Markus Bläser, L. Shankar Ram
Approximate Fair Cost Allocation in Metric Traveling Salesman Games.
Theory of Computing Systems, 43(1):19-37, 2008.
PDF
[J4]Markus Bläser, Thomas Heynen, Bodo Manthey
Adding Cardinality Constraints to Integer Programs with Applications to Maximum Satisfiability.
Information Processing Letters, 105(5):194-198, 2008.

2007

Conference Papers

[P8]Bodo Manthey, L. Shankar Ram
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems.
Approximation and Online Algorithms, Fourth International Workshop (WAOA) in Lecture Notes in Computer Science 4368:302-315. Springer, 2007.
[P7]Bodo Manthey
Minimum-weight Cycle Covers and Their Approximability.
Graph-Theoretic Concepts in Computer Science, 33rd International Workshop (WG 2007) in Lecture Notes in Computer Science 4769:178-189. Springer, 2007.
[P6]Markus Bläser, Andreas Meyer de Voltaire
Semisimple Algebras of Almost Minimal Rank over the Reals.
Mathematical Foundations of Computer Science 2007, 32nd International Symposium (MFCS) in Lecture Notes in Computer Science 4708:669-6802007.
PDF
[P5]Markus Bläser, Holger Dell
Complexity of the Cover Polynomial.
Automata, Languages and Programming, 34th International Colloquium (ICALP) in Lecture Notes in Computer Science 4596:801-8122007.
[P4]Deepak Ajwani, Ulrich Meyer, Vitaly Osipov
Improved External Memory BFS Implementations.
Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), 2007.

Journal Articles

[J3]Bodo Manthey, Rüdiger Reischuk
Smoothed Analysis of Binary Search Trees.
Theoretical Computer Science, 378(3):292-315, 2007.

Research Reports

[R6]Bodo Manthey, L. Shankar Ram
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems.
arXiv:cs/0606040 [cs.DS], 2007.
[R5]Markus Bläser, Christian Hoffmann
On the Complexity of the Interlace Polynomial.
arXiv:0707.4565 [cs.CC], 2007.
[R4]Bodo Manthey
Minimum-weight Cycle Covers and Their Approximability.
Minimum-weight Cycle Covers and Their Approximability, 2007.
[R3]Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise.
Electronic Colloquium on Computational Complexity (ECCC), 2007.
[R2]Bodo Manthey
On Approximating Restricted Cycle Covers.
Electronic Colloquium on Computational Complexity (ECCC), 2007.

2006

Conference Papers

[P3]Bodo Manthey
Approximations Algorithms for Restricted Cycle Covers Based on Cycle Decompositions.
Graph-Theoretic Concepts in Computer Science, 32nd International Workshop (WG 2006) in Lecture Notes in Computer Science 4271:292-303. Springer, 2006.
[P2]Jan Arpe, Bodo Manthey
Approximability of Minimum AND-Circuits.
10th Scandinavian Workshop on Algorithm Theory (SWAT 2006) in Lecture Notes in Computer Science 4059:292-303. Springer, 2006.

Book Chapters

[B1]Bodo Manthey
Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees.
Ausgezeichnete Informatikdissertationen in Lecture Notes in Informatics .

Journal Articles

[J2]Markus Bläser, Bodo Manthey, Jiří Sgall
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality.
Journal of Discrete Algorithms (JDA), 4(4):623-632, 2006.
[J1]Markus Bläser, Andreas Jakoby, Maciej Liśkiewicz, Bodo Manthey
Private Computation: k-Connected versus 1-Connected Networks.
Journal of Cryptology (JOC), 19(3):341-357, 2006.

Research Reports

[R1]Jan Arpe, Bodo Manthey
Approximability of Minimum AND-Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2006.

2005

Conference Papers

[P1]Markus Bläser, L. Shankar Ram
Approximate Fair Cost Allocation in Metric Traveling Salesman Games.
Approximation and Online Algorithms, Third International Workshop (WAOA) in Lecture Notes in Computer Science 3879:82-95. Springer, 2005.