Document

**Published in:** LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

We study interactive proofs in the framework of real number complexity as introduced by Blum, Shub, and Smale. The ultimate goal is to give a Shamir like characterization of the real counterpart IP_R of classical IP. Whereas classically Shamir's result implies IP = PSPACE = PAT = PAR, in our framework a major difficulty arises from the fact that in contrast to Turing complexity theory the real number classes PAR_R and PAT_R differ and space resources considered alone are not meaningful. It is not obvious to see whether IP_R is characterized by one of them - and if so by which.
In recent work the present authors established an upper bound IP_R is a subset of MA(Exists)R, where MA(Exists)R is a complexity class satisfying PAR_R is a strict subset of MA(Exists)R, which is a subset of PAT_R and conjectured to be different from PAT_R. The goal of the present paper is to complement this result and to prove interesting lower bounds for IP_R. More precisely, we design interactive real protocols for a large class of functions introduced by Koiran and Perifel and denoted by UniformVSPACE^0. As consequence, we show PAR_R is a subset of IP_R, which in particular implies co-NP_R is a subset of IP_R, and P_R^{Res} is a subset of IP_R, where Res denotes certain multivariate Resultant polynomials.
Our proof techniques are guided by the question in how far Shamir's classical proof can be used as well in the real number setting. Towards this aim results by Koiran and Perifel on UniformVSPACE^0 are extremely helpful.

Martijn Baartse and Klaus Meer. Real Interactive Proofs for VPSPACE. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{baartse_et_al:LIPIcs.MFCS.2016.14, author = {Baartse, Martijn and Meer, Klaus}, title = {{Real Interactive Proofs for VPSPACE}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {14:1--14:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.14}, URN = {urn:nbn:de:0030-drops-64300}, doi = {10.4230/LIPIcs.MFCS.2016.14}, annote = {Keywords: interactive proofs, real number computation, Shamir's theorem} }

Document

**Published in:** LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

In this paper we show that the PCP theorem holds as well in the real
number computational model introduced by Blum, Shub, and Smale.
More precisely, the real number counterpart NP_R of the classical
Turing model class NP can be characterized as NP_R = PCP_R(O(log n), O(1)). Our proof structurally follows the one by Dinur for classical NP. However, a lot of minor and major changes are necessary due to the real numbers as underlying computational structure. The analogue result holds for the complex numbers and NP_C.

Martijn Baartse and Klaus Meer. The PCP theorem for NP over the reals. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 104-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{baartse_et_al:LIPIcs.STACS.2013.104, author = {Baartse, Martijn and Meer, Klaus}, title = {{The PCP theorem for NP over the reals}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {104--115}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.104}, URN = {urn:nbn:de:0030-drops-39262}, doi = {10.4230/LIPIcs.STACS.2013.104}, annote = {Keywords: PCP, real number computation, systems of polynomials} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6391, Algorithms and Complexity for Continuous Problems (2007)

In this talk we introduce a class of groups represented as quotient groups
of some free groups generated by infinitely many elements and certain normal
subgroups. We show that the related word problem is universal in the Blum-Shub-Smale model
of computation, i.e. it has the same difficulty as the real Halting Problem.
This is the first natural example of a problem with this property.
The work has been done jointly with Martin Ziegler.

Klaus Meer and Martin Ziegler. Real Computational Universality: The Word Problem for a class of groups with infinite presentation. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{meer_et_al:DagSemProc.06391.2, author = {Meer, Klaus and Ziegler, Martin}, title = {{Real Computational Universality: The Word Problem for a class of groups with infinite presentation}}, booktitle = {Algorithms and Complexity for Continuous Problems}, pages = {1--20}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {6391}, editor = {Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06391.2}, URN = {urn:nbn:de:0030-drops-8773}, doi = {10.4230/DagSemProc.06391.2}, annote = {Keywords: Computational group theory, word problem, Blum-Shub-Smale model} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 4061, Real Computation and Complexity (2006)

From 01.02.04 to 06.02.04, the Dagstuhl Seminar 04061 ``Real Computation and Complexity'' was held in the International Conference and Research Center (IBFI),
Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo. 04061 Abstracts Collection – Real Computation and Complexity. In Real Computation and Complexity. Dagstuhl Seminar Proceedings, Volume 4061, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lickteig_et_al:DagSemProc.04061.1, author = {Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel}, title = {{04061 Abstracts Collection – Real Computation and Complexity}}, booktitle = {Real Computation and Complexity}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {4061}, editor = {Thomas Lickteig and Klaus Meer and Luis Miguel Pardo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04061.1}, URN = {urn:nbn:de:0030-drops-4584}, doi = {10.4230/DagSemProc.04061.1}, annote = {Keywords: Real algebraic complexity and lower bounds, numerical methods, homotopy methods, condition as complexity ingredient, symbolic methods, bit complexity} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 4061, Real Computation and Complexity (2006)

The seminar "Real Computation and Complexity" was intended as a meeting
place of several tendencies in the complexity analysis of algorithms in real computation.
One main idea therefore was to bring together scientists with rather
different backgrounds such as numerical analysis, symbolic computing, real and
complex algebraic geometry, logic, differential algebra and computational complexity.
This broadness guaranteed to get a thorough overview of current results,
methods and trends in the area. It allowed as well to discuss main problems
related to all aspects of real computation and complexity from different perspectives.

Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo. 04061 Summary – Real Computation and Complexity. In Real Computation and Complexity. Dagstuhl Seminar Proceedings, Volume 4061, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lickteig_et_al:DagSemProc.04061.2, author = {Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel}, title = {{04061 Summary – Real Computation and Complexity}}, booktitle = {Real Computation and Complexity}, pages = {1--7}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {4061}, editor = {Thomas Lickteig and Klaus Meer and Luis Miguel Pardo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04061.2}, URN = {urn:nbn:de:0030-drops-4994}, doi = {10.4230/DagSemProc.04061.2}, annote = {Keywords: } }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 4401, Algorithms and Complexity for Continuous Problems (2005)

We study the question how difficult it is to compute the multi-homogeneous
B\'ezout number for a polynomial system of given number $n$ of variables
and given support $A$ of monomials with non-zero coefficients.
We show that this number is NP-hard to compute. It cannot even be efficiently
approximated within an arbitrary, fixed factor unless P = NP.
This is joint work with Gregorio Malajovich.

Klaus Meer and Gregorio Malajovich. On the Complexity of Computing Multi-Homogeneous BÃƒÂ©zout Numbers. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{meer_et_al:DagSemProc.04401.9, author = {Meer, Klaus and Malajovich, Gregorio}, title = {{On the Complexity of Computing Multi-Homogeneous B\~{A}ƒ\^{A}©zout Numbers}}, booktitle = {Algorithms and Complexity for Continuous Problems}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {4401}, editor = {Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.9}, URN = {urn:nbn:de:0030-drops-1460}, doi = {10.4230/DagSemProc.04401.9}, annote = {Keywords: multi-homogeneous B\~{A}ƒ\^{A}©zout numbers , number of roots of polynomials , approximation algorithms} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo. Real Computation and Complexity (Dagstuhl Seminar 04061). Dagstuhl Seminar Report 407, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2004)

Copy BibTex To Clipboard

@TechReport{lickteig_et_al:DagSemRep.407, author = {Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel}, title = {{Real Computation and Complexity (Dagstuhl Seminar 04061)}}, pages = {1--25}, ISSN = {1619-0203}, year = {2004}, type = {Dagstuhl Seminar Report}, number = {407}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.407}, URN = {urn:nbn:de:0030-drops-152874}, doi = {10.4230/DagSemRep.407}, }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail