@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} } @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{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} } @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} } @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{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} } @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} } @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} } @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} } @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} } @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} }