@misc{BaartseBarmpalias, author = {Baartse, Martijn and Barmpalias, George}, title = {On the gap between trivial and nontrivial initial segment prefix-free complexity}, series = {Theory of Computing Systems}, journal = {Theory of Computing Systems}, issn = {1433-0490}, pages = {20}, abstract = {An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if the prefix-free Kolmogorov complexity of each initial segment of X is the same as the complexity of the sequence of 0s of the same length, up to a constant. We study the gap between the minimum complexity K(0 n ) and the initial segment complexity of a nontrivial sequence, and in particular the nondecreasing unbounded functions f such that (⋆) for a nontrivial sequence X, where K denotes the prefix-free complexity. Our first result is that there exists a \$\varDelta^{0}_{3}\$ unbounded nondecreasing function f which does not have this property. It is known that such functions cannot be \$\varDelta^{0}_{2}\$ hence this is an optimal bound on their arithmetical complexity. Moreover it improves the bound \$\varDelta^{0}_{4}\$ that was known from Csima and Montalb{\´a}n (Proc. Amer. Math. Soc. 134(5):1499-1502, 2006). Our second result is that if f is \$\varDelta^{0}_{2}\$ then there exists a non-empty \$\varPi^{0}_{1}\$ class of reals X with nontrivial prefix-free complexity which satisfy (⋆). This implies that in this case there uncountably many nontrivial reals X satisfying (⋆) in various well known classes from computability theory and algorithmic randomness; for example low for Ω, non-low for Ω and computably dominated reals. A special case of this result was independently obtained by Bienvenu, Merkle and Nies (STACS, pp. 452-463, 2011).}, 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{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{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{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{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} }