32 Search Results for "Traub, Joseph"


Document
Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 15391)

Authors: Aicke Hinrichs, Joseph F. Traub, Henryk Wozniakowski, and Larisa Yaroslavtseva

Published in: Dagstuhl Reports, Volume 5, Issue 9 (2016)


Abstract
From 20.09.15 to 25.09.15, the Dagstuhl Seminar 15391 Algorithms and Complexity for Continuous Problems was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts or the presentations given during the seminar can be found in this report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Aicke Hinrichs, Joseph F. Traub, Henryk Wozniakowski, and Larisa Yaroslavtseva. Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 15391). In Dagstuhl Reports, Volume 5, Issue 9, pp. 57-76, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{hinrichs_et_al:DagRep.5.9.57,
  author =	{Hinrichs, Aicke and Traub, Joseph F. and Wozniakowski, Henryk and Yaroslavtseva, Larisa},
  title =	{{Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 15391)}},
  pages =	{57--76},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{9},
  editor =	{Hinrichs, Aicke and Traub, Joseph F. and Wozniakowski, Henryk and Yaroslavtseva, Larisa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.9.57},
  URN =		{urn:nbn:de:0030-drops-56854},
  doi =		{10.4230/DagRep.5.9.57},
  annote =	{Keywords: High Dimensional Problems, Tractability, Random coefficients, Multilevel algorithms, computational stochastic processes, Compressed sensing, Learning theory}
}
Document
Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 12391)

Authors: Alexander Keller, Frances Kuo, Andreas Neuenkirch, and Joseph F. Traub

Published in: Dagstuhl Reports, Volume 2, Issue 9 (2013)


Abstract
From 23.09.12 to 28.09.12, the Dagstuhl Seminar 12391 Algorithms and Complexity for Continuous Problems was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar can be found in this report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Alexander Keller, Frances Kuo, Andreas Neuenkirch, and Joseph F. Traub. Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 12391). In Dagstuhl Reports, Volume 2, Issue 9, pp. 200-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{keller_et_al:DagRep.2.9.200,
  author =	{Keller, Alexander and Kuo, Frances and Neuenkirch, Andreas and Traub, Joseph F.},
  title =	{{Algorithms and Complexity for Continuous Problems (Dagstuhl Seminar 12391)}},
  pages =	{200--225},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{9},
  editor =	{Keller, Alexander and Kuo, Frances and Neuenkirch, Andreas and Traub, Joseph F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.9.200},
  URN =		{urn:nbn:de:0030-drops-38920},
  doi =		{10.4230/DagRep.2.9.200},
  annote =	{Keywords: Computational complexity of continuous problems, Partial information, Biomedical learning problems, Random media, Computational finance, Noisy data, Tractability, Quantum computation, Computational stochastic processes, High-dimensional problems}
}
Document
09391 Abstracts Collection – Algorithms and Complexity for Continuous Problems

Authors: Thomas Müller-Gronbach, Leszek Plaskota, and Joseph F. Traub

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


Abstract
From 20.09.09 to 25.09.09, the Dagstuhl Seminar 09391 Algorithms and Complexity for Continuous Problems was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar 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 Müller-Gronbach, Leszek Plaskota, and Joseph F. Traub. 09391 Abstracts Collection – Algorithms and Complexity for Continuous Problems. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 9391, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{mullergronbach_et_al:DagSemProc.09391.1,
  author =	{M\"{u}ller-Gronbach, Thomas and Plaskota, Leszek and Traub, Joseph F.},
  title =	{{09391 Abstracts Collection – Algorithms and Complexity for Continuous Problems}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9391},
  editor =	{Thomas M\"{u}ller-Gronbach and Leszek Plaskota 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.09391.1},
  URN =		{urn:nbn:de:0030-drops-23005},
  doi =		{10.4230/DagSemProc.09391.1},
  annote =	{Keywords: Computational complexity of continuous problems, partial information, high-dimensional problems, tractability analysis, quasi-Monte Carlo methods, op operator equations, non-linear approximation, stochastic computation, ill posed-problems}
}
Document
Discrepancy Bounds for Mixed Sequences

Authors: Michael Gnewuch

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


Abstract
A mixed sequence is a sequence in the $s$-dimensional unit cube which one obtains by concatenating a $d$-dimensional low-discrepancy sequence with an $s-d$-dimensional random sequence. We discuss some probabilistic bounds on the star discrepancy of mixed sequences.

Cite as

Michael Gnewuch. Discrepancy Bounds for Mixed Sequences. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 9391, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{gnewuch:DagSemProc.09391.2,
  author =	{Gnewuch, Michael},
  title =	{{Discrepancy Bounds for Mixed Sequences}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9391},
  editor =	{Thomas M\"{u}ller-Gronbach and Leszek Plaskota 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.09391.2},
  URN =		{urn:nbn:de:0030-drops-22975},
  doi =		{10.4230/DagSemProc.09391.2},
  annote =	{Keywords: Star Discrepancy, Mixed Sequence, Hybrid Method, Monte Carlo, Quasi-Monte Carlo, Probabilistic Bounds}
}
Document
Evaluating Expectations of Functionals of Brownian Motions: a Multilevel Idea

Authors: Fred J. Hickernell, Thomas Müller-Gronbach, Ben Niu, and Klaus Ritter

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


Abstract
Prices of path dependent options may be modeled as expectations of functions of an infinite sequence of real variables. This talk presents recent work on bounding the error of such expectations using quasi-Monte Carlo algorithms. The expectation is approximated by an average of $n$ samples, and the functional of an infinite number of variables is approximated by a function of only $d$ variables. A multilevel algorithm employing a sum of sample averages, each with different truncated dimensions, $d_l$, and different sample sizes, $n_l$, yields faster convergence than a single level algorithm. This talk presents results in the worst-case error setting.

Cite as

Fred J. Hickernell, Thomas Müller-Gronbach, Ben Niu, and Klaus Ritter. Evaluating Expectations of Functionals of Brownian Motions: a Multilevel Idea. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 9391, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{hickernell_et_al:DagSemProc.09391.3,
  author =	{Hickernell, Fred J. and M\"{u}ller-Gronbach, Thomas and Niu, Ben and Ritter, Klaus},
  title =	{{Evaluating Expectations of Functionals of Brownian Motions: a Multilevel Idea}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9391},
  editor =	{Thomas M\"{u}ller-Gronbach and Leszek Plaskota 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.09391.3},
  URN =		{urn:nbn:de:0030-drops-22987},
  doi =		{10.4230/DagSemProc.09391.3},
  annote =	{Keywords: Brownian motions, multilevel, option pricing, worst-case error}
}
Document
Quasi-Monte Carlo, Monte Carlo, and regularized gradient optimization methods for source characterization of atmospheric releases

Authors: Krzysztof Sikorski, Bhagirath Addepalli, E. R. Pardyjak, and M. Zhdanov

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


Abstract
An inversion technique based on MC/QMC search and regularized gradient optimization was developed to solve the atmospheric source characterization problem. The Gaussian Plume Model was adopted as the forward operator and QMC/MC search was implemented in order to find good starting points for the gradient optimization. This approach was validated on the Copenhagen Tracer Experiments. The QMC approach with the utilization of clasical and scrambled Halton, Hammersley and Sobol points was shown to be 10-100 times more efficient than the Mersenne Twister Monte Carlo generator. Further experiments are needed for different data sets. Computational complexity analysis needs to be carried out .

Cite as

Krzysztof Sikorski, Bhagirath Addepalli, E. R. Pardyjak, and M. Zhdanov. Quasi-Monte Carlo, Monte Carlo, and regularized gradient optimization methods for source characterization of atmospheric releases. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 9391, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{sikorski_et_al:DagSemProc.09391.4,
  author =	{Sikorski, Krzysztof and Addepalli, Bhagirath and Pardyjak, E. R. and Zhdanov, M.},
  title =	{{Quasi-Monte Carlo, Monte Carlo, and regularized gradient optimization methods for source characterization of atmospheric releases }},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9391},
  editor =	{Thomas M\"{u}ller-Gronbach and Leszek Plaskota 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.09391.4},
  URN =		{urn:nbn:de:0030-drops-22998},
  doi =		{10.4230/DagSemProc.09391.4},
  annote =	{Keywords: Atmospheric source problem, Gaussian Plume Model, Quasi Monte Carlo method, gradient optimization}
}
Document
Weighted L_2 B Discrepancy and Approximation of Integrals over Reproducing Kernel Hilbert Spaces

Authors: Michael Gnewuch

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


Abstract
We extend the notion of $L_2$ $B$ discrepancy provided in [E. Novak, H. Wo'zniakowski, $L_2$ discrepancy and multivariate integration, in: Analytic number theory. Essays in honour of Klaus Roth. W. W. L. Chen, W. T. Gowers, H. Halberstam, W. M. Schmidt, and R. C. Vaughan (Eds.), Cambridge University Press, Cambridge, 2009, 359 – 388] to the weighted $L_2$ $mathcal{B}$ discrepancy. This newly defined notion allows to consider weights, but also volume measures different from the Lebesgue measure and classes of test sets different from measurable subsets of some Euclidean space. We relate the weighted $L_2$ $mathcal{B}$ discrepancy to numerical integration defined over weighted reproducing kernel Hilbert spaces and settle in this way an open problem posed by Novak and Wo'zniakowski.

Cite as

Michael Gnewuch. Weighted L_2 B Discrepancy and Approximation of Integrals over Reproducing Kernel Hilbert Spaces. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 9391, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{gnewuch:DagSemProc.09391.5,
  author =	{Gnewuch, Michael},
  title =	{{Weighted L\underline2 B Discrepancy and Approximation of Integrals over Reproducing Kernel Hilbert Spaces}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9391},
  editor =	{Thomas M\"{u}ller-Gronbach and Leszek Plaskota 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.09391.5},
  URN =		{urn:nbn:de:0030-drops-22966},
  doi =		{10.4230/DagSemProc.09391.5},
  annote =	{Keywords: Discrepancy, Numerical Integration, Quasi-Monte Carlo, Reproducing Kernel Hilbert Space}
}
Document
06391 Abstracts Collection – Algorithms and Complexity for Continuous Problems

Authors: Stephan Dahlke, Klaus Ritter, Ian H. Sloan, and Joseph F. Traub

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


Abstract
From 24.09.06 to 29.09.06, the Dagstuhl Seminar 06391 ``Algorithms and Complexity for Continuous Problems'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar 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

Stephan Dahlke, Klaus Ritter, Ian H. Sloan, and Joseph F. Traub. 06391 Abstracts Collection – Algorithms and Complexity for Continuous Problems. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{dahlke_et_al:DagSemProc.06391.1,
  author =	{Dahlke, Stephan and Ritter, Klaus and Sloan, Ian H. and Traub, Joseph F.},
  title =	{{06391 Abstracts Collection – Algorithms and Complexity for Continuous Problems}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--21},
  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.1},
  URN =		{urn:nbn:de:0030-drops-8782},
  doi =		{10.4230/DagSemProc.06391.1},
  annote =	{Keywords: Computational complexity, partial information, high-dimensional problems, operator equations, non-linear approximation, quantum computation, stochastic computation, ill posed-problems}
}
Document
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
Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries

Authors: Howard Barnum

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


Abstract
Generalizing earlier work characterizing the quantum query complexity of computing a function of an unknown classical ``black box'' function drawn from some set of such black box functions, we investigate a more general quantum query model in which the goal is to compute functions of $N imes N$ ``black box'' unitary matrices drawn from a set of such matrices, a problem with applications to determining properties of quantum physical systems. We characterize the existence of an algorithm for such a query problem, with given query and error, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct. Relaxing the primal constraints to correspond to mere pairwise near-orthogonality of the final states of a quantum computer, conditional on the various black-box inputs, rather than bounded-error distinguishability, we obtain a relaxed primal program the feasibility of whose dual still implies the nonexistence of a quantum algorithm. We use this to obtain a generalization, to our not-necessarily-commutative setting, of the ``spectral adversary method'' for quantum query lower bounds.

Cite as

Howard Barnum. Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{barnum:DagSemProc.06391.3,
  author =	{Barnum, Howard},
  title =	{{Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--25},
  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.3},
  URN =		{urn:nbn:de:0030-drops-8769},
  doi =		{10.4230/DagSemProc.06391.3},
  annote =	{Keywords: Quantum query complexity semidefinite programming}
}
Document
04401 Abstracts Collection – Algorithms and Complexity for Continuous

Authors: Thomas Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub

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


Abstract
From 26.09.04 to 01.10.04, the Dagstuhl Seminar ``Algorithms and Complexity for Continuous Problems'' 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 Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub. 04401 Abstracts Collection – Algorithms and Complexity for Continuous. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{mullergronbach_et_al:DagSemProc.04401.1,
  author =	{M\"{u}ller-Gronbach, Thomas and Novak, Erich and Petras, Knut and Traub, Joseph F.},
  title =	{{04401 Abstracts Collection – Algorithms and Complexity for Continuous}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--21},
  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.1},
  URN =		{urn:nbn:de:0030-drops-1545},
  doi =		{10.4230/DagSemProc.04401.1},
  annote =	{Keywords: Complexity and regularization of ill-posed problems , nonlinear approximation , tractability of high-dimensional numerical problems quantum computing , stochastic computation and quantization , global optimization , differential and integral equations}
}
Document
04401 Summary – Algorithms and Complexity for Continuous Problems

Authors: Thomas Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub

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


Abstract
The goal of this workshop was to bring together researchers from different communities working on computational aspects of continuous problems. Continuous computational problems arise in many areas of science and engineering. Examples include path and multivariate integration, function approximation, optimization, as well as differential, integral, and operator equations. Understanding the complexity of such problems and constructing efficient algorithms is both important and challenging. The workshop was of a very interdisciplinary nature with invitees from, e.g., computer science, numerical analysis, discrete, applied, and pure mathematics, physics, statistics, and scientific computation. Many of the lectures were presented by Ph.D. students. Compared to earlier meetings, several very active research areas received more emphasis. These include Quantum Computing, Complexity and Tractability of high-dimensional problems, Stochastic Computation, and Quantization, which was an entirely new field for this workshop. Due to strong connections between the topics treated at this workshop many of the participants initiated new cooperations and research projects. For more details, see the pdf-file with the same title.

Cite as

Thomas Müller-Gronbach, Erich Novak, Knut Petras, and Joseph F. Traub. 04401 Summary – Algorithms and Complexity for Continuous Problems. 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{mullergronbach_et_al:DagSemProc.04401.2,
  author =	{M\"{u}ller-Gronbach, Thomas and Novak, Erich and Petras, Knut and Traub, Joseph F.},
  title =	{{04401 Summary – Algorithms and Complexity for Continuous Problems}},
  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.2},
  URN =		{urn:nbn:de:0030-drops-1530},
  doi =		{10.4230/DagSemProc.04401.2},
  annote =	{Keywords: Complexity and Regularization of Ill-Posed Problems , Non-Linear Approximation , Tractability of High-Dimensional Numerical Problems Quasi-Monte Carlo Methods , Quantum Computing , Stochastic Computation and Quantization , Global Optimization , Differential and Integral Equation}
}
Document
Fast Component-By-Component Construction of Rank-1 Lattice Rules for (Non-)Primes (Part II)

Authors: Dirk Nuyens and Ronald Cools

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


Abstract
Part I: (this part of the talk by Ronald Cools) We restate our previous result which showed that it is possible to construct the generating vector of a rank-1 lattice rule in a fast way, i.e. O(s n log(n)), with s the number of dimensions and n the number of points assumed to be prime. Here we explicitly use basic facts from algebra to exploit the structure of a matrix – which introduces the crucial cost in the construction – to get a matrix-vector multiplication in time O(n log(n)) instead of O(n^2). We again stress the fact that the algorithm works for any tensor product reproducing kernel Hilbert space. Part II: (this part of the talk by Dirk Nuyens) In the second part we generalize the tricks used for primes to non-primes, by basically falling back to algebraic group theory. In this way it can be shown that also for a non-prime number of points, this crucial matrix-vector multiplication can be done in time O(n log(n)). We conclude that the construction of rank-1 lattice rules in an arbitrary r.k.h.s. for an arbitrary amount of points can be done in a fast way of O(s n log(n)).

Cite as

Dirk Nuyens and Ronald Cools. Fast Component-By-Component Construction of Rank-1 Lattice Rules for (Non-)Primes (Part II). In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{nuyens_et_al:DagSemProc.04401.3,
  author =	{Nuyens, Dirk and Cools, Ronald},
  title =	{{Fast Component-By-Component Construction of Rank-1 Lattice Rules for (Non-)Primes (Part II)}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--26},
  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.3},
  URN =		{urn:nbn:de:0030-drops-1486},
  doi =		{10.4230/DagSemProc.04401.3},
  annote =	{Keywords: numerical integration , cubature/quadrature , rank-1 lattice , component-by-component construction , fast algorithm}
}
Document
Functional Quantization and Entropy for Stochastic Processes

Authors: Harald Luschgy and Gilles Pagès

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


Abstract
Let X be a Gaussian process and let U denote the Strassen ball of X. A precise link between the L^2-quantization error of X and the Kolmogorov (metric) entropy of U in a Hilbert space setting is established. In particular, the sharp asymptotics of the Kolmogorov entropy problem is derived. The condition imposed is regular variation of the eigenvalues of the covariance operator. Good computable quantizers for Gaussian and diffusion processes and their numerical efficieny are discussed. This is joint work with G. Pagès, Université de Paris 6.

Cite as

Harald Luschgy and Gilles Pagès. Functional Quantization and Entropy for Stochastic Processes. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{luschgy_et_al:DagSemProc.04401.4,
  author =	{Luschgy, Harald and Pag\`{e}s, Gilles},
  title =	{{Functional Quantization and Entropy for Stochastic Processes}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--15},
  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.4},
  URN =		{urn:nbn:de:0030-drops-1446},
  doi =		{10.4230/DagSemProc.04401.4},
  annote =	{Keywords: Functional quantization , entropy , product quantizers}
}
Document
Information-Based Nonlinear Approximation: An Average Case Setting

Authors: Leszek Plaskota

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


Abstract
Nonlinear approximation has usually been studied under deterministic assumption and complete information about the underlying functions. We assume only partial information and we are interested in the average case error and complexity of approximation. It turns out that the problem can be essentially split into two independent problems related to average case nonlinear (restricted) approximation from complete information, and average case unrestricted approximation from partial information. The results are then applied to average case piecewise polynomial approximation, and to average case approximation of real sequences.

Cite as

Leszek Plaskota. Information-Based Nonlinear Approximation: An Average Case Setting. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{plaskota:DagSemProc.04401.5,
  author =	{Plaskota, Leszek},
  title =	{{Information-Based Nonlinear Approximation: An Average Case Setting}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--1},
  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.5},
  URN =		{urn:nbn:de:0030-drops-1504},
  doi =		{10.4230/DagSemProc.04401.5},
  annote =	{Keywords: average case setting , nonlinear approximation , information-based comlexity}
}
  • Refine by Author
  • 11 Traub, Joseph F.
  • 6 Ritter, Klaus
  • 5 Müller-Gronbach, Thomas
  • 5 Novak, Erich
  • 3 Dahlke, Stephan
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Computational complexity of continuous problems
  • 2 Quasi-Monte Carlo
  • 2 Tractability
  • 2 complexity
  • 2 high-dimensional problems
  • Show More...

  • Refine by Type
  • 32 document

  • Refine by Publication Year
  • 16 2005
  • 5 2009
  • 3 2007
  • 1 1992
  • 1 1994
  • 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