8 Search Results for "Meer, Klaus"

Document
DOI: 10.4230/LIPIcs.MFCS.2016.14
Real Interactive Proofs for VPSPACE

Authors: Martijn Baartse and Klaus Meer

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2013.104
The PCP theorem for NP over the reals

Authors: Martijn Baartse and Klaus Meer

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

Abstract
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.
Cite as

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
DOI: 10.4230/DagSemProc.06391.2
Real Computational Universality: The Word Problem for a class of groups with infinite presentation

Authors: Klaus Meer and Martin Ziegler

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

Abstract
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.
Cite as

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
DOI: 10.4230/DagSemProc.04061.1
04061 Abstracts Collection – Real Computation and Complexity

Authors: Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo

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

Abstract
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.
Cite as

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
DOI: 10.4230/DagSemProc.04061.2
04061 Summary – Real Computation and Complexity

Authors: Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo

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

Abstract
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.
Cite as

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
DOI: 10.4230/DagSemProc.04401.9
On the Complexity of Computing Multi-Homogeneous Bézout Numbers

Authors: Klaus Meer and Gregorio Malajovich

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

Abstract
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.
Cite as

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
DOI: 10.4230/DagSemProc.04411.6
Bridging today's Internet Heterogeneity with a Content-oriented Approach

Authors: Klaus Wehrle

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
Despite the success of Internet technology and protocols, their deficiencies become apparent with growing and emerging applications like 3G mobile devices or pervasive environments. In these fields, there is a growing demand for additional support of mobility, multi- or anycast communication, or service composition. ...
Cite as

Klaus Wehrle. Bridging today's Internet Heterogeneity with a Content-oriented Approach. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{wehrle:DagSemProc.04411.6,
  author =	{Wehrle, Klaus},
  title =	{{Bridging today's Internet Heterogeneity with a Content-oriented Approach}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.6},
  URN =		{urn:nbn:de:0030-drops-1004},
  doi =		{10.4230/DagSemProc.04411.6},
  annote =	{Keywords: Peer-to-Peer , Overlay , Communication Form , Bridging Heterogeneity}
}
Document
DOI: 10.4230/DagSemRep.407
Real Computation and Complexity (Dagstuhl Seminar 04061)

Authors: Thomas Lickteig, Klaus Meer, and Luis Miguel Pardo

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

Abstract
Cite as

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},
}
  • Refine by Author
  • 7 Meer, Klaus
  • 3 Lickteig, Thomas
  • 3 Pardo, Luis Miguel
  • 2 Baartse, Martijn
  • 1 Malajovich, Gregorio
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 real number computation
  • 1 Blum-Shub-Smale model
  • 1 Bridging Heterogeneity
  • 1 Communication Form
  • 1 Computational group theory
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2005
  • 2 2006
  • 1 2004
  • 1 2007
  • 1 2013
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact