Publications by Klaus Meer

Theses

"Quadratic Programming: Complexity Issues in Real Number Models."
Klaus Meer
Habilitation thesis RWTH Aachen, Mathematisch-Naturwissenschaftliche Fakultät;
Verlag Shaker Aachen, 1996, ISBN 978-3-8265-1803-4

"Komplexitätsbetrachtungen für reelle Maschinenmodelle."
Klaus Meer
Dissertation thesis RWTH Aachen, Mathematisch-Naturwissenschaftliche Fakultät, Verlag Shaker Aachen, 1993, ISBN 978-3-86111-385-0

"Über Dualitätseigenschaften in Abelschen Gruppen."
Klaus Meer
Diplomarbeit (Master's thesis), RWTH Aachen, Mathematisch-Naturwissenschaftliche Fakultät, 1988.

Books

Edited work:

Proceedings Graph-Theoretic Concepts in Computer Science - 44th International Workshop WG 2018,
Cottbus, Germany, June 27-29, 2018.
Andreas Brandstädt, Ekkehard Köhler, Klaus Meer (Editors).
Lecture Notes in Computer Science 11159, Springer 2018, ISBN 978-3-030-00255-8

Proceedings 45. Jahrestagung der Gesellschaft für Informatik, Informatik 2015, Informatik, Energie und Umwelt, 28. September - 2. Oktober 2015 in Cottbus, Deutschland.
Douglas W. Cunningham, Petra Hofstedt, Klaus Meer, Ingo Schmitt (Hrsg.).
LNI 246, GI, ISBN 978-3-88579-640-4

Language, Life, Limits - Proceedings 10th Conference on Computability in Europe CiE 2014,
Budapest, Hungary, June 23-27, 2014.
Arnold Beckmann, Erzsébet Csuhaj-Varjú, Klaus Meer (Editors).
Lecture Notes in Computer Science 8493, Springer 2014, ISBN 978-3-319-08018-5

Monography:

Optimization Theory
H.Th. Jongen, K. Meer,  E. Triesch.
Kluwer Academic Publishers, Springer
June 2004, ISBN 1-4020-8099-9
For the table of contents click here

Journals and contributions to books (peer reviewed)

"Interactive Proofs and a Shamir-like Result for Real Number Computations."
Martijn Baartse and Klaus Meer
Accepted for publication in Computational Complexity. Online version here.

"An algebraic proof of the real number PCP theorem."

Martijn Baartse and Klaus Meer
Journal of Complexity, Vol. 40, pp 34--77, 2017.The article won the Best Paper Award 2017 of the Journal of Complexity. Online version here

"Generalized finite automata over real and complex numbers."
Klaus Meer and Ameen Naif
Theoretical Computer Science, Vol. 591, 85-98, 2015.
Online version click here.

"The PCP theorem for NP over the reals."
Martijn Baartse and Klaus Meer
Foundations of Computational Mathematics, Vol. 15, Issue 3, 651-680, 2015.
Online version click here.

"An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents."
Klaus Meer
Theory of Computing Systems, Volume 55, Issue 2, pp 330-346, 2014.

"Topics in Real and Complex Number Complexity Theory."
Martijn Baartse and Klaus Meer
In: Recent Advances in Real Complexity and Computation, Contemporary Mathematics Vol. 604, J.L. Montana, L.M. Pardo (Eds.), American Mathematical Society, 1--53, 2013.

"On Ladner's result for a class of real machines with restricted use of constants."
Klaus Meer
Information and Computation, Volume 210, 13-20, 2012.

"Some initial thoughts on bounded query computations over the reals."
Klaus Meer
Special Issue on 'Frontier between Decidability and Undecidability and Related Problem', International Journal of Foundations of Computer Science, Vol. 23, No.7, 1499-1510, 2012.

"On the expressive power of CNF formulas of bounded Tree- and Clique-Width."
Irénée Briquel, Pascal Koiran, and Klaus Meer
Discrete Applied Mathematics, Vol. 159 (1), 1-14, 2011.

"Treewidth in algebraic complexity."
Klaus Meer
Fundamenta Informaticae, Vol. 98 (4), 391-409, 2010.

"Real Computational Universality: The word problem for a class of groups with infinite presentation."
Klaus Meer and Martin Ziegler
Foundations of Computational Mathematics, Vol. 9(5), 599-609, 2009.

"On the OBDD size for graphs of bounded tree- and clique-width"
Klaus Meer and Dieter Rautenbach
Discrete Mathematics, Volume 309, Issue 4, 843-851, 2009.

"An explicit solution to Post's problem over the reals."
Klaus Meer and Martin Ziegler
Journal of Complexity, Volume 24, Issue 1, 3-15, 2008.

"Complexity aspects of a semi-infinite optimization problem."
Klaus Meer
Optimization Vol. 57, Issue 1, 143-152, 2008.

"Simulated Annealing versus Metropolis for a TSP instance."
Klaus Meer
Information Processing Letters, Volume 104, Issue 6, 216-219, 2007.

"On some relations between approximation and PCPs over the real numbers."
Klaus Meer
Theory of Computing Systems, Springer, vol. 41, 107-118, 2007.

"Computing Multi-homogeneous B\'ezout numbers is hard."
Gregorio Malajovich and Klaus Meer
Theory of Computing Systems, Springer, vol. 40, 553-570, 2007.

"Two logical hierarchies of optimization problems over the real numbers."
Uffe Flarup and Klaus Meer
Mathematical Logic Quarterly, vol. 52 no. 1, 37-50, 2006.

"Transparent long proofs: A first PCP theorem for NP_R."
Klaus Meer
Foundations of Computational Mathematics, Springer, vol. 5 nr.3, 231-255, 2005.

"Probabilistically checkable proofs over the reals."
Klaus Meer
Proc. Workshop on Logic, Language, Information and Computation WOLLIC'2004. Electronic Notes in Theoretical Computer Science ENTCS, vol. 123, 165-177, 2005.

"On a refined analysis of some problems in interval arithmetic using real number complexity theory."
Klaus Meer
Reliable Computing, Vol. 10, No.3, 209-225, 2004.

"A step towards a complexity theory for analog systems."
Marco Gori and Klaus Meer
Mathematical Logic Quarterly, 48, Suppl. 1, 45-58, 2002.

"Dimensional Synthesis of Planar Stephenson-Mechanisms for Motion Generation by Circlepoint Search and Homotopy Methods."
Klaus Meer, Burkhard Schmitt and Harold Schreiber
Mechanism and Machine Theory, Vol. 37, Nr. 7, 717-737, 2002.

"Polynomials of bounded tree-width."
J.A. Makowsky and Klaus Meer
Foundations of Computational Mathematics, Proceedings of the Smalefest 2000, F. Cucker and M. Rojas (eds.), World Scientific, 211-250, 2002.

"Some aspects of studying an optimization or decision problem in different computational models."
Klaus Meer and Gerhard-Wilhelm Weber
European Journal of Operational Research, Vol. 143, Issue 2, 406-418, 2002.

"Counting problems over the reals."
Klaus Meer
Theoretical Computer Science, vol. 242, 1-2, 41-58, 2000.

"A note on non-complete problems in NP_R."
Shai Ben-David, Klaus Meer and Christian Michaux
Journal of Complexity, vol. 16, no. 1, 324-332, 2000. Download (access to Science Direct required).

"On the computational structure of the connected components of difficult sets."
Martin Matamala and Klaus Meer
Information Processing Letters, vol. 72, issue 3-4, 83-90, 1999. Download (access to Science Direct required)

"Logics which capture complexity classes over the reals."
Felipe Cucker and Klaus Meer
Journal of Symbolic Logic, Vol. 64, No.1, 363-390, 1999.

"On the structure of NP_C."
Gregorio Malajovich and Klaus Meer
SIAM Journal on Computing, Vol. 28, No.1, 27-35, 1999. Download

"Innere-Punkt Methoden für die automatisierte Fehlersuche in geodätischen Anwendungen (Interior point methods for automatic blunders detection in surveying)" (in german)
Wilhelm Benning, Ashraf A. Elkoushy and Klaus Meer
Allgemeine Vermessungsnachrichten, AVN 104, 319-324, 1997.

"Semi-algebraic complexity - Additive complexity of matrix computational tasks."
Thomas Lickteig and Klaus Meer
In: Festschrift in honor of S. Winograd, Journal of Complexity Vol. 13, Nr. 1, 83-107, 1997.

"A Survey on Real Structural Complexity Theory."
Klaus Meer and Christian Michaux
Bulletin of the Belgian Mathematical Society Simon Stevin 4, 113-148, 1997.

"Semi-algebraic complexity - Additive complexity of diagonalization of quadratic forms."
Thomas Lickteig and Klaus Meer
Proceedings ``Real algebraic and analytic geometry" RAAG , Segovia 1995 Revista Matem\'atica de la Universidad Complutense de Madrid, Vol. 10, n\'umero suplementario, 183-207, 1997.

"Descriptive Complexity Theory over the real numbers."
Erich Grädel and Klaus Meer
Proceedings of the AMS-SIAM Summer School : "Mathematics of Numerical Analysis - Real Number Algorithms", 1995, ed.: J. Renegar, M. Shub, S. Smale, Lecture Notes in Applied Mathematics vol. 32, 381-403.

"A note on testing the resultant."
Thomas Lickteig and Klaus Meer
Journal of Complexity, volume 11, issue 3, 344-351, 1995.

"On the relations between discrete and continuous complexity theory."
Klaus Meer
Mathematical Logic Quarterly, volume 41, issue 2, 281-286, 1995.

"On the complexity of Quadratic Programming in real number models of computation."
Klaus Meer
Theoretical Computer Science, volume 133, issue 1, 85-94, 1994.

"Real number models : on the use of information."
Klaus Meer
Journal of Symbolic Computation, vol. 18, issue 3, 199-206, 1994.

"Real number models under various sets of operations."
Klaus Meer
Journal of Complexity, volume 9, issue 3, 366-372, 1993.

"A note on a $ P \neq NP-$ result in a restricted class of real machines."
Klaus Meer
Journal of Complexity, volume 8, issue 4, 451-453, 1992.

"Computations over Z and R : a comparison."
Klaus Meer
Journal of Complexity, volume 6, issue 3, 256-263, 1990.

Conference proceedings (peer reviewed)

"Real Interacive Proofs for VPSPACE."
Martijn Baartse and Klaus Meer
Extended abstract in: Proc. 41st Interantional Symposium on Mathematical Foundations of Computer Science, Krakow, P. Faliszewski, A. Muscholl, R. Nierdermeier (eds.), Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl, DOI: 10.4230/LIPIcs.MFCS.2016.14,URL: http://drops.dagstuhl.de/opus/volltexte/2016/6430/, 14:1-14:3, 2016.

"Periodic Generalized Automata over the Reals."
Klaus Meer and Ameen Naif
Extended abstract in: Proc. 10th International Conference on Language and Automata Theory and Applications LATA 2016, Prague, Adrian-Horia Dediu, Jan Janousek, Carlos Martín-Vide, and Bianca Truthe (eds.), Springer LNCS 9618, 168--180, 2016.


"An algebraic proof of the real number PCP theorem."

Martijn Baartse and Klaus Meer
Extended abstract  to appear in: Proc. 40th conference Mathematical Foundations of Computer Science MFCS 2015, Springer LNCS, 2015.

"Some results on interactive proofs for real computations."
Martijn Baartse and Klaus Meer
Extended abstract in: Proc. 11th conference Computability in Europe CiE 2015, Bucharest, A. Beckmann, V. Mitrana, M. Soskova (eds.), Springer LNCS 9136, 107--116, 2015.

"Testing Low Degree Trigonometric Polynomials."
Martijn Baartse and Klaus Meer
Extended abstract in: Proc. 9th International Computer Science Symposium in Russia CSR 2014, Moscow, N.K. Vereshchagin, E.A. Hirsch, S.O. Kuznetsov, J.E. Pin (eds.), Springer LNCS 8476,  77--96, 2014.

"Generalized Finite Automata over Real and Complex Numbers."
Klaus Meer and Ameen Naif
Extended abstract in: Proc. 11th annual conference on Theory and Applications of Models of Computational TAMC 2014, Chennai, M. Agrawal, B. Cooper, TV Gopal, A.Li (eds.), Springer LNCS 8402, 168--187, 2014.

"The PCP theorem for NP over the reals."
Martijn Baartse and Klaus Meer
Extended abstract in: Proc. 30th Symposium on Theoretical Aspects of Computer Science STACS 2013, Leibniz International Proceedings in Informatics (LIPIcs) series Vol. 20, Schloss Dagstuhl, 104--115, 2013

"Almost transparent short proof for NP_R."
Klaus Meer
Extended abstract in: Proc. 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, Lecture Notes in Computer Science 6914, 41-52, 2011.

"An extended tree-width notion for directed graphs related to the computation of permanents."
Klaus Meer
Extended Abstract in: Proc. 6th Computer Science Symposium in Russia CSR 2011, St. Petersburg, Lecture Notes in Computer Science 6651, 247-260, 2011.

"On Ladner's result for a class of real machines with restricted use of constants"
Klaus Meer
Extended Abstract in: Proc. 5th Conference on Computability in Europe 2009: Mathematical Theory and Computational Practice, Heidelberg, Lecture Notes in Computer Science 5635, 352-361, 2009.

"On the expressive power of CNF formulas of bounded tree- and clique-width."
Pascal Koiran and Klaus Meer
Extended abstract in: Proc. 34th International Workshop on Graph-Theoretic Concepts in Computer Science Durham, UK, 2008, Lecture Notes in Computer Science 5344, 252-263, 2008.

"Real Computational Universality: The word problem for a class of groups with infinite presentation."
Klaus Meer and Martin Ziegler
Extended Abstract in: Proceedings 32nd International Symposium on Mathematical Foundations of Computer Science, Cesky Krumlov, Czech Republic, 2007, Lecture Notes in Computer Science 4708, 726-737, 2007.

"Some aspects of a complexity theory for continuous time systems."
Marco Gori and Klaus Meer
Extended abstract in: Proceedings 3rd Conference on Computability in Europe 2007: Computation and Logic in the Real World, Siena, Italy, 2007, Lecture Notes in Computer Science 4497, 554-565, 2007.

"On the OBDD size for graphs of bounded tree- and clique-width."
Klaus Meer and Dieter Rautenbach
Extended abstract in: Proceedings 2nd International Workshop on Parameterized and Exact Computation, Zürich, Switzerland, 2006, Lecture Notes in Computer Science 4169, 72-83, 2006.

"Approximation classes for real number optimization problems."
Uffe Flarup and Klaus Meer
Extended Abstract in: Proceedings 5th International Conference on Unconventional Computation, York, United Kingdom, 2006, Lecture Notes in Computer Science 4135, 86-100, 2006.

"Uncomputability below the real Halting Problem."
Klaus Meer and Martin Ziegler
Extended Abstract in: Proc. 2nd Conference on Computability in Europe 2006: New Computational Paradigms, Swansea, Lecture Notes in Computer Science 3988, 368-377, 2006.

"Optimization and approximation problems related to polynomial system solving."
Klaus Meer
Invited paper in: Proc. 2nd Conference on Computability in Europe 2006: New Computational Paradigms, Swansea, Lecture Notes in Computer Science 3988, 360-367, 2006.

"On the approximation of interval functions."
Klaus Meer
Extended Abstract in: Applied Parallel Computing. State-of-the-Art in Scientific Computing PARA 04, Lyngby, Denmark, 2004, Lecture Notes in Computer Science 3732, 169-178, 2006.

"Two logical hierarchies of optimization problems over the real numbers."
Uffe Flarup and Klaus Meer
Extended Abstract in: Proceedings 30th International Symposium on Mathematical Foundations of Computer Science MFCS, Gdansk, Poland, 2005, Lecture Notes in Computer Science 3618, 459-470, 2005.

"An explicit solution to Post's problem over the reals."
Klaus Meer and Martin Ziegler
Extended Abstract in: Proceedings 15th International Symposium on Fundamentals of Computation Theory FCT, Lübeck, Germany, 2005 Lecture Notes in Computer Science 3623, 456-467, 2005.

"On some relations between approximation and PCPs over the real numbers."
Klaus Meer
Extended Abstract in: Proc. Computability in Europe 2005: New Computational Paradigms, Amsterdam, The Netherlands, 2005 Lecture Notes in Computer Science 3526, 322-331, 2005.

"Computing Multi-homogeneous B\'ezout numbers is hard."
Gregorio Malajovich and Klaus Meer
Extended Abstract in: Proceedings 22nd Symposium on Theoretical Aspects of Computer Science STACS, Stuttgart, Germany, 2005 Lecture Notes in Computer Science vol. 3404, 244-255, 2005.

"Transparent long proofs: A first PCP theorem for NP_{\R}."
Klaus Meer
Extended Abstract in: 31st International Colloquium on Automata, Languages and Programming ICALP, Turku, Finland, 2004 Lecture Notes in Computer Science. Volume 3142 , 959-970, 2004.

"On the complexity of some problems in interval arithmetic."
Klaus Meer
Extended abstract in: Proc. 28th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 2003 Springer Lecture Notes in Computer Science Volume 2747 , 582-591, 2003.

"On consistency and width notions for constraint programs with algebraic constraints."
Klaus Meer
Extended abstract in: Proc. of Sixth International Symposium on Functional and Logic Programming 2002, Aizu, Japan, 2002 Springer Lecture Notes in Computer Science 2441, 88-102, 2002.

"Maßsynthese vier- sechs- und achtgliedriger ebener Kurbelgetriebe und ihre Anwendung im Kfz-Karosseriebau."
Klaus Meer and Harold Schreiber
In: Verein Deutscher Ingenieure VDI (ed.): Kurvengetriebe, Koppelgetriebe, gesteuerte Antriebe: Problemlösungen in der Bewegungstechnik; Conference Veitshöchheim 26. and 27. September 2000, VDI-Getriebetagung 2000. VDI-Gesellschaft Entwicklung, Konstruktion, Vertrieb. Düsseldorf: VDI-Verlag (VDI-Berichte 1567; ISBN 3-18-091567-6), 277-297, 2000.

"On the complexity of combinatorial and metafinite generating functions."
J.A. Makowsky and Klaus Meer
Extended abstract in: Proc. of Computer Science Logic CSL 2000, Fischbachau, Germany, 2000 Springer Lecture Notes in Computer Science 1862, 399-410, 2000.

"Polynomials of bounded tree-width."
J.A. Makowsky and Klaus Meer
Extended abstract in: Formal Power Series and Algebraic Combinatorics, Proceedings of the 12th International Conference, FPSAC'00, Moscow, Russia, 2000, D. Krob, A.A. Mikhalev and A.V. Mikhalev eds., Springer, 692-703, 2000.

"Query languages for real number databases based on descriptive complexity over R."
Klaus Meer
Extended Abstract in: Proc. 24th International Symposium on Mathematical Foundations of Computer Science MFCS <\br> Szklarska Poreba, Poland, 1999, Lecture Notes in Computer Science Volume 1672, Springer, 12-22, 1999. A preprint version can be downloaded here

"Counting problems over the reals."
Klaus Meer
Extended Abstract in: Proc. 22nd International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 1997, Lecture Notes in Computer Science, Volume 1295, Springer, 398-407, 1997

"Logics which capture complexity classes over the reals."
Felipe Cucker and Klaus Meer
Extended Abstract in: Proc. 11th International Symposium on Fundamentals of Computation Theory FCT, Krakow, Poland, 1997 Lecture Notes in Computer Science , Volume 1279, Springer, 157-168, 1997.

"On diagonal sets in uncountable structures."
Klaus Meer
In: Proceedings 2. Workshop ``Computability and complexity in Analysis" , Trier 1996, Ed.: K. Weihrauch, Ker-I Ko, N. Müller, Forschungsbericht Universität Trier 96-44.

"Descriptive Complexity Theory over the real numbers."
Erich Grädel and Klaus Meer
Extended abstract in: Proceedings of the 27th Symposium on Theory of Computing STOC, Las Vegas, 315-324, 1995.

Miscellaneous

"Fragestellungen aus Mathematik und theoretischer Informatik bei der Konstruktion von Getrieben"
Klaus Meer
Forum der Forschung, BTU Cottbus, 145-150, 2008.

"Real Computation and Complexity"
T. Lickteig, K. Meer, L.M. Pardo (eds.), Dagstuhl Seminar Proceedings, Vol. 04061, Schloss Dagstuhl, Germany, 2006.

"Complexity analysis of a semi-infinite optimization problem in interval arithmetic."
Klaus Meer
Proceedings PARA'04 Workshop on State of the Art in Scientific Computing. J. Dongarraa, K. Madsen, J. Wa\'sniewski (eds.), Technical University Denmark, Lyngby, Vol. 1, 100-105, 2004.

"Optimierung" (Optimization).
Hubertus Theodor Jongen and Klaus Meer
In: Faszination Mathematik, ed.: G. Walz, Spektrum Akademischer Verlag, Heidelberg, 211-216, 2003

"Das Simplexverfahren" (The Simplex method).
Hubertus Theodor Jongen and Klaus Meer
Lexikon der Mathematik, ed.: G. Walz, Spektrum Akademischer Verlag, Heidelberg, Vol. 5, 27-30, 2002

"Ellipsoidmethoden" (Ellipsoid methods).
Hubertus Theodor Jongen and Klaus Meer
Lexikon der Mathematik, ed.: G. Walz, Spektrum Akademischer Verlag, Heidelberg, Vol. 2, 37-38, 2001

"Innere-Punkte Methoden" (Interior Point methods).
Hubertus Theodor Jongen and Klaus Meer
Lexikon der Mathematik, ed.: G. Walz, Spektrum Akademischer Verlag, Heidelberg, Vol. 2, 491-494, 2001

"NP-complete and NP-hard problems."
Hubertus Theodor Jongen and Klaus Meer
Encyclopaedia of Mathematics, Supplement II, ed.: M. Hazewinkel, Kluwer Academic Publishers, 362-364, 2000

In addition, H.Th. Jongen and myself contributed to the Lexikon der Mathematik about 200 keywords in the field of optimization.

Book reviews

Review on "Ming-Yang Kao (ed.): Encyclopedia of Algorithms." Springer New York 2016, 3 volumes, 2nd Edition. In: AMS Mathematical Reviews, MR3523863

Review on "A. Syropoulos: Hypercomputation." Springer 2008.
In: AMS Mathematical Reviews, MR2450722 (2009j:68065)

Review on "I. Wegener: Komplexit\"atstheorie." Springer 2003.
Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 108, no. 2, 5-8, 2006.

Review on "L. Blum, F. Cucker, M. Shub and S. Smale: Complexity and Real Computation." Springer 1998.
In: AMS Mathematical Reviews, MR1479636 (99a:68070).

Lecture notes (in german)

Approximationsalgorithmen
Klaus Meer
2010, 78 pages

Algebraische Komplexitätstheorie
Klaus Meer
1999, 91 pages

Lineare und quadratische Programmierung.
Klaus Meer
1998, 120 pages

Diskrete Strukturen
Klaus Meer
1997, 111 pages

Einführung in die reelle Komplexitätstheorie
Klaus Meer
1995, 60 pages

AMS Reviews

Click here to see a list of the reviews I have written for the American Mathematical Society (Math Scinet access required)