TY - GEN A1 - Meer, Klaus T1 - Complexity aspects of a semi-infinite optimization problem T2 - Optimization : a Journal of Mathematical Programming and Operations Research Y1 - 2008 SN - 1029-4945 SN - 0233-1934 VL - 57 IS - 1 SP - 143 EP - 152 ER - TY - GEN A1 - Meer, Klaus A1 - Rautenbach, Dieter T1 - On the OBDD size for graphs of bounded tree- and clique-width Y1 - 2009 ER - TY - GEN A1 - Meer, Klaus A1 - Ziegler, Martin T1 - An explicit solution to Post's problem over the reals T2 - Journal of Complexity Y1 - 2008 SN - 0885-064x VL - 24 IS - 1 SP - 3 EP - 15 ER - TY - CHAP A1 - Meer, Klaus A1 - Ziegler, Martin ED - Kučera, Luděk T1 - Real Computational Universality: The word problem for a class of groups with infinite presentation T2 - Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, Český Krumlov, Czech Republic, August 26-31, 2007, proceedings Y1 - 2007 SN - 978-3-540-74455-9 SP - 726 EP - 737 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Ziegler, Martin ED - Beckmann, Arnold T1 - Uncomputability below the real halting problem T2 - Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings. Y1 - 2006 SN - 978-3-540-35466-6 SP - 368 EP - 377 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus ED - Beckmann, Arnold T1 - Optimization and approximation problems related to polynominal system solving T2 - Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings Y1 - 2006 SN - 978-3-540-35466-6 SP - 360 EP - 367 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus T1 - On the approximation of interval functions Y1 - 2006 ER - TY - CHAP A1 - Flarup Hansen, Uffe A1 - Meer, Klaus ED - Jedrzejowicz, Joanna T1 - Two logical hierarchies of optimization problems over the real numbers T2 - Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005 Y1 - 2005 SN - 978-3-540-29702-5 SP - 459 EP - 470 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus A1 - Ziegler, Martin ED - Liskiewicz, Maciej T1 - An explicit solution to Post's problem over the reals T2 - Fundamentals of computation theory, 15th international symposium, FCT 2005, Lübeck, Germany, August 17 - 20, 2005 Y1 - 2005 SN - 3-540-28193-2 SP - 456 EP - 467 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus ED - Cooper, Stuart Barry T1 - On some relations between approximation and PCPs over the real numbers T2 - New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005 Y1 - 2005 SN - 3-540-26179-6 SP - 322 EP - 331 PB - Springer CY - Heidelberg [u.a.] ER - TY - CHAP A1 - Malajovich, Gregorio A1 - Meer, Klaus T1 - Computing Minimal Multi-Homogeneous Bézout Numbers Is Hard Y1 - 2005 ER - TY - GEN A1 - Meer, Klaus T1 - Simulated Annealing versus Metropolis for a TSP instance T2 - Information Processing Letters Y1 - 2007 SN - 0020-0190 VL - 104 IS - 6 SP - 216 EP - 219 ER - TY - GEN A1 - Malajovich, Gregorio A1 - Meer, Klaus T1 - Computing Minimal Multi-Homogeneous Bézout Numbers Is Hard T2 - Theory of Computing Systems Y1 - 2007 SN - 1432-4350 VL - 40 IS - 4 SP - 553 EP - 570 ER - TY - GEN A1 - Meer, Klaus T1 - On some relations between approximation and PCPs over the real numbers T2 - Theory of Computing Systems Y1 - 2007 SN - 1432-4350 VL - 41 IS - 1 SP - 107 EP - 118 ER - TY - GEN A1 - Meer, Klaus T1 - Transparent long proofs: A first PCP Theorem for NP(R) T2 - Foundations of Computational Mathematics Y1 - 2005 SN - 1615-3375 VL - 5 IS - 3 SP - 231 EP - 255 ER - TY - GEN A1 - Meer, Klaus T1 - Probabilistically checkable proofs over the reals T2 - Electronic notes in theoretical computer science : ENTCS Y1 - 2005 SN - 1571-0661 VL - 123 SP - 165 EP - 177 ER - TY - GEN A1 - Meer, Klaus T1 - On a refined analysis of some problems in interval arithmetic using real number complexity theory T2 - Reliable Computing Y1 - 2004 SN - 1385-3139 VL - 10 IS - 3 SP - 209 EP - 225 ER - TY - CHAP A1 - Gori, Marco A1 - Meer, Klaus ED - Cooper, Stuart Barry T1 - Some aspects of a complexity theory for continuous time systems T2 - Extended abstract, Proceedings Computability in Europe, CiE 2007, Siena, Italy, June 18 - 23, 2007 Y1 - 2007 SN - 978-3-540-73000-2 SP - 554 EP - 565 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus A1 - Rautenbach, Dieter ED - Bodlaender, Hans L. T1 - On the OBDD size for graphs of bounded tree- and clique-width T2 - Parameterized and exact computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13 - 15, 2006 Y1 - 2006 SN - 978-3-540-39098-5 SP - 72 EP - 83 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Flarup Hansen, Uffe A1 - Meer, Klaus ED - Calude, Cristian T1 - Approximation classes for real number optimization problems T2 - Extended abstract, 5th International conference on Unconventional Computation, York, UK, September 4-8, 2006 Y1 - 2006 SN - 978-3-540-38593-6 SP - 86 EP - 100 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus ED - Ambos-Spies, Klaus T1 - On Ladner's Result for a Class of Real Machines with Restricted use of Constants T2 - 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19 - 24, 2009 Y1 - 2009 SN - 978-3-642-03072-7 SP - 352 EP - 361 PB - Springer CY - Heidelber [u.a.] ER - TY - GEN A1 - Meer, Klaus T1 - Fragestellungen aus Mathematik und theoretischer Informatik bei der Konstruktion von Getrieben T2 - Forum der Forschung Y1 - 2008 SN - 0947-6989 VL - 12 IS - 21 SP - 145 EP - 150 ER - TY - GEN A1 - Meer, Klaus A1 - Ziegler, Martin T1 - Real Computational Universality: The word problem for a class of groups with infinite presentation Y1 - 2009 ER - TY - GEN A1 - Koiran, Pascal A1 - Meer, Klaus A1 - Briquel, Irénée T1 - On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width Y1 - 2011 ER - TY - GEN A1 - Meer, Klaus T1 - Treewidth in Algebraic Complexity Y1 - 2010 ER - TY - GEN A1 - Meer, Klaus T1 - On Ladnerʼs result for a class of real machines with restricted use of constants T2 - Information and Computation Y1 - 2012 UR - http://www.sciencedirect.com/science/article/pii/S0890540111001507# SN - 0890-5401 VL - 210 SP - 13 EP - 20 ER - TY - GEN A1 - Meer, Klaus T1 - Some initial thoughts on bounded query computations over the reals T2 - International Journal of Foundations of Computer Science Y1 - 2012 U6 - https://doi.org/10.1142/S0129054112400618 SN - 0129-0541 N1 - Special Issue on 'Frontier between Decidability and Undecidability and Related Problem' VL - 23 IS - 7 SP - 1499 EP - 1510 ER - TY - CHAP A1 - Meer, Klaus T1 - On the complexity of some problems in interval arithmetic T2 - Proceedings, 28th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 2003 Y1 - 2003 SN - 3-540-40671-9 SP - 582 EP - 591 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Das Simplexverfahren T2 - Lexikon der Mathematik, Band 5 Y1 - 2002 SN - 3-8274-0437-1 SP - 27 EP - 30 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Ellipsoidmethoden T2 - Lexikon der Mathematik, Band 2 Y1 - 2001 SN - 3-8274-0434-7 SP - 37 EP - 38 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Innere-Punkte Methoden T2 - Lexikon der Mathematik, Band 2 Y1 - 2001 SN - 3-8274-0434-7 SP - 491 EP - 494 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - GEN A1 - Meer, Klaus T1 - An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents T2 - Theory of Computing Systems Y1 - 2014 SN - 1432-4350 VL - 55 IS - 2 SP - 330 EP - 346 ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Optimierung T2 - Faszination Mathematik Y1 - 2003 SN - 3-8274-1419-9 SP - 211 EP - 216 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - GEN A1 - Meer, Klaus A1 - Schmitt, Burkhard A1 - Schreiber, Harold T1 - Dimensional Synthesis of Planar Stephenson-Mechanisms for Motion Generation by Circlepoint Search and Homotopy Methods T2 - Mechanism and Machine Theory N2 - 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ézout number and the BKK bound – will be compared. Y1 - 2002 UR - http://www.sciencedirect.com/science/article/pii/S0094114X02000162 U6 - https://doi.org/10.1016/S0094-114X(02)00016-2 SN - 0094-114X VL - 37 IS - 7 SP - 717 EP - 737 ER - TY - GEN A1 - Meer, Klaus A1 - Weber, Gerhard Wilhelm T1 - Some aspects of studying an optimization or decision problem in different computational models T2 - European Journal of Operational Research N2 - 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. KW - Complexity theory Saturation KW - Algebraic models of computation KW - Linear and quadratic programming KW - Structure of complexity classes Y1 - 2002 UR - http://www.sciencedirect.com/science/article/pii/S0377221702002692 U6 - https://doi.org/10.1016/S0377-2217(02)00269-2 SN - 0377-2217 VL - 143 IS - 2 SP - 406 EP - 418 ER - TY - JOUR A1 - Meer, Klaus T1 - Wegener, Ingo: Komplexitätstheorie. Berlin : Springer, 2003 JF - Jahresbericht der Deutschen Mathematiker-Vereinigung Y1 - 2006 SN - 0012-0456 VL - 108 IS - 2 SP - 5 EP - 8 ER - TY - GEN A1 - Meer, Klaus A1 - Naif, Ameen T1 - Generalized finite automata over real and complex numbers T2 - Theoretical Computer Science N2 - 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. KW - Generalized finite automata KW - Real and complex number computations KW - Decision problems for automata over uncountable structures Y1 - 2015 UR - http://www.sciencedirect.com/science/article/pii/S0304397515003928 U6 - https://doi.org/10.1016/j.tcs.2015.05.001 SN - 0304-3975 VL - Vol. 591 SP - 85 EP - 98 ER - TY - GEN A1 - Meer, Klaus A1 - Baartse, Martijn T1 - The PCP theorem for NP over the reals T2 - Foundations of Computational Mathematics KW - Probabilistically checkable proofs Real and complex number computations PCP theorem Hilbert Nullstellensatz decision problem Y1 - 2015 UR - http://link.springer.com/article/10.1007/s10208-014-9188-x?sa_campaign=email/event/articleAuthor/onlineFirst U6 - https://doi.org/10.1007/s10208-014-9188-x SN - 1615-3375 VL - 15 IS - 3 SP - 651 EP - 680 ER - TY - GEN A1 - Meer, Klaus A1 - Lickteig, Thomas T1 - Semi-algebraic complexity - Additive complexity of matrix computational tasks T2 - Journal of Complexity N2 - 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. Y1 - 1997 UR - http://www.sciencedirect.com/science/article/pii/S0885064X97904301 U6 - https://doi.org/10.1006/jcom.1997.0430 SN - 0885-064X VL - 13 IS - 1 SP - 83 EP - 107 ER - TY - GEN A1 - Meer, Klaus A1 - Malajovich, Gregorio T1 - On the structure of NP_C T2 - SIAM Journal on Computing KW - complexity KW - NP-completeness KW - BSS machines over C KW - Hilbert Nullstellensatz Y1 - 1999 UR - http://epubs.siam.org/action/showAbstract?page=27&volume=28&issue=1&journalCode=smjcat& U6 - https://doi.org/10.1137/S0097539795294980 SN - 1095-7111 VL - 28 IS - 1 SP - 27 EP - 35 ER - TY - CHAP A1 - Meer, Klaus ED - Kutylowski, Miroslaw ED - Leszek, Pacholski ED - Wierzbicki, Tomasz T1 - Query languages for real number databases based on descriptive complexity over R T2 - Mathematical foundations of computer science 1999, 24th international symposium, MFCS '99, Szklarska Pore̜ba, Poland, September 6 - 10, 1999, proceedings N2 - 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. Y1 - 1999 UR - http://link.springer.com/chapter/10.1007%2F3-540-48340-3_2 SN - 978-3-540-66408-6 U6 - https://doi.org/10.1007/3-540-48340-3_2 SP - 12 EP - 22 PB - Springer CY - Berlin [u.a.] ER - TY - GEN A1 - Meer, Klaus T1 - Computations over Z and R : a comparison T2 - Journal of Complexity N2 - 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. Y1 - 1990 UR - http://www.sciencedirect.com/science/article/pii/0885064X90900226 U6 - https://doi.org/10.1016/0885-064X(90)90022-6 SN - 0885-064X VL - 6 IS - 3 SP - 256 EP - 263 ER - TY - GEN A1 - Meer, Klaus T1 - A note on a $ P \neq NP-$ result in a restricted class of real machines T2 - Journal of Complexity N2 - For a class of real machines using only linear functionals as computations and equality-tests, we show that the classes P and NP differ. Y1 - 1992 UR - http://www.sciencedirect.com/science/article/pii/0885064X9290007X U6 - https://doi.org/10.1016/0885-064X(92)90007-X SN - 0885-064X VL - 8 IS - 4 SP - 451 EP - 453 ER - TY - GEN A1 - Meer, Klaus T1 - Real number models under various sets of operations T2 - Journal of Complexity N2 - 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. Y1 - 1993 UR - http://www.sciencedirect.com/science/article/pii/S0885064X8371023X U6 - https://doi.org/10.1006/jcom.1993.1023 SN - 0885-064X VL - 9 IS - 3 SP - 366 EP - 372 ER - TY - GEN A1 - Meer, Klaus T1 - Real number models : on the use of information T2 - Journal of Symbolic Computation N2 - 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. Y1 - 1994 UR - http://www.sciencedirect.com/science/article/pii/S0747717184710443 U6 - https://doi.org/10.1006/jsco.1994.1044 SN - 0747-7171 VL - 18 IS - 3 SP - 199 EP - 206 ER - TY - GEN A1 - Meer, Klaus T1 - On the complexity of Quadratic Programming in real number models of computation T2 - Theoretical Computer Science N2 - 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. Y1 - 1994 UR - http://www.sciencedirect.com/science/article/pii/0304397594000700 U6 - https://doi.org/10.1016/0304-3975(94)00070-0 SN - 0304-3975 VL - 133 IS - 1 SP - 85 EP - 94 ER - TY - GEN A1 - Meer, Klaus T1 - On the relations between discrete and continuous complexity theory T2 - Mathematical Logic Quarterly N2 - 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. KW - Real model of computation KW - 3-Satisfiability KW - Sparseness KW - Exponential-time computations Y1 - 1995 UR - http://onlinelibrary.wiley.com/doi/10.1002/malq.19950410214/abstract U6 - https://doi.org/10.1002/malq.19950410214 SN - 0885-064X VL - 41 IS - 2 SP - 281 EP - 286 ER - TY - GEN A1 - Meer, Klaus A1 - Lickteig, Thomas T1 - A note on testing the resultant T2 - Journal of Complexity N2 - 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. Y1 - 1995 UR - http://www.sciencedirect.com/science/article/pii/S0885064X85710163?np=y U6 - https://doi.org/10.1006/jcom.1995.1016 SN - 0885-064X VL - 11 IS - 3 SP - 344 EP - 351 ER - TY - GEN A1 - Meer, Klaus T1 - Counting problems over the reals. T2 - Theoretical Computer Science Y1 - 2000 SN - 0304-397 VL - 242 IS - 1-2 SP - 41 EP - 58 ER - TY - GEN A1 - Ben-David, Shai A1 - Meer, Klaus A1 - Michaux, Christian T1 - A note on non-complete problems in NP_R. T2 - Journal of Complexity Y1 - 2000 SN - 0885-064X VL - 16 IS - 1 SP - 324 EP - 332 ER - TY - GEN A1 - Gori, Marco A1 - Meer, Klaus T1 - A step towards a complexity theory for analog systems. T2 - Mathematical Logic Quarterly Y1 - 2002 SN - 0942-5616 VL - 48 IS - Suppl. 1 SP - 45 EP - 58 ER - TY - CHAP A1 - Makowsky, Janos A. A1 - Meer, Klaus ED - Cucker, Felipe ED - Rojas, Maurice T1 - Polynomials of bounded treewidth T2 - Foundations of Computational Mathematics, Proceedings of the Smalefest 2000 Y1 - 2002 SN - 978-981-02-4845-1 SP - 211 EP - 250 PB - World Scientific CY - Singapore ER - TY - GEN A1 - Matamala, Martin A1 - Meer, Klaus T1 - On the computational structure of the connected components of difficult sets T2 - Information Processing Letters Y1 - 1999 SN - 0020-0190 VL - 72 IS - 3-4 SP - 83 EP - 90 ER - TY - GEN A1 - Cucker, Felipe A1 - Meer, Klaus T1 - Logics which capture complexity classes over the reals T2 - Journal of Symbolic Logic Y1 - 1999 SN - 0022-4812 VL - 64 IS - 1 SP - 363 EP - 390 ER - TY - GEN A1 - Benning, Wilhelm A1 - Elkoushy, Ashraf A1 - Meer, Klaus T1 - Innere-Punkt Methoden für die automatisierte Fehlersuche in geodätischen Anwendungen (Interior point methods for automatic blunders detection in surveying) T2 - Allgemeine Vermessungsnachrichten Y1 - 1997 SN - 0002-5968 VL - 104 IS - 8-9 SP - 319 EP - 324 ER - TY - GEN A1 - Meer, Klaus A1 - Michaux, Christian T1 - A Survey on Real Structural Complexity Theory T2 - Bulletin of the Belgian Mathematical Society Simon Stevin Y1 - 1997 SN - 1370-1444 VL - 4 IS - 1 SP - 113 EP - 148 ER - TY - GEN A1 - Baartse, Martijn A1 - Meer, Klaus T1 - An algebraic proof of the real number PCP theorem T2 - Journal of Complexity N2 - 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. KW - Probabilistically checkable proofs KW - Real number model of computation KW - PCP theorem for NP over the reals KW - Testing trigonometric polynomials KW - Algebraic proofs Y1 - 2017 UR - http://www.sciencedirect.com/science/article/pii/S0885064X1630111X U6 - https://doi.org/10.1016/j.jco.2016.11.006 SN - 0885-064X VL - 40 SP - 34 EP - 77 ER - TY - GEN A1 - Baartse, Martijn A1 - Meer, Klaus T1 - Interactive proofs and a Shamir-like result for real number computations T2 - Computational Complexity Y1 - 2018 U6 - https://doi.org/10.1007/s00037-018-0174-6 SN - 1016-3328 SN - 1420-8954 ER - TY - CHAP A1 - Baartse, Martijn A1 - Meer, Klaus ED - Faliszewski, Piotr ED - Muscholl, Anca ED - Niedermeier, Rolf T1 - Real Interactive Proofs for VPSPACE T2 - 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-64300 SN - 978-3-95977-016-3 SP - 14.1 EP - 14.13 PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH CY - Wadern ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn ED - Beckmann, Arnold ED - Mitrana, Victor ED - Soskova, Mariya T1 - Some results on interactive proofs for real computations T2 - Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings Y1 - 2015 UR - http://www.springer.com/in/book/9783319200279 SN - 978-3-319-20027-9 U6 - https://doi.org/10.1007/978-3-319-20028-6 SP - 107 EP - 116 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn ED - Hirsch, Edward ED - Kuznetsov, Sergei O. ED - Pin, Jean-Éric ED - Vereshchagin, Nikolay T1 - Testing Low Degree Trigonometric Polynomials T2 - Computer Science - Theory and Applications 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014, Proceedings Y1 - 2014 UR - http://www.springer.com/de/book/9783319066851 SN - 978-3-319-06685-1 U6 - https://doi.org/10.1007/978-3-319-06686-8 SP - 77 EP - 96 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Naif, Ameen ED - Gopal, T. V. ED - Agrawal, Manindra ED - Li, Angsheng ED - Cooper, Stuart Barry T1 - Generalized Finite Automata over Real and Complex Numbers T2 - Theory and Applications of Models of Computation 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014, Proceedings Y1 - 2014 UR - http://www.springer.com/us/book/9783319060880 SN - 978-3-319-06088-0 U6 - https://doi.org/10.1007/978-3-319-06089-7 SP - 168 EP - 187 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn T1 - An algebraic proof of the real number PCP theorem T2 - Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II Y1 - 2015 UR - http://www.springer.com/us/book/9783662480533 SN - 978-3-662-48053-3 U6 - https://doi.org/10.1007/978-3-662-48054-0 SP - 50 EP - 61 PB - Springer-Verlag CY - Berlin [u.a.] ER - TY - CHAP A1 - Makowsky, Janos A. A1 - Meer, Klaus ED - Clote, Peter ED - Schwichtenberg, Helmut T1 - On the complexity of combinatorial and metafinite generating functions T2 - Computer science logic, 14th international workshop, proceedings, CSL 2000, Fischbachau, Germany, August 21 - 26, 2000 Y1 - 2000 SN - 3-540-67895-6 SP - 399 EP - 410 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Makowsky, Janos A. A1 - Meer, Klaus T1 - Polynomials of bounded tree-width T2 - Formal Power Series and Algebraic Combinatorics, Proceedings of the 12th International Conference, FPSAC'00, Moscow, Russia, June 2000 Y1 - 2000 SN - 3-540-67247-8 SP - 692 EP - 703 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Naif, Ameen ED - Dediu, Adrian-Horia ED - Janoušek, Jan ED - Martín-Vide, Carlos ED - Truthe, Bianca T1 - Periodic Generalized Automata over the Reals T2 - Language and Automata Theory and Applications 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings Y1 - 2016 UR - http://www.springer.com/de/book/9783319299990 SN - 978-3-319-29999-0 U6 - https://doi.org/10.1007/978-3-319-30000-9 SP - 168 EP - 180 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn ED - Montaña, José Luis ED - Pardo, Luis Miguel T1 - Topics in Real and Complex Number Complexity Theory T2 - Recent Advances in Real Complexity and Computation Y1 - 2013 UR - http://bookstore.ams.org/conm-604?c=1 SN - 978-0-8218-9150-6 U6 - https://doi.org/10.1090/conm/604 SP - 1 EP - 53 PB - American Mathematical Society CY - Providence, RI ER - TY - CHAP A1 - Cucker, Felipe A1 - Meer, Klaus T1 - Logics which capture complexity classes over the reals T2 - Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS '97 Bratislava, Slovakia, August 25-29, 1997 Proceedings Y1 - 1997 SP - 398 EP - 407 PB - Springer CY - Heidelberg ER - TY - CHAP A1 - Grädel, Erich A1 - Meer, Klaus T1 - Descriptive Complexity Theory over the real numbers T2 - Proceedings of the 27th Annual ACM Symposium on Theory of Computing STOC, Las Vegas, 1995 Y1 - 1995 U6 - https://doi.org/10.1145/225058.225151 SP - 315 EP - 324 PB - ACM CY - New York, NY ER - TY - CHAP A1 - Meer, Klaus A1 - Schreiber, Harold T1 - Maßsynthese vier- sechs- und achtgliedriger ebener Kurbelgetriebe und ihre Anwendung im Kfz-Karosseriebau T2 - Kurvengetriebe, Koppelgetriebe, gesteuerte Antriebe, Problemlösungen in der Bewegungstechnik, Conference Veitshöchheim 26. and 27. September 2000, VDI-Getriebetagung 2000 Y1 - 2000 SN - 3-18-091567-6 SP - 277 EP - 297 PB - VDI Verlag CY - Düsseldorf ER - TY - CHAP A1 - Meer, Klaus T1 - On consistency and width notions for constraint programs with algebraic constraints T2 - Functional and logic programming, 6th international symposium, proceedings, FLOPS 2002, Aizu, Japan, September 15 - 17, 2002 Y1 - 2002 SN - 3-540-44233-2 SP - 88 EP - 102 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus ED - Prívara, Igor ED - Ružička, Peter T1 - Counting problems over the reals T2 - Mathematical foundations of computer science 1997, 22nd international symposium, proceedings, MFCS '97, Bratislava, Slovakia, August 25 - 29, 1997 N2 - 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. Y1 - 1997 UR - http://www.springer.com/us/book/9783540634379?wt_mc=ThirdParty.SpringerLink.3.EPR653.About_eBook SN - 978-3-540-63437-9 U6 - https://doi.org/10.1007/BFb0029983 SP - 398 EP - 407 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus ED - Dongarra, Jack T1 - On the Approximation of Interval Functions T2 - Applied Parallel Computing. State of the Art in Scientific Computing, 7th International Workshop, PARA 2004, Lyngby, Denmark, June 20-23, 2004, Revised Selected Papers Y1 - 2004 SN - 978-3-540-29067-4 SP - 169 EP - 178 PB - Springer CY - Heidelberg [u.a.] ER - TY - CHAP A1 - Lickteig, Thomas A1 - Meer, Klaus A1 - Pardo, Luis Miguel T1 - Real Computation and Complexity, Dagstuhl seminar Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-4994 UR - http://drops.dagstuhl.de/opus/volltexte/2006/499/ PB - Internationale Begegnungs- und Forschungszentrum für Informatik CY - Dagstuhl ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn T1 - The PCP theorem for NP over the reals T2 - 30th Symposium on Theoretical Aspects of Computer Science STACS , Kiel, 2013 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-39262 UR - http://drops.dagstuhl.de/opus/volltexte/2013/3926/ SP - 104 EP - 115 CY - Leibnitz ER - TY - CHAP A1 - Meer, Klaus T1 - Almost transparent short proof for NP? T2 - Extended abstract, Proceedings 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, 2011 Y1 - 2011 SN - 978-3-642-22952-7 SP - 41 EP - 52 ER - TY - CHAP A1 - Meer, Klaus T1 - An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents Y1 - 2011 ER - TY - CHAP A1 - Koiran, Pascal A1 - Meer, Klaus T1 - On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width T2 - Graph-theoretic concepts in computer science, 34th international workshop, WG 2008, Durham, UK, June 30-July 2, 2008 Y1 - 2008 SN - 978-3-540-92247-6 SP - 252 EP - 263 PB - Springer CY - Berlin [u.a.] ER - TY - GEN A1 - Flarup Hansen, Uffe A1 - Meer, Klaus T1 - Two logical hierarchies of optimization problems over the real numbers T2 - Mathematical Logic Quaterly Y1 - 2006 SN - 0942-5616 VL - 52 IS - 1 SP - 37 EP - 50 ER - TY - CHAP A1 - Meer, Klaus T1 - Transparent long proofs: A first PCP theorem for NP(R) T2 - Extended Abstract in 31st International Colloquium on Automata, Languages and Programming ICALP 2004, Turku Y1 - 2004 SN - 3-540-22849-7 SP - 959 EP - 970 PB - Springer CY - Berlin ER - TY - JOUR A1 - Meer, Klaus T1 - Syropoulos, Apostolos: Hypercomputation. Berlin : Springer, 2008 JF - AMS Mathematical Reviews Y1 - 2009 SN - 0025-5629 IS - 2009j ER - TY - BOOK A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus A1 - Triesch, Eberhard T1 - Optimization Theory Y1 - 2004 SN - 978-1-402-08098-2 PB - Kluwer CY - Boston ER - TY - JOUR A1 - Meer, Klaus T1 - Blum, Lenore [u.a.]: Complexity and real computation. Berlin : Springer, 1998 JF - AMS Mathematical Reviews Y1 - 1999 SN - 0025-5629 IS - 99a SP - 509 EP - 600 ER -