38 Search Results for "Traub, Joseph F."

Document
DOI: 10.4230/LIPIcs.GD.2025.23
The Price of Connectivity Augmentation on Planar Graphs

Authors: Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.
Cite as

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt. The Price of Connectivity Augmentation on Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.GD.2025.23,
  author =	{A. Akitaya, Hugo and Dallant, Justin and Demaine, Erik D. and Kaufmann, Michael and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D. and Ueckerdt, Torsten},
  title =	{{The Price of Connectivity Augmentation on Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.23},
  URN =		{urn:nbn:de:0030-drops-250095},
  doi =		{10.4230/LIPIcs.GD.2025.23},
  annote =	{Keywords: connectivity augmentation, local crossing number, flip distance}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.4
Streaming Algorithms for Network Design

Authors: Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, and Ali Vakilian

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph G = (V, E) and an integer connectivity requirement r(uv) for each u, v ∈ V. The objective is to find a minimum-weight subgraph H ⊆ G such that, for every pair of vertices u, v ∈ V, u and v are r(uv)-edge/vertex-connected. Recent work by [Ce Jin et al., 2024] obtained approximation algorithms for edge-connectivity augmentation, and via that, also derived algorithms for edge-connectivity SNDP (EC-SNDP). In this work we consider vertex-connectivity setting (VC-SNDP) and obtain several results for it as well as improved results for EC-SNDP. - We provide a general framework for solving connectivity problems including SNDP and others in streaming; this is based on a connection to fault-tolerant spanners. For VC-SNDP we provide an O(tk)-approximation in Õ(k^{1-1/t}n^{1 + 1/t}) space, where k is the maximum connectivity requirement, assuming an exact algorithm at the end of the stream. Using a refined LP-based analysis, we provide an O(β t)-approximation where β is the integrality gap of the natural cut-based LP relaxation. These are the first approximation algorithms in the streaming model for VC-SNDP. When applied to the EC-SNDP, our framework provides an O(t)-approximation in Õ(k^{1/2-1/(2t)}n^{1 + 1/t} + kn) space, improving the O(t log k)-approximation of [Ce Jin et al., 2024] using Õ(kn^{1+1/t}) space; this also extends to element-connectivity SNDP. - We consider vertex connectivity-augmentation in the link-arrival model. The input is a k-vertex-connected spanning subgraph G, and additional weighted links L arrive in the stream; the goal is to store the min-weight set of links such that G ∪ L is (k+1)-vertex-connected. We obtain constant-factor approximations in near-linear space for k = 1, 2. Our result for k = 2 is based on using the SPQR tree, a novel application for this well-known representation of 2-connected graphs.
Cite as

Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, and Ali Vakilian. Streaming Algorithms for Network Design. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2025.4,
  author =	{Chekuri, Chandra and Jain, Rhea and Mahabadi, Sepideh and Vakilian, Ali},
  title =	{{Streaming Algorithms for Network Design}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.4},
  URN =		{urn:nbn:de:0030-drops-243709},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.4},
  annote =	{Keywords: Streaming Algorithms, Survivable Network Design, Fault-Tolerant Spanners}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.24
Computational Geometry with Probabilistically Noisy Primitive Operations

Authors: David Eppstein, Michael T. Goodrich, and Vinesh Sridhar

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.
Cite as

David Eppstein, Michael T. Goodrich, and Vinesh Sridhar. Computational Geometry with Probabilistically Noisy Primitive Operations. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.WADS.2025.24,
  author =	{Eppstein, David and Goodrich, Michael T. and Sridhar, Vinesh},
  title =	{{Computational Geometry with Probabilistically Noisy Primitive Operations}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.24},
  URN =		{urn:nbn:de:0030-drops-242552},
  doi =		{10.4230/LIPIcs.WADS.2025.24},
  annote =	{Keywords: Computational geometry, noisy comparisons, random walks}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2025.36
Explainability is a Game for Probabilistic Bisimilarity Distances

Authors: Emily Vlasman, Anto Nanah Ji, James Worrell, and Franck van Breugel

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
We revisit a game from the literature that characterizes the probabilistic bisimilarity distances of a labelled Markov chain. We illustrate how an optimal policy of the game can explain these distances. Like the games that characterize bisimilarity and probabilistic bisimilarity, the game is played on pairs of states and matches transitions of those states. To obtain more convincing and interpretable explanations than those provided by generic optimal policies, we restrict to optimal policies that delay reaching observably inequivalent state pairs for as long as possible (called 1-maximal) while quickly reaching equivalent ones (called 0-minimal). We present iterative algorithms that compute 1-maximal and 0-minimal policies and prove an exponential lower bound for the number of iterations of the algorithm that computes 1-maximal policies.
Cite as

Emily Vlasman, Anto Nanah Ji, James Worrell, and Franck van Breugel. Explainability is a Game for Probabilistic Bisimilarity Distances. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vlasman_et_al:LIPIcs.CONCUR.2025.36,
  author =	{Vlasman, Emily and Nanah Ji, Anto and Worrell, James and van Breugel, Franck},
  title =	{{Explainability is a Game for Probabilistic Bisimilarity Distances}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.36},
  URN =		{urn:nbn:de:0030-drops-239861},
  doi =		{10.4230/LIPIcs.CONCUR.2025.36},
  annote =	{Keywords: probabilistic bisimilarity distance, labelled Markov chain, game, policy, explainability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.51
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures

Authors: Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the (p,q)-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains p-edge-connectivity between given terminal pairs against edge failures, assuming at most q unprotected edges can fail. We design polynomial-time exact algorithms for the cases where p and q are small and approximation algorithms for general values of p and q. Additionally, we show that when both p and q are part of the input, even deciding whether a given solution is feasible is NP-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either p or q is constant, for which our new hardness result now provides justification.
Cite as

Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang. Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hommelsheim_et_al:LIPIcs.STACS.2025.51,
  author =	{Hommelsheim, Felix and Liu, Zhenwei and Megow, Nicole and Zhang, Guochuan},
  title =	{{Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.51},
  URN =		{urn:nbn:de:0030-drops-228761},
  doi =		{10.4230/LIPIcs.STACS.2025.51},
  annote =	{Keywords: Network Design, Edge Failures, Graph Connectivity, Approximation Algorithms}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.3
Knowledge Engineering Using Large Language Models

Authors: Bradley P. Allen, Lise Stork, and Paul Groth

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Knowledge engineering is a discipline that focuses on the creation and maintenance of processes that generate and apply knowledge. Traditionally, knowledge engineering approaches have focused on knowledge expressed in formal languages. The emergence of large language models and their capabilities to effectively work with natural language, in its broadest sense, raises questions about the foundations and practice of knowledge engineering. Here, we outline the potential role of LLMs in knowledge engineering, identifying two central directions: 1) creating hybrid neuro-symbolic knowledge systems; and 2) enabling knowledge engineering in natural language. Additionally, we formulate key open research questions to tackle these directions.
Cite as

Bradley P. Allen, Lise Stork, and Paul Groth. Knowledge Engineering Using Large Language Models. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.1.1.3,
  author =	{Allen, Bradley P. and Stork, Lise and Groth, Paul},
  title =	{{Knowledge Engineering Using Large Language Models}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:19},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.3},
  URN =		{urn:nbn:de:0030-drops-194777},
  doi =		{10.4230/TGDK.1.1.3},
  annote =	{Keywords: knowledge engineering, large language models}
}
Document
DOI: 10.4230/DagRep.5.9.57
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.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
DOI: 10.4230/DagRep.2.9.200
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.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
DOI: 10.4230/DagSemProc.09391.1
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.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
DOI: 10.4230/DagSemProc.09391.2
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.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
DOI: 10.4230/DagSemProc.09391.3
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.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
DOI: 10.4230/DagSemProc.09391.4
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.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
DOI: 10.4230/DagSemProc.09391.5
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.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
DOI: 10.4230/DagSemProc.06391.1
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.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
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}
}
  • Refine by Type
  • 38 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2023
  • 1 2016
  • 1 2013
  • 5 2009
  • Show More...

  • 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 Series/Journal
  • 5 LIPIcs
  • 1 TGDK
  • 2 DagRep
  • 6 DagSemRep
  • 24 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Computing methodologies → Machine learning
  • 1 Computing methodologies → Natural language processing
  • 1 Computing methodologies → Philosophical/theoretical foundations of artificial intelligence
  • 1 Mathematics of computing → Combinatorial optimization
  • Show More...

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

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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