Search Results

Documents authored by Ziegler, Martin

Document
DOI: 10.4230/LIPIcs.CSL.2020.34
Computing Haar Measures

Authors: Arno Pauly, Dongseong Seon, and Martin Ziegler

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
According to Haar’s Theorem, every compact topological group G admits a unique (regular, right and) left-invariant Borel probability measure μ_G. Let the Haar integral (of G) denote the functional ∫_G:?(G)∋ f ↦ ∫ f d μ_G integrating any continuous function f:G → ℝ with respect to μ_G. This generalizes, and recovers for the additive group G=[0;1)mod 1, the usual Riemann integral: computable (cmp. Weihrauch 2000, Theorem 6.4.1), and of computational cost characterizing complexity class #P_1 (cmp. Ko 1991, Theorem 5.32). We establish that in fact, every computably compact computable metric group renders the Haar measure/integral computable: once using an elegant synthetic argument, exploiting uniqueness in a computably compact space of probability measures; and once presenting and analyzing an explicit, imperative algorithm based on "maximum packings" with rigorous error bounds and guaranteed convergence. Regarding computational complexity, for the groups SO(3) and SU(2), we reduce the Haar integral to and from Euclidean/Riemann integration. In particular both also characterize #P_1.
Cite as

Arno Pauly, Dongseong Seon, and Martin Ziegler. Computing Haar Measures. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pauly_et_al:LIPIcs.CSL.2020.34,
  author =	{Pauly, Arno and Seon, Dongseong and Ziegler, Martin},
  title =	{{Computing Haar Measures}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.34},
  URN =		{urn:nbn:de:0030-drops-116779},
  doi =		{10.4230/LIPIcs.CSL.2020.34},
  annote =	{Keywords: Computable analysis, topological groups, exact real arithmetic, Haar measure}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.30
Average-Case Polynomial-Time Computability of Hamiltonian Dynamics

Authors: Akitoshi Kawamura, Holger Thies, and Martin Ziegler

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We apply average-case complexity theory to physical problems modeled by continuous-time dynamical systems. The computational complexity when simulating such systems for a bounded time-frame mainly stems from trajectories coming close to complex singularities of the system. We show that if for most initial values the trajectories do not come close to singularities the simulation can be done in polynomial time on average. For Hamiltonian systems we relate this to the volume of "almost singularities" in phase space and give some general criteria to show that a Hamiltonian system can be simulated efficiently on average. As an application we show that the planar circular-restricted three-body problem is average-case polynomial-time computable.
Cite as

Akitoshi Kawamura, Holger Thies, and Martin Ziegler. Average-Case Polynomial-Time Computability of Hamiltonian Dynamics. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kawamura_et_al:LIPIcs.MFCS.2018.30,
  author =	{Kawamura, Akitoshi and Thies, Holger and Ziegler, Martin},
  title =	{{Average-Case Polynomial-Time Computability of Hamiltonian Dynamics}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.30},
  URN =		{urn:nbn:de:0030-drops-96125},
  doi =		{10.4230/LIPIcs.MFCS.2018.30},
  annote =	{Keywords: Computable Analysis, Real computation, Dynamical systems, Average-case complexity, Computation in physics}
}
Document
DOI: 10.4230/DagRep.7.11.142
Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481)

Authors: Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch, and Martin Ziegler

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)

Abstract
Naive computations with real numbers on computers may cause serious errors. In traditional numerical computation these errors are often neglected or, more seriously, not identified. Two approaches attack this problem and investigate its background, Reliable Computing and Computable Analysis. Methods in Reliable Computing are essentially mathematical theorems, the assumptions of which are verified on the computer. This verification is performed using the very efficient floating point arithmetic. If the verification succeeds, the assertions are true and correct error bounds have been computed; if not, a corresponding message is given. Thus the results are always mathematically correct. A specific advantage of Reliable Computing is that imprecise data are accepted; the challenge is to develop mathematical theorems the assumptions of which can be verified effectively in floating-point and to produce narrow bounds for the solution. Computable Analysis extends the traditional theory of computability on countable sets to the real numbers and more general spaces by refining continuity to computability. Numerous even basic and simple problems are not computable since they cannot be solved continuously. In many cases computability can be refined to computational complexity which is the time or space a Turing machine needs to compute a result with given precision. By treating precision as a parameter, this goes far beyond the restrictions of double precision arithmetic used in Reliable computing. For practical purposes, however, the asymptotic results from complexity theory must be refined. Software libraries provide efficient implementations for exact real computations. Both approaches are established theories with numerous important results. However, despite of their obvious close relations these two areas are developing almost independently. For exploring possibilities of closer contact we have invited experts from both areas to this seminar. For improving the mutual understanding some tutorial-like talks have been included in the program. As a result of the seminar it can be stated that interesting joint research is possible.
Cite as

Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch, and Martin Ziegler. Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481). In Dagstuhl Reports, Volume 7, Issue 11, pp. 142-167, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{muller_et_al:DagRep.7.11.142,
  author =	{M\"{u}ller, Norbert T. and Rump, Siegfried M. and Weihrauch, Klaus and Ziegler, Martin},
  title =	{{ Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481)}},
  pages =	{142--167},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{M\"{u}ller, Norbert T. and Rump, Siegfried M. and Weihrauch, Klaus and Ziegler, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.11.142},
  URN =		{urn:nbn:de:0030-drops-86826},
  doi =		{10.4230/DagRep.7.11.142},
  annote =	{Keywords: Computable Analysis, Verification Methods, Real Complexity Theory, Reliable Computing}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2277
Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability

Authors: Martin Ziegler

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
It is folklore particularly in numerical and computer sciences that, instead of solving some general problem $f:A\to B$, additional structural information about the input $x\in A$ (that is any kind of promise that $x$ belongs to a certain subset $A'\subseteq A$) should be taken advantage of. Some examples from real number computation show that such discrete advice can even make the difference between computability and uncomputability. We turn this into a both topological and combinatorial complexity theory of information, investigating for several practical problem show much advice is necessary and sufficient to render them computable. Specifically, finding a nontrivial solution to a homogeneous linear equation $A\cdot\vec x=0$ for a given singular real $n\times n$-matrix $A$ is possible when knowing $\rank(A)\in\{0,1,\ldots,n-1\}$; and we show this to be best possible. Similarly, diagonalizing (i.e. finding a basis of eigenvectors of) a given real symmetric $n\times n$-matrix $A$ is possible when knowing the number of distinct eigenvalues: an integer between $1$ and $n$ (the latter corresponding to the nondegenerate case). And again we show that $n$--fold (i.e. roughly $\log n$ bits of) additional information is indeed necessary in order to render this problem (continuous and) computable; whereas finding \emph{some single} eigenvector of $A$ requires and suffices with $\Theta(\log n)$--fold advice.
Cite as

Martin Ziegler. Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ziegler:OASIcs.CCA.2009.2277,
  author =	{Ziegler, Martin},
  title =	{{Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{269--280},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2277},
  URN =		{urn:nbn:de:0030-drops-22770},
  doi =		{10.4230/OASIcs.CCA.2009.2277},
  annote =	{Keywords: Nonuniform computability, recursive analysis, topological complexity, linear algebra}
}
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.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}
}
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