@misc{Meer, author = {Meer, Klaus}, title = {Complexity aspects of a semi-infinite optimization problem}, series = {Optimization : a Journal of Mathematical Programming and Operations Research}, volume = {57}, journal = {Optimization : a Journal of Mathematical Programming and Operations Research}, number = {1}, issn = {1029-4945}, pages = {143 -- 152}, language = {en} } @misc{MeerRautenbach, author = {Meer, Klaus and Rautenbach, Dieter}, title = {On the OBDD size for graphs of bounded tree- and clique-width}, language = {en} } @misc{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {An explicit solution to Post's problem over the reals}, series = {Journal of Complexity}, volume = {24}, journal = {Journal of Complexity}, number = {1}, issn = {0885-064x}, pages = {3 -- 15}, language = {en} } @inproceedings{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {Real Computational Universality: The word problem for a class of groups with infinite presentation}, series = {Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, Česk{\´y} Krumlov, Czech Republic, August 26-31, 2007, proceedings}, booktitle = {Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, Česk{\´y} Krumlov, Czech Republic, August 26-31, 2007, proceedings}, editor = {Kučera, Luděk}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-74455-9}, pages = {726 -- 737}, language = {en} } @inproceedings{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {Uncomputability below the real halting problem}, series = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings.}, booktitle = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings.}, editor = {Beckmann, Arnold}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-35466-6}, pages = {368 -- 377}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Optimization and approximation problems related to polynominal system solving}, series = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings}, booktitle = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings}, editor = {Beckmann, Arnold}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-35466-6}, pages = {360 -- 367}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On the approximation of interval functions}, language = {en} } @inproceedings{FlarupHansenMeer, author = {Flarup Hansen, Uffe and Meer, Klaus}, title = {Two logical hierarchies of optimization problems over the real numbers}, series = {Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005}, booktitle = {Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005}, editor = {Jedrzejowicz, Joanna}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-29702-5}, pages = {459 -- 470}, language = {en} } @inproceedings{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {An explicit solution to Post's problem over the reals}, series = {Fundamentals of computation theory, 15th international symposium, FCT 2005, L{\"u}beck, Germany, August 17 - 20, 2005}, booktitle = {Fundamentals of computation theory, 15th international symposium, FCT 2005, L{\"u}beck, Germany, August 17 - 20, 2005}, editor = {Liskiewicz, Maciej}, publisher = {Springer}, address = {Berlin}, isbn = {3-540-28193-2}, pages = {456 -- 467}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On some relations between approximation and PCPs over the real numbers}, series = {New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005}, booktitle = {New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005}, editor = {Cooper, Stuart Barry}, publisher = {Springer}, address = {Heidelberg [u.a.]}, isbn = {3-540-26179-6}, pages = {322 -- 331}, language = {en} } @inproceedings{MalajovichMeer, author = {Malajovich, Gregorio and Meer, Klaus}, title = {Computing Minimal Multi-Homogeneous B{\´e}zout Numbers Is Hard}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Simulated Annealing versus Metropolis for a TSP instance}, series = {Information Processing Letters}, volume = {104}, journal = {Information Processing Letters}, number = {6}, issn = {0020-0190}, pages = {216 -- 219}, language = {en} } @misc{MalajovichMeer, author = {Malajovich, Gregorio and Meer, Klaus}, title = {Computing Minimal Multi-Homogeneous B{\´e}zout Numbers Is Hard}, series = {Theory of Computing Systems}, volume = {40}, journal = {Theory of Computing Systems}, number = {4}, issn = {1432-4350}, pages = {553 -- 570}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On some relations between approximation and PCPs over the real numbers}, series = {Theory of Computing Systems}, volume = {41}, journal = {Theory of Computing Systems}, number = {1}, issn = {1432-4350}, pages = {107 -- 118}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Transparent long proofs: A first PCP Theorem for NP(R)}, series = {Foundations of Computational Mathematics}, volume = {5}, journal = {Foundations of Computational Mathematics}, number = {3}, issn = {1615-3375}, pages = {231 -- 255}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Probabilistically checkable proofs over the reals}, series = {Electronic notes in theoretical computer science : ENTCS}, volume = {123}, journal = {Electronic notes in theoretical computer science : ENTCS}, issn = {1571-0661}, pages = {165 -- 177}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On a refined analysis of some problems in interval arithmetic using real number complexity theory}, series = {Reliable Computing}, volume = {10}, journal = {Reliable Computing}, number = {3}, issn = {1385-3139}, pages = {209 -- 225}, language = {en} } @inproceedings{GoriMeer, author = {Gori, Marco and Meer, Klaus}, title = {Some aspects of a complexity theory for continuous time systems}, series = {Extended abstract, Proceedings Computability in Europe, CiE 2007, Siena, Italy, June 18 - 23, 2007}, booktitle = {Extended abstract, Proceedings Computability in Europe, CiE 2007, Siena, Italy, June 18 - 23, 2007}, editor = {Cooper, Stuart Barry}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-73000-2}, pages = {554 -- 565}, language = {en} } @inproceedings{MeerRautenbach, author = {Meer, Klaus and Rautenbach, Dieter}, title = {On the OBDD size for graphs of bounded tree- and clique-width}, series = {Parameterized and exact computation, Second International Workshop, IWPEC 2006, Z{\"u}rich, Switzerland, September 13 - 15, 2006}, booktitle = {Parameterized and exact computation, Second International Workshop, IWPEC 2006, Z{\"u}rich, Switzerland, September 13 - 15, 2006}, editor = {Bodlaender, Hans L.}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-39098-5}, pages = {72 -- 83}, language = {en} } @inproceedings{FlarupHansenMeer, author = {Flarup Hansen, Uffe and Meer, Klaus}, title = {Approximation classes for real number optimization problems}, series = {Extended abstract, 5th International conference on Unconventional Computation, York, UK, September 4-8, 2006}, booktitle = {Extended abstract, 5th International conference on Unconventional Computation, York, UK, September 4-8, 2006}, editor = {Calude, Cristian}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-38593-6}, pages = {86 -- 100}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On Ladner's Result for a Class of Real Machines with Restricted use of Constants}, series = {5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19 - 24, 2009}, booktitle = {5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19 - 24, 2009}, editor = {Ambos-Spies, Klaus}, publisher = {Springer}, address = {Heidelber [u.a.]}, isbn = {978-3-642-03072-7}, pages = {352 -- 361}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Fragestellungen aus Mathematik und theoretischer Informatik bei der Konstruktion von Getrieben}, series = {Forum der Forschung}, volume = {12}, journal = {Forum der Forschung}, number = {21}, issn = {0947-6989}, pages = {145 -- 150}, language = {de} } @misc{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {Real Computational Universality: The word problem for a class of groups with infinite presentation}, language = {en} } @misc{KoiranMeerBriquel, author = {Koiran, Pascal and Meer, Klaus and Briquel, Ir{\´e}n{\´e}e}, title = {On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Treewidth in Algebraic Complexity}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On Ladnerʼs result for a class of real machines with restricted use of constants}, series = {Information and Computation}, volume = {210}, journal = {Information and Computation}, issn = {0890-5401}, pages = {13 -- 20}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Some initial thoughts on bounded query computations over the reals}, series = {International Journal of Foundations of Computer Science}, volume = {23}, journal = {International Journal of Foundations of Computer Science}, number = {7}, issn = {0129-0541}, doi = {10.1142/S0129054112400618}, pages = {1499 -- 1510}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On the complexity of some problems in interval arithmetic}, series = {Proceedings, 28th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 2003}, booktitle = {Proceedings, 28th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 2003}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-40671-9}, pages = {582 -- 591}, language = {en} } @incollection{JongenMeer, author = {Jongen, Hubertus Theodor and Meer, Klaus}, title = {Das Simplexverfahren}, series = {Lexikon der Mathematik, Band 5}, booktitle = {Lexikon der Mathematik, Band 5}, editor = {Walz, Guido}, publisher = {Spektrum Akademischer Verlag}, address = {Heidelberg}, isbn = {3-8274-0437-1}, pages = {27 -- 30}, language = {de} } @incollection{JongenMeer, author = {Jongen, Hubertus Theodor and Meer, Klaus}, title = {Ellipsoidmethoden}, series = {Lexikon der Mathematik, Band 2}, booktitle = {Lexikon der Mathematik, Band 2}, editor = {Walz, Guido}, publisher = {Spektrum Akademischer Verlag}, address = {Heidelberg}, isbn = {3-8274-0434-7}, pages = {37 -- 38}, language = {de} } @incollection{JongenMeer, author = {Jongen, Hubertus Theodor and Meer, Klaus}, title = {Innere-Punkte Methoden}, series = {Lexikon der Mathematik, Band 2}, booktitle = {Lexikon der Mathematik, Band 2}, editor = {Walz, Guido}, publisher = {Spektrum Akademischer Verlag}, address = {Heidelberg}, isbn = {3-8274-0434-7}, pages = {491 -- 494}, language = {de} } @misc{Meer, author = {Meer, Klaus}, title = {An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents}, series = {Theory of Computing Systems}, volume = {55}, journal = {Theory of Computing Systems}, number = {2}, issn = {1432-4350}, pages = {330 -- 346}, language = {en} } @incollection{JongenMeer, author = {Jongen, Hubertus Theodor and Meer, Klaus}, title = {Optimierung}, series = {Faszination Mathematik}, booktitle = {Faszination Mathematik}, editor = {Walz, Guido}, publisher = {Spektrum Akademischer Verlag}, address = {Heidelberg}, isbn = {3-8274-1419-9}, pages = {211 -- 216}, language = {de} } @misc{MeerSchmittSchreiber, author = {Meer, Klaus and Schmitt, Burkhard and Schreiber, Harold}, title = {Dimensional Synthesis of Planar Stephenson-Mechanisms for Motion Generation by Circlepoint Search and Homotopy Methods}, series = {Mechanism and Machine Theory}, volume = {37}, journal = {Mechanism and Machine Theory}, number = {7}, issn = {0094-114X}, doi = {10.1016/S0094-114X(02)00016-2}, pages = {717 -- 737}, abstract = {The kinematic synthesis of Stephenson mechanisms for motion generation is often based on specifying arbitrary values for certain kinematic dimensions. If no appropriate values are known, an inadequate choice can make it impossible to find a good mechanism. In the present paper a synthesis method is described where kinematic dimensions can be chosen a priori (to meet side conditions, e.g., a limited area for the locations of the fixed pivots), but do not have to be chosen. A circlepoint search in combination with homotopy methods will be applied. Concerning the homotopy methods two approaches - via the B{\´e}zout number and the BKK bound - will be compared.}, language = {en} } @misc{MeerWeber, author = {Meer, Klaus and Weber, Gerhard Wilhelm}, title = {Some aspects of studying an optimization or decision problem in different computational models}, series = {European Journal of Operational Research}, volume = {143}, journal = {European Journal of Operational Research}, number = {2}, issn = {0377-2217}, doi = {10.1016/S0377-2217(02)00269-2}, pages = {406 -- 418}, abstract = {In this paper we want to discuss some of the features coming up when analyzing a problem in different complexity theoretic frameworks. The focus will be on two problems. The first is related to mathematical optimization. We consider the quadratic programming problem of minimizing a quadratic polynomial on a polyhedron. We discuss how the complexity of this problem might change if we consider real data together with an algebraic model of computation (the Blum-Shub-Smale model) instead of rational inputs together with the Turing machine model. The results obtained will lead us to the second problem; it deals with the intrinsic structure of complexity classes in models over real- or algebraically closed fields. A classical theorem by Ladner for the Turing model is examined in these different frameworks. Both examples serve well for working out in how far different approaches to the same problem might shed light upon each other. In some cases this will lead to quite diverse results with respect to the different models. On the other hand, for some problems the more general approach can also give a unifying idea why results hold true in several frameworks. The paper is of tutorial character in that it collects some results into the above direction obtained previously.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Wegener, Ingo: Komplexit{\"a}tstheorie. Berlin : Springer, 2003}, series = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, volume = {108}, journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, number = {2}, issn = {0012-0456}, pages = {5 -- 8}, language = {de} } @misc{MeerNaif, author = {Meer, Klaus and Naif, Ameen}, title = {Generalized finite automata over real and complex numbers}, series = {Theoretical Computer Science}, volume = {Vol. 591}, journal = {Theoretical Computer Science}, issn = {0304-3975}, doi = {10.1016/j.tcs.2015.05.001}, pages = {85 -- 98}, abstract = {In a recent work, Gandhi, Khoussainov, and Liu [7] introduced and studied a generalized model of finite automata able to work over arbitrary structures. As one relevant area of research for this model the authors identify studying such automata over particular structures such as real and algebraically closed fields. In this paper we start investigations into this direction. We prove several structural results about sets accepted by such automata, and analyze decidability as well as complexity of several classical questions about automata in the new framework. Our results show quite a diverse picture when compared to the well known results for finite automata over finite alphabets.}, language = {en} } @misc{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {The PCP theorem for NP over the reals}, series = {Foundations of Computational Mathematics}, volume = {15}, journal = {Foundations of Computational Mathematics}, number = {3}, issn = {1615-3375}, doi = {10.1007/s10208-014-9188-x}, pages = {651 -- 680}, language = {en} } @misc{MeerLickteig, author = {Meer, Klaus and Lickteig, Thomas}, title = {Semi-algebraic complexity - Additive complexity of matrix computational tasks}, series = {Journal of Complexity}, volume = {13}, journal = {Journal of Complexity}, number = {1}, issn = {0885-064X}, doi = {10.1006/jcom.1997.0430}, pages = {83 -- 107}, abstract = {This paper is devoted to the study of lower bounds on the inherent number of additions and subtractions necessary to solve some natural matrix computational tasks such as computing the nullspace, some band transformation, and some triangulation of a givenm×mmatrix. The additive complexities of such tasks are shown to grow asymptotically like that of them×mmatrix multiplication. The paper is a continuation of an earlier paper by the authors, and also of 4where multiplicative complexity has been considered. We also propose a formalization of semialgebraic computational tasks.}, language = {en} } @misc{MeerMalajovich, author = {Meer, Klaus and Malajovich, Gregorio}, title = {On the structure of NP_C}, series = {SIAM Journal on Computing}, volume = {28}, journal = {SIAM Journal on Computing}, number = {1}, issn = {1095-7111}, doi = {10.1137/S0097539795294980}, pages = {27 -- 35}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Query languages for real number databases based on descriptive complexity over R}, series = {Mathematical foundations of computer science 1999, 24th international symposium, MFCS '99, Szklarska Pore̜ba, Poland, September 6 - 10, 1999, proceedings}, booktitle = {Mathematical foundations of computer science 1999, 24th international symposium, MFCS '99, Szklarska Pore̜ba, Poland, September 6 - 10, 1999, proceedings}, editor = {Kutylowski, Miroslaw and Leszek, Pacholski and Wierzbicki, Tomasz}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-66408-6}, doi = {10.1007/3-540-48340-3_2}, pages = {12 -- 22}, abstract = {We propose the study of query languages for databases involving real numbers as data (called real number databases in the sequel). As main new aspect our approach is based on real number complexity theory as introduced in [8] and descriptive complexity for the latter developed in [17]. Using this formal framework a uniform treatment of query languages for such databases is obtained. Precise results about both the data- and the expression-complexity of several such query languages are proved. More explicitly, relying on descriptive complexity theory over ℝ gives the possibility to derive a hierarchy of complete languages for most of the important real number complexity classes. A clear correspondence between different logics and such complexity classes is established. In particular, it is possible to formalize queries involving in a uniform manner real spaces of different dimensions. This can be done in such a way that the logical description exactly reflects the computational complexity of a query. The latter might circumvent a problem appearing in some of the former approaches dealing with semi-algebraic databases (see [20] , [18]), where the use of first-order logic over real-closed fields can imply inefficiency as soon as the dimension of the underlying real space is not fixed - no matter whether the query under consideration is easy to compute or not.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Computations over Z and R : a comparison}, series = {Journal of Complexity}, volume = {6}, journal = {Journal of Complexity}, number = {3}, issn = {0885-064X}, doi = {10.1016/0885-064X(90)90022-6}, pages = {256 -- 263}, abstract = {Regarding real number models of computation may be a helpful way to get deeper insight into the classical theory over Z. Therefore it seems useful to study the complexity of classical problems in the real model. In this connection, the problem of deciding the existence of a nonnegative zero for certain polynomials plays an important part because a lot of NP-problems over Z can be polynomial reduced to it.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {A note on a \$ P \neq NP-\$ result in a restricted class of real machines}, series = {Journal of Complexity}, volume = {8}, journal = {Journal of Complexity}, number = {4}, issn = {0885-064X}, doi = {10.1016/0885-064X(92)90007-X}, pages = {451 -- 453}, abstract = {For a class of real machines using only linear functionals as computations and equality-tests, we show that the classes P and NP differ.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Real number models under various sets of operations}, series = {Journal of Complexity}, volume = {9}, journal = {Journal of Complexity}, number = {3}, issn = {0885-064X}, doi = {10.1006/jcom.1993.1023}, pages = {366 -- 372}, abstract = {The computational model of Blum, Shub, and Smale (1989, Bull. Amer. Math. Soc.21, 1-46) yields a numerous number of different algorithm-classes if the allowed set of instructions is varied. For two such classes we consider the "P = NP?" problem as well as the question of whether the NP- problems are decidable.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Real number models : on the use of information}, series = {Journal of Symbolic Computation}, volume = {18}, journal = {Journal of Symbolic Computation}, number = {3}, issn = {0747-7171}, doi = {10.1006/jsco.1994.1044}, pages = {199 -- 206}, abstract = {When comparing complexity theory over the ring Z (Turing machine) on one hand and over the ring R (Blum-Shub-Smale machine) on the other hand, it will be important to study how methods and ideas of the first can be transformed to the second one. In this sense the present paper is concerned with the relation between a characterization of the P = NP?-question for the Z-case (given by Krentel) and a special class of quadratic-programming problems which are important in the real model.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On the complexity of Quadratic Programming in real number models of computation}, series = {Theoretical Computer Science}, volume = {133}, journal = {Theoretical Computer Science}, number = {1}, issn = {0304-3975}, doi = {10.1016/0304-3975(94)00070-0}, pages = {85 -- 94}, abstract = {The complexity of linearly constrained (nonconvex) quadratic programming is analyzed within the framework of real number models, namely the one of Blum, Shub, and Smale and its modification recently introduced by Koiran ("weak BSS-model"). In particular we show that this problem is not NP-complete in the Koiran setting. Applications to the (full) BSS-model are discussed.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On the relations between discrete and continuous complexity theory}, series = {Mathematical Logic Quarterly}, volume = {41}, journal = {Mathematical Logic Quarterly}, number = {2}, issn = {0885-064X}, doi = {10.1002/malq.19950410214}, pages = {281 -- 286}, abstract = {Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reals is examined based on certain conditions on the discrete setting. Moreover we study the behaviour of exponential time computations over the reals depending on the real complexity of 3-Satisfiability. This will be done using tools from complexity theory over the integers.}, language = {en} } @misc{MeerLickteig, author = {Meer, Klaus and Lickteig, Thomas}, title = {A note on testing the resultant}, series = {Journal of Complexity}, volume = {11}, journal = {Journal of Complexity}, number = {3}, issn = {0885-064X}, doi = {10.1006/jcom.1995.1016}, pages = {344 -- 351}, abstract = {Shub (in "From Topology to Computation: Proceedings of the Smalefest." (M. Hirsch, J. Marsden, and M. Shub, Eds.), pp. 281-301, Springer-Verlag, New York/Berlin, 1993) proposes to attack the complex PFull-size image (<1 K) versus the NPFull-size image (<1 K) problem by focussing on lower bounds on testing the resultant of quadratic forms for zero. Taking up this question we show in the present paper a lower bound of order n3 for the resultant.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Counting problems over the reals.}, series = {Theoretical Computer Science}, volume = {242}, journal = {Theoretical Computer Science}, number = {1-2}, issn = {0304-397}, pages = {41 -- 58}, language = {en} } @misc{BenDavidMeerMichaux, author = {Ben-David, Shai and Meer, Klaus and Michaux, Christian}, title = {A note on non-complete problems in NP_R.}, series = {Journal of Complexity}, volume = {16}, journal = {Journal of Complexity}, number = {1}, issn = {0885-064X}, pages = {324 -- 332}, language = {en} } @misc{GoriMeer, author = {Gori, Marco and Meer, Klaus}, title = {A step towards a complexity theory for analog systems.}, series = {Mathematical Logic Quarterly}, volume = {48}, journal = {Mathematical Logic Quarterly}, number = {Suppl. 1}, issn = {0942-5616}, pages = {45 -- 58}, language = {en} } @incollection{MakowskyMeer, author = {Makowsky, Janos A. and Meer, Klaus}, title = {Polynomials of bounded treewidth}, series = {Foundations of Computational Mathematics, Proceedings of the Smalefest 2000}, booktitle = {Foundations of Computational Mathematics, Proceedings of the Smalefest 2000}, editor = {Cucker, Felipe and Rojas, Maurice}, publisher = {World Scientific}, address = {Singapore}, isbn = {978-981-02-4845-1}, pages = {211 -- 250}, language = {en} } @misc{MatamalaMeer, author = {Matamala, Martin and Meer, Klaus}, title = {On the computational structure of the connected components of difficult sets}, series = {Information Processing Letters}, volume = {72}, journal = {Information Processing Letters}, number = {3-4}, issn = {0020-0190}, pages = {83 -- 90}, language = {en} } @misc{CuckerMeer, author = {Cucker, Felipe and Meer, Klaus}, title = {Logics which capture complexity classes over the reals}, series = {Journal of Symbolic Logic}, volume = {64}, journal = {Journal of Symbolic Logic}, number = {1}, issn = {0022-4812}, pages = {363 -- 390}, language = {en} } @misc{BenningElkoushyMeer, author = {Benning, Wilhelm and Elkoushy, Ashraf and Meer, Klaus}, title = {Innere-Punkt Methoden f{\"u}r die automatisierte Fehlersuche in geod{\"a}tischen Anwendungen (Interior point methods for automatic blunders detection in surveying)}, series = {Allgemeine Vermessungsnachrichten}, volume = {104}, journal = {Allgemeine Vermessungsnachrichten}, number = {8-9}, issn = {0002-5968}, pages = {319 -- 324}, language = {de} } @misc{MeerMichaux, author = {Meer, Klaus and Michaux, Christian}, title = {A Survey on Real Structural Complexity Theory}, series = {Bulletin of the Belgian Mathematical Society Simon Stevin}, volume = {4}, journal = {Bulletin of the Belgian Mathematical Society Simon Stevin}, number = {1}, issn = {1370-1444}, pages = {113 -- 148}, language = {en} } @misc{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {An algebraic proof of the real number PCP theorem}, series = {Journal of Complexity}, volume = {40}, journal = {Journal of Complexity}, issn = {0885-064X}, doi = {10.1016/j.jco.2016.11.006}, pages = {34 -- 77}, abstract = {The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale (Baartse and Meer, 2015). The proof given there structurally closely follows the proof of the original PCP theorem by Dinur (2007). In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora et al. (Arora et al., 1998; Arora and Safra, 1998) in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition. We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result as the PCP theorem in different computational models.}, language = {en} } @misc{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {Interactive proofs and a Shamir-like result for real number computations}, series = {Computational Complexity}, journal = {Computational Complexity}, issn = {1016-3328}, doi = {10.1007/s00037-018-0174-6}, pages = {33}, language = {en} } @inproceedings{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {Real Interactive Proofs for VPSPACE}, series = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik GmbH}, address = {Wadern}, isbn = {978-3-95977-016-3}, doi = {10.4230/LIPIcs.MFCS.2016.14}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-64300}, pages = {14.1 -- 14.13}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {Some results on interactive proofs for real computations}, series = {Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings}, booktitle = {Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings}, editor = {Beckmann, Arnold and Mitrana, Victor and Soskova, Mariya}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-20027-9}, doi = {10.1007/978-3-319-20028-6}, pages = {107 -- 116}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {Testing Low Degree Trigonometric Polynomials}, series = {Computer Science - Theory and Applications 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014, Proceedings}, booktitle = {Computer Science - Theory and Applications 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014, Proceedings}, editor = {Hirsch, Edward and Kuznetsov, Sergei O. and Pin, Jean-{\´E}ric and Vereshchagin, Nikolay}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-06685-1}, doi = {10.1007/978-3-319-06686-8}, pages = {77 -- 96}, language = {en} } @inproceedings{MeerNaif, author = {Meer, Klaus and Naif, Ameen}, title = {Generalized Finite Automata over Real and Complex Numbers}, series = {Theory and Applications of Models of Computation 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014, Proceedings}, booktitle = {Theory and Applications of Models of Computation 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014, Proceedings}, editor = {Gopal, T. V. and Agrawal, Manindra and Li, Angsheng and Cooper, Stuart Barry}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-06088-0}, doi = {10.1007/978-3-319-06089-7}, pages = {168 -- 187}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {An algebraic proof of the real number PCP theorem}, series = {Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II}, booktitle = {Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II}, publisher = {Springer-Verlag}, address = {Berlin [u.a.]}, isbn = {978-3-662-48053-3}, doi = {10.1007/978-3-662-48054-0}, pages = {50 -- 61}, language = {en} } @inproceedings{MakowskyMeer, author = {Makowsky, Janos A. and Meer, Klaus}, title = {On the complexity of combinatorial and metafinite generating functions}, series = {Computer science logic, 14th international workshop, proceedings, CSL 2000, Fischbachau, Germany, August 21 - 26, 2000}, booktitle = {Computer science logic, 14th international workshop, proceedings, CSL 2000, Fischbachau, Germany, August 21 - 26, 2000}, editor = {Clote, Peter and Schwichtenberg, Helmut}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-67895-6}, pages = {399 -- 410}, language = {en} } @inproceedings{MakowskyMeer, author = {Makowsky, Janos A. and Meer, Klaus}, title = {Polynomials of bounded tree-width}, series = {Formal Power Series and Algebraic Combinatorics, Proceedings of the 12th International Conference, FPSAC'00, Moscow, Russia, June 2000}, booktitle = {Formal Power Series and Algebraic Combinatorics, Proceedings of the 12th International Conference, FPSAC'00, Moscow, Russia, June 2000}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-67247-8}, pages = {692 -- 703}, language = {en} } @inproceedings{MeerNaif, author = {Meer, Klaus and Naif, Ameen}, title = {Periodic Generalized Automata over the Reals}, series = {Language and Automata Theory and Applications 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings}, booktitle = {Language and Automata Theory and Applications 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings}, editor = {Dediu, Adrian-Horia and Janoušek, Jan and Mart{\´i}n-Vide, Carlos and Truthe, Bianca}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-29999-0}, doi = {10.1007/978-3-319-30000-9}, pages = {168 -- 180}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {Topics in Real and Complex Number Complexity Theory}, series = {Recent Advances in Real Complexity and Computation}, booktitle = {Recent Advances in Real Complexity and Computation}, editor = {Monta{\~n}a, Jos{\´e} Luis and Pardo, Luis Miguel}, publisher = {American Mathematical Society}, address = {Providence, RI}, isbn = {978-0-8218-9150-6}, doi = {10.1090/conm/604}, pages = {1 -- 53}, language = {en} } @inproceedings{CuckerMeer, author = {Cucker, Felipe and Meer, Klaus}, title = {Logics which capture complexity classes over the reals}, series = {Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS '97 Bratislava, Slovakia, August 25-29, 1997 Proceedings}, booktitle = {Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS '97 Bratislava, Slovakia, August 25-29, 1997 Proceedings}, publisher = {Springer}, address = {Heidelberg}, pages = {398 -- 407}, language = {en} } @inproceedings{GraedelMeer, author = {Gr{\"a}del, Erich and Meer, Klaus}, title = {Descriptive Complexity Theory over the real numbers}, series = {Proceedings of the 27th Annual ACM Symposium on Theory of Computing STOC, Las Vegas, 1995}, booktitle = {Proceedings of the 27th Annual ACM Symposium on Theory of Computing STOC, Las Vegas, 1995}, publisher = {ACM}, address = {New York, NY}, doi = {10.1145/225058.225151}, pages = {315 -- 324}, language = {en} } @inproceedings{MeerSchreiber, author = {Meer, Klaus and Schreiber, Harold}, title = {Maßsynthese vier- sechs- und achtgliedriger ebener Kurbelgetriebe und ihre Anwendung im Kfz-Karosseriebau}, series = {Kurvengetriebe, Koppelgetriebe, gesteuerte Antriebe, Probleml{\"o}sungen in der Bewegungstechnik, Conference Veitsh{\"o}chheim 26. and 27. September 2000, VDI-Getriebetagung 2000}, booktitle = {Kurvengetriebe, Koppelgetriebe, gesteuerte Antriebe, Probleml{\"o}sungen in der Bewegungstechnik, Conference Veitsh{\"o}chheim 26. and 27. September 2000, VDI-Getriebetagung 2000}, publisher = {VDI Verlag}, address = {D{\"u}sseldorf}, isbn = {3-18-091567-6}, pages = {277 -- 297}, language = {de} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On consistency and width notions for constraint programs with algebraic constraints}, series = {Functional and logic programming, 6th international symposium, proceedings, FLOPS 2002, Aizu, Japan, September 15 - 17, 2002}, booktitle = {Functional and logic programming, 6th international symposium, proceedings, FLOPS 2002, Aizu, Japan, September 15 - 17, 2002}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-44233-2}, pages = {88 -- 102}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Counting problems over the reals}, series = {Mathematical foundations of computer science 1997, 22nd international symposium, proceedings, MFCS '97, Bratislava, Slovakia, August 25 - 29, 1997}, booktitle = {Mathematical foundations of computer science 1997, 22nd international symposium, proceedings, MFCS '97, Bratislava, Slovakia, August 25 - 29, 1997}, editor = {Pr{\´i}vara, Igor and Ružička, Peter}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-63437-9}, doi = {10.1007/BFb0029983}, pages = {398 -- 407}, abstract = {In this paper we introduce a complexity theoretic notion of counting problems over the real numbers. We follow the approaches of Blum, Shub, and Smale.}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On the Approximation of Interval Functions}, series = {Applied Parallel Computing. State of the Art in Scientific Computing, 7th International Workshop, PARA 2004, Lyngby, Denmark, June 20-23, 2004, Revised Selected Papers}, booktitle = {Applied Parallel Computing. State of the Art in Scientific Computing, 7th International Workshop, PARA 2004, Lyngby, Denmark, June 20-23, 2004, Revised Selected Papers}, editor = {Dongarra, Jack}, publisher = {Springer}, address = {Heidelberg [u.a.]}, isbn = {978-3-540-29067-4}, pages = {169 -- 178}, language = {en} } @inproceedings{LickteigMeerPardo, author = {Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel}, title = {Real Computation and Complexity, Dagstuhl seminar}, publisher = {Internationale Begegnungs- und Forschungszentrum f{\"u}r Informatik}, address = {Dagstuhl}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-4994}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {The PCP theorem for NP over the reals}, series = {30th Symposium on Theoretical Aspects of Computer Science STACS , Kiel, 2013}, booktitle = {30th Symposium on Theoretical Aspects of Computer Science STACS , Kiel, 2013}, address = {Leibnitz}, doi = {10.4230/LIPIcs.STACS.2013.104}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-39262}, pages = {104 -- 115}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Almost transparent short proof for NP?}, series = {Extended abstract, Proceedings 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, 2011}, booktitle = {Extended abstract, Proceedings 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, 2011}, isbn = {978-3-642-22952-7}, pages = {41 -- 52}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents}, language = {en} } @inproceedings{KoiranMeer, author = {Koiran, Pascal and Meer, Klaus}, title = {On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width}, series = {Graph-theoretic concepts in computer science, 34th international workshop, WG 2008, Durham, UK, June 30-July 2, 2008}, booktitle = {Graph-theoretic concepts in computer science, 34th international workshop, WG 2008, Durham, UK, June 30-July 2, 2008}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-92247-6}, pages = {252 -- 263}, language = {en} } @misc{FlarupHansenMeer, author = {Flarup Hansen, Uffe and Meer, Klaus}, title = {Two logical hierarchies of optimization problems over the real numbers}, series = {Mathematical Logic Quaterly}, volume = {52}, journal = {Mathematical Logic Quaterly}, number = {1}, issn = {0942-5616}, pages = {37 -- 50}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Transparent long proofs: A first PCP theorem for NP(R)}, series = {Extended Abstract in 31st International Colloquium on Automata, Languages and Programming ICALP 2004, Turku}, booktitle = {Extended Abstract in 31st International Colloquium on Automata, Languages and Programming ICALP 2004, Turku}, publisher = {Springer}, address = {Berlin}, isbn = {3-540-22849-7}, pages = {959 -- 970}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Syropoulos, Apostolos: Hypercomputation. Berlin : Springer, 2008}, series = {AMS Mathematical Reviews}, journal = {AMS Mathematical Reviews}, number = {2009j}, issn = {0025-5629}, language = {en} } @book{JongenMeerTriesch, author = {Jongen, Hubertus Theodor and Meer, Klaus and Triesch, Eberhard}, title = {Optimization Theory}, publisher = {Kluwer}, address = {Boston}, isbn = {978-1-402-08098-2}, pages = {XI, 443}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Blum, Lenore [u.a.]: Complexity and real computation. Berlin : Springer, 1998}, series = {AMS Mathematical Reviews}, journal = {AMS Mathematical Reviews}, number = {99a}, issn = {0025-5629}, pages = {509 -- 600}, language = {en} }