Publications by K.
Meer
If you are interested in getting reprints of any of my publications please send me an email.
"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.
Optimization Theory
H.Th. Jongen,
K. Meer,
E. Triesch.
Kluwer Academic Publishers, Springer
June 2004, ISBN 1-4020-8099-9
For a list of contents click here
"Treewidth in algebraic complexity."
Klaus Meer
To appear in: Fundamenta Informaticae.
"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 9, 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.
Online version
"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.
Download
(access to Science Direct required).
"A Survey on Real Structural
Complexity Theory."
Klaus Meer and Christian Michaux
Bulletin of
the Belgian Mathematical Society Simon Stevin 4, 113-148, 1997.
Download (pdf)
"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
11, 344-351, 1995.
Download (access to Science Direct required).
"On the relations between discrete and continuous complexity
theory."
Klaus Meer
Mathematical Logic Quarterly, Heft 2, 41, 281-286, 1995.
"On the complexity of Quadratic Programming in real number models
of computation."
Klaus Meer
Theoretical Computer Science 133, 85-94, 1994.
"Real number models : on the use of information."
Klaus Meer
Journal of Symbolic Computation
vol. 18, 199-206, 1994.
Download
(access to Science Direct required).
"Real number models under various sets of operations."
Klaus Meer
Journal
of Complexity 9, 366-372, 1993.
Download
(access to Science Direct required).
"A note on a $ P \neq NP-$ result in a restricted class of real
machines."
Klaus Meer
Journal of Complexity 8, 451-453,
1992.
"Computations over Z and R : a comparison."
Klaus Meer
Journal of
Complexity 6, 256-263, 1990.
"On Ladner's result for a class of real
machines with restricted use of constants"
Klaus Meer
Extended Abstract to appear 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 to appear 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.
"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.
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).
Einführung
in die reelle Komplexitätstheorie
Klaus Meer
1995, 60 pages
Diskrete
Strukturen
Klaus Meer
1997, 111 pages
"Lineare und quadratische Programmierung."
Klaus Meer
1998, 120 pages
Algebraische Komplexitästheorie
Klaus Meer
1999, 91 pages
Click here
to see a list of the reviews I have written for the American Mathematical Society (Math Scinet access required)
BTU HOME |
Institute of Computer Science |
Chair of Theoretical Computer Science |
Previous Page
Klaus Meer <meer
at informatik.tu-cottbus.de>
Last modified: 18.11.2009