Computational Complexity - Publications

2011 and forthcoming

Conference Papers

[P36]	Markus Bläser, Radu Curticapean. The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), 6907:96-107, 2011.
[P35]	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 (FSTTCS 2011), 13:115-126, 2011.
[P34]	Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao. Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals The 12th Algorithms and Data Structures Symposium (WADS 2011), 12:110-121, 2011.
[P33]	Alexey Pospelov. Faster Polynomial Multiplication via Discrete Fourier Transforms The 6th International Computer Science Symposium in Russia (CSR 2011), 6:91-104, 2011.
[P32]	Alexey Pospelov. Fast Fourier Transforms over Poor Fields The 36th International Symposium on Symbolic and Algebraic Computation (ISSAC 2011), 36:289-296, 2011.
[P31]	Alexey Pospelov. Group-theoretic Lower Bounds for the Complexity of Matrix Multiplication The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), 8:2-13, 2011.
[P30]	Benjamin Doerr, Mahmoud Fouz, Tobias Friedrich. Social Networks Spread Rumors in Sublogarithmic Time ACM Symposium on Theory of Computing (STOC 2011), 43:21-30, 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 2011), 9:555-566, 2011.

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.
[J15]	Christian Hoffmann. A Most General Edge Elimination Polynomial - Thickening of Edges. Fundamenta Informaticae, 98(4):373-378, 2010.

Conference Papers

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

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.
[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.
[J12]	Bodo Manthey. Minimum-weight Cycle Covers and Their Approximability. Discrete Applied Mathematics, 157(7):1470-1480, 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.

Conference Papers

[P23]	Benjamin Doerr, Mahmoud Fouz. A Time-Randomness Tradeoff for Quasi-Random Rumor Spreading. European Conference on Combinatorics, Graph Theory and Applications (EuroComb '09).
[P22]	Bodo Manthey, Heiko Röglin. Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences. In Yingfei Dong, Ding-Zhu Du, Oscar Ibarra (eds.): Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009, Proceedings, vol. 5878 of Lecture Notes in Computer Science, pp. 1024-1033. Springer, 2009.
[P21]	Bodo Manthey. Multi-Criteria TSP: Min and Max Combined. In Evripidis Bampis, Klaus Jansen (eds.): Approximation and Online Algorithms, 7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Papers, vol. 5893 of Lecture Notes in Computer Science, pp. 205-216. Springer 2010.
[P20]	David Arthur, Bodo Manthey, Heiko Röglin. k-Means has Polynomial Smoothed Complexity. In Proc. 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), October 24-27, 2009. Atlanta, GA, USA, pp. 405-414. IEEE Computer Society, 2009.
[P19]	Markus Bläser, Christian Hoffmann. Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. In Amos Fiat, Peter Sanders (eds.): Algorithms – ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings, vol. 5757 of Lecture Notes in Computer Science, pp. 623-634, Springer 2009.
[P18]	Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi. On Smoothed Analysis of Quicksort and Hoare's Find. In Hung Q. Ngo (ed.): Computing and Combinatorics, 15th Annual International Conference, COCOON 2009, Niagara Falls, NY, USA, July 2009, Proceedings, vol. 5609 of Lecture Notes in Computer Science, pp. 158-167. Springer, 2009.
[P17]	Benjamin Doerr, Mahmoud Fouz, Martin Schmitt, Magnus Wahlström. BBOB: Nelder-Mead with Resize and Halfruns. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO 2009), Montreal, Québec, Canada, July 08-12, 2009, Companion Material, pages 2239-2246. ACM, 2009.
[P16]	Bodo Manthey. On Approximating Multi-Criteria TSP. In Susanne Albers, Jean-Yves Marion (eds.): Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pages 637-648. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009.
[P15]	Bodo Manthey, Heiko Röglin. Improved Smoothed Analysis of the k-Means Method. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pp. 461-470. SIAM, 2009.

Research Reports

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

2008

Book Chapters

[C2]

Markus Bläser. Metric TSP. In Ming-Yang Kao (Ed.): Encyclopedia of Algorithms, pp. 517-519. Springer, 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.
[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.
[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.

Conference Papers

[P14]	Markus Bläser, Bodo Manthey, Oliver Putz. Approximating Multi-Criteria Max-TSP. In Dan Halperin, Kurt Mehlhorn (eds.): Algorithms – ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings, vol. 5193 of Lecture Notes in Computer Science, pp. 185-197. Springer, 2008.
[P13]	Bodo Manthey, Till Tantau. Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. In Edward Ochmański, Jerzy Tyszkiewicz (eds.): Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Toruń, Poland, August 25-29, 2008, Proceedings, vol. 5162 of Lecture Notes in Computer Science, pp. 467-478. Springer, 2008.
[P12]	Markus Bläser, Moritz Hardt, David Steurer. Asymptotically Optimal Hitting Sets Against Polynomials. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz (Eds.): Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I, vol. 5125 of Lecture Notes in Computer Science, pp. 345-356. Springer, 2008.
[P11]	Markus Bläser, Holger Dell, Johann A. Makowsky. Complexity of the Bollobás-Riordan Polynomial. In Edward A. Hirsch, Alexander A. Razborov, Alexei Semenov, Anatol Slissenko (Eds.): Computer Science – Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings, vol. 5010 of Lecture Notes in Computer Science, pp. 86-98. Springer, 2008.
[P10]	Markus Bläser, Elias Vicari. Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity. In Burkhard Monien, Ulf-Peter Schroeder (Eds.): Algorithmic Game Theory, First International Symposium, SAGT 2008, Paderborn, Germany, April 30-May 2, 2008, Proceedings, vol. 4997 of Lecture Notes in Computer Science, pp. 206-217. Springer, 2008.
[P9]	Markus Bläser, Christian Hoffmann. On the Complexity of the Interlace Polynomial. In Susanne Albers, Pascal Weil (Eds.): Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), pages 97-108. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2009.

Research Reports

[R10]	Bodo Manthey. On Approximating Multi-Criteria TSP. arXiv:0711.2157 [cs.DS], 2008.
[R9]	Bodo Manthey, Heiko Röglin. Improved Smoothed Analysis of the k-Means Method. arXiv:0809.1715 [cs.DS], 2008.
[R8]	Markus Bläser, Bodo Manthey, Oliver Putz. Approximating Multi-Criteria Max-TSP. arXiv:0806.3668 [cs.DS], 2008.
[R7]	Christian Hoffmann. A Most General Edge Elimination Polynomial — Thickening of Edges. arXiv:0801.1600 [math.CO], 2008.

2007

Journal Articles

[J3]

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

Conference Papers

[P8]	Bodo Manthey. Minimum-weight Cycle Covers and Their Approximability. In Andreas Brandstädt, Dieter Kratsch, Haiko Müller (Eds.): Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers, vol. 4769 of Lecture Notes in Computer Science, pp. 178-189. Springer, 2007.
[P7]	Markus Bläser, Andreas Meyer de Voltaire. Semisimple Algebras of Almost Minimal Rank over the Reals. In Luděk Kučera, Antonín Kučera (Eds.): Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Český Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 of Lecture Notes in Computer Science, pp. 669-680. Springer, 2007.
[P6]	Markus Bläser, Holger Dell. Complexity of the Cover Polynomial. In Lars Arge, Christian Cachin, Tomasz Jurdziński, Andrzej Tarlecki (Eds.): Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wrocław, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pp. 801-812. Springer, 2007.
[P5]	Deepak Ajwani, Ulrich Meyer, Vitaly Osipov. Improved External Memory BFS Implementations. In: Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX 2007), pp. 3-12. SIAM, 2007.
[P4]	Bodo Manthey, L. Shankar Ram. Approximation Algorithms for Multi-Criteria Traveling Salesman Problems. In Thomas Erlebach, Christos Kaklamanis (Eds.): Approximation and Online Algorithms, Fourth International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006, Revised Papers, volume 4368 of Lecture Notes in Computer Science, pp. 302-315. Springer, 2007.

Research Reports

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

2006

Book Chapters

[C1]

Bodo Manthey. Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees. In Dorothea Wagner, Abraham Bernstein, Thomas Dreier, Steffen Hölldobler, Günter Hotz, Klaus-Peter Löhr, Paul Molitor, Gustaf Neumann, Rüdiger Reischuk, Dietmar Saupe, and Myra Spiliopoulou (Eds.): Ausgezeichnete Informatikdissertationen 2005, volume D-6 of GI-Edition – Lecture Notes in Informatics, pp. 57-66. Köllen, 2006.

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, 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, 19(3):341-357, July 2006.

Conference Papers

[P3]	Bodo Manthey. Approximations Algorithms for Restricted Cycle Covers Based on Cycle Decompositions. In Fedor V. Fomin (Ed.): Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers, vol. 4271 of Lecture Notes in Computer Science, pp. 336-347. Springer, 2006.
[P2]	Jan Arpe, Bodo Manthey. Approximability of Minimum AND-Circuits. In Lars Arge, Rusins Freivalds (Eds.): Algorithm Theory – SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, vol. 4059 of Lecture Notes in Computer Science, pp. 292-303. Springer, 2006.
[P1]	Markus Bläser, L. Shankar Ram. Approximate Fair Cost Allocation in Metric Traveling Salesman Games. In Thomas Erlebach, Giuseppe Persiano (Eds.): Approximation and Online Algorithms, Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers, vol. 3879 of Lecture Notes in Computer Science, pp. 82-95. Springer, 2006.

Research Reports

[R1]

Jan Arpe, Bodo Manthey. Approximability of Minimum AND-Circuits. Electronic Colloquium on Computational Complexity (ECCC), Revision 1 of Technical Report 06-045, 2006.

Copyright Notice: The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.