Publications by Klaus Meer

Theses

"Quadratic Programming: Complexity Issues in Real Number Models."
Klaus Meer
Habilitation thesis RWTH Aachen, Mathematisch-Naturwissenschaftliche Fakultät;
Verlag Link zu einer externen Seite 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 Link zu einer externen Seite 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:

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

Monography:

Optimization Theory
H.Th. Jongen, K. Meer, Link zu einer externen Seite  E. Triesch.
Link zu einer externen Seite Kluwer Academic Publishers, Springer
June 2004, ISBN 1-4020-8099-9
For a list of contents click Link zu einer externen Seite here

Journals and contributions to books (peer reviewed)

"An algebraic proof of the real number PCP theorem."
Martijn Baartse and Klaus Meer
Link zu einer externen Seite Journal of Complexity, Vol. 40, pp 34--77, 2017. Online version Link zu einer externen Seite here

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

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

"An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents."
Klaus Meer
Link zu einer externen Seite 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: Link zu einer externen Seite 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
Link zu einer externen Seite 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', Link zu einer externen Seite 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, Link zu einer externen Seite Pascal Koiran, and Klaus Meer
Link zu einer externen Seite Discrete Applied Mathematics, Vol. 159 (1), 1-14, 2011.

"Treewidth in algebraic complexity."
Klaus Meer
Link zu einer externen Seite 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
Link zu einer externen Seite 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
Link zu einer externen Seite Discrete Mathematics, Volume 309, Issue 4, 843-851, 2009.

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

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

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

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

"Computing Multi-homogeneous B\'ezout numbers is hard."
Gregorio Malajovich and Klaus Meer
Link zu einer externen Seite 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
Link zu einer externen Seite Mathematical Logic Quarterly, vol. 52 no. 1, 37-50, 2006.

"Transparent long proofs: A first PCP theorem for NP_R."
Klaus Meer
Link zu einer externen Seite 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. Link zu einer externen Seite 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
Link zu einer externen Seite Reliable Computing, Vol. 10, No.3, 209-225, 2004.

"A step towards a complexity theory for analog systems."
Marco Gori and Klaus Meer
Link zu einer externen Seite 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
Link zu einer externen Seite Mechanism and Machine Theory, Vol. 37, Nr. 7, 717-737, 2002.

"Polynomials of bounded tree-width."
J.A. Makowsky and Klaus Meer
Link zu einer externen Seite 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
Link zu einer externen Seite European Journal of Operational Research, Vol. 143, Issue 2, 406-418, 2002.

"Counting problems over the reals."
Klaus Meer
Link zu einer externen Seite 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
Link zu einer externen Seite 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
Link zu einer externen Seite 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
Link zu einer externen Seite 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, Link zu einer externen Seite 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
Link zu einer externen Seite Journal of Complexity, volume 11, issue 3, 344-351, 1995.

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

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

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

"Real number models under various sets of operations."
Klaus Meer
Link zu einer externen Seite 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
Link zu einer externen Seite Journal of Complexity, volume 8, issue 4, 451-453, 1992.

"Computations over Z and R : a comparison."
Klaus Meer
Link zu einer externen Seite 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: Link zu einer externen Seite 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: Link zu einer externen Seite 10.4230/LIPIcs.MFCS.2016.14,URL: Link zu einer externen Seite 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: Link zu einer externen Seite 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 Link zu einer externen Seite 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 Link zu einer externen Seite 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: Link zu einer externen Seite 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: Link zu einer externen Seite 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: Link zu einer externen Seite 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,Link zu einer externen Seite  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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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, Link zu einer externen Seite 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 "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 Link zu einer externen Seite here to see a list of the reviews I have written for the American Mathematical Society (Math Scinet access required)