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 -