DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2026.39

Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions

Authors: Keerti Choudhary, Amit Kumar, and Lakshay Saggi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We study the 2-Disjoint Shortest Paths (2-DSP) problem: given a directed weighted graph and two terminal pairs (s₁,t₁) and (s₂,t₂), decide whether there exist vertex-disjoint shortest paths between each pair. Building on recent advances in disjoint shortest paths for DAGs and undirected graphs (Akmal et al. 2024), we present an O(mn log n)-time algorithm for this problem in weighted directed graphs that do not contain negative or zero weight cycles. This algorithm presents a significant improvement over the previously known O(m⁵n)-time bound (Berczi et al. 2017). Our approach exploits the algebraic structure of polynomials that enumerate shortest paths between terminal pairs. A key insight is that these polynomials admit a recursive decomposition, enabling efficient evaluation via dynamic programming over fields of characteristic two. Furthermore, we demonstrate how to report the corresponding paths in O(mn² log n)-time. In addition, we extend our techniques to a more general setting: given two terminal pairs (s₁, t₁) and (s₂, t₂) in a directed graph, find the minimum possible number of vertex intersections between any shortest path from s₁ to t₁ and s₂ to t₂. We call this the Minimum 2-Disjoint Shortest Paths (Min-2-DSP) problem. We provide in this paper the first efficient algorithm for this problem, including an O(m² n³)-time algorithm for directed graphs with positive edge weights, and an O(m+n)-time algorithm for DAGs and undirected graphs. Moreover, if the number of intersecting vertices is at least one, we show that it is possible to report the paths in the same O(m+n)-time. This is somewhat surprising, as there is no known o(mn) time algorithm for explicitly reporting the paths if they are vertex-disjoint, and is left as an open problem in (Akmal et al. 2024).

Cite as

Keerti Choudhary, Amit Kumar, and Lakshay Saggi. Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.ITCS.2026.39,
  author =	{Choudhary, Keerti and Kumar, Amit and Saggi, Lakshay},
  title =	{{Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{39:1--39:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.39},
  URN =		{urn:nbn:de:0030-drops-253267},
  doi =		{10.4230/LIPIcs.ITCS.2026.39},
  annote =	{Keywords: Disjoint paths, Disjoint shortest paths, Algebraic graph algorithms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.5

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs

Authors: Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

This paper addresses the problem of designing fault-tolerant data structures for the (s,t)-max-flow and (s,t)-min-cut problems in unweighted directed graphs. Given a directed graph G = (V, E) with a designated source s, sink t, and an (s,t)-max-flow of value λ, we present constructions for max-flow and min-cut sensitivity oracles, and introduce the concept of a fault-tolerant flow family, which may be of independent interest. Our main contributions are as follows. 1) Fault-Tolerant Flow Family: We construct a family ℬ of 2λ+1 (s,t)-flows such that for every edge e, ℬ contains an (s,t)-max-flow of G-e. This covering property is tight up to constants for single failures and provably cannot extend to comparably small families for k ≥ 2, where we show an Ω(n) lower bound on the family size, independent of λ. 2) Max-Flow Sensitivity Oracle: Using the fault-tolerant flow family, we construct a single as well as dual-edge sensitivity oracle for (s,t)-max-flow that requires only O(λ n) space. Given any set F of up to two failing edges, the oracle reports the updated max-flow value in G-F in O(n) time. Additionally, for the single-failure case, the oracle can determine in constant time whether the flow through an edge x changes when another edge e fails. 3) Min-Cut Sensitivity Oracle for Dual Failures: Recently, Baswana et al. (ICALP’22) designed an O(n²)-sized oracle for answering (s,t)-min-cut size queries under dual edge failures in constant time, along with a matching lower bound. We extend this by focusing on graphs with small min-cut values λ, and present a more compact oracle of size O(λ n) that answers such min-cut size queries in constant time and reports the corresponding (s,t)-min-cut partition in O(n) time. We also show that the space complexity of our oracle is asymptotically optimal in this setting. 4) Min-Cut Sensitivity Oracle for Multiple Failures: We extend our results to the general case of k edge failures. For any graph with (s,t)-min-cut of size λ, we construct a k-fault-tolerant min-cut oracle with space complexity O_{λ,k}(n log n) that answers min-cut size queries in O_{λ,k}(log n) time. This also leads to improved fault-tolerant (s,t)-reachability oracles, achieving O(n log n) space and O(log n) query time for up to k = O(1) edge failures.

Cite as

Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi. Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahi_et_al:LIPIcs.ITCS.2026.5,
  author =	{Ahi, Mridul and Choudhary, Keerti and Pande, Shlok and Pushpraj and Saggi, Lakshay},
  title =	{{Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.5},
  URN =		{urn:nbn:de:0030-drops-252920},
  doi =		{10.4230/LIPIcs.ITCS.2026.5},
  annote =	{Keywords: Fault tolerance, Data structures, Minimum cuts, Maximum flows}
}

Document

DOI: 10.4230/LIPIcs.DNA.31.1

Algorithmic Hardness of the Partition Function for Nucleic Acid Strands

Authors: Gwendal Ducloz, Ahmed Shalaby, and Damien Woods

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract

To understand and engineer biological and artificial nucleic acid systems, algorithms are employed for prediction of secondary structures at thermodynamic equilibrium. Dynamic programming algorithms are used to compute the most favoured, or Minimum Free Energy (MFE), structure, and the Partition Function (PF) - a tool for assigning a probability to any structure. However, in some situations, such as when there are large numbers of strands, or pseudoknotted systems, NP-hardness results show that such algorithms are unlikely, but only for MFE. Curiously, algorithmic hardness results were not shown for PF, leaving two open questions on the complexity of PF for multiple strands and single strands with pseudoknots. The challenge is that while the MFE problem cares only about one, or a few structures, PF is a summation over the entire secondary structure space, giving theorists the vibe that computing PF should not only be as hard as MFE, but should be even harder. We answer both questions. First, we show that computing PF is #P-hard for systems with an unbounded number of strands, answering a question of Condon Hajiaghayi, and Thachuk [DNA27]. Second, for even a single strand, but allowing pseudoknots, we find that PF is #P-hard. Our proof relies on a novel magnification trick that leads to a tightly-woven set of reductions between five key thermodynamic problems: MFE, PF, their decision versions, and #SSEL that counts structures of a given energy. Our reductions show these five problems are fundamentally related for any energy model amenable to magnification. That general classification clarifies the mathematical landscape of nucleic acid energy models and yields several open questions.

Cite as

Gwendal Ducloz, Ahmed Shalaby, and Damien Woods. Algorithmic Hardness of the Partition Function for Nucleic Acid Strands. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ducloz_et_al:LIPIcs.DNA.31.1,
  author =	{Ducloz, Gwendal and Shalaby, Ahmed and Woods, Damien},
  title =	{{Algorithmic Hardness of the Partition Function for Nucleic Acid Strands}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.1},
  URN =		{urn:nbn:de:0030-drops-238504},
  doi =		{10.4230/LIPIcs.DNA.31.1},
  annote =	{Keywords: Partition function, minimum free energy, nucleic acid, DNA, RNA, secondary structure, computational complexity, #P-hardness}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.36

Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.

Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.66

Graph Reconstruction via MIS Queries

Authors: Christian Konrad, Conor O'Sullivan, and Victor Traistaru

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G = (V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle’s answers. Angluin and Chen [Journal of Computer and System Sciences, 2008] resolved the number of Independent Set (IS) queries necessary and sufficient for GR on m-edge graphs. In this setting, each query consists of a subset of vertices U ⊆ V, and the oracle responds with a boolean, indicating whether U is an independent set in G. They gave algorithms that use O(m ⋅ log n) IS queries, which is best possible. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of IS queries. Given a query U ⊆ V, the oracle responds with any, potentially adversarially chosen, maximal independent set I ⊆ U in the induced subgraph G[U]. We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Δ of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1) We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Δ² ⋅ log n) queries and succeeds with high probability. This should be contrasted with the fact that Ω(Δ ⋅ n ⋅ log(n/Δ)) IS queries are required for such graphs, which shows that MIS queries are strictly more powerful than IS queries. Interestingly, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Δ³ ⋅ log(n/Δ)) queries. 2) Regarding lower bounds, we prove that the additional Δ factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Ω(Δ³ / log² Δ) queries. For arbitrary randomized adaptive algorithms, we show that Ω(Δ²) queries are necessary in graphs of maximum degree Δ, and that Ω(log n) queries are necessary, even when the input graph is an n-vertex cycle.

Cite as

Christian Konrad, Conor O'Sullivan, and Victor Traistaru. Graph Reconstruction via MIS Queries. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ITCS.2025.66,
  author =	{Konrad, Christian and O'Sullivan, Conor and Traistaru, Victor},
  title =	{{Graph Reconstruction via MIS Queries}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{66:1--66:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.66},
  URN =		{urn:nbn:de:0030-drops-226945},
  doi =		{10.4230/LIPIcs.ITCS.2025.66},
  annote =	{Keywords: Query Complexity, Graph Reconstruction, Maximal Independent Set Queries}
}

Document

DOI: 10.4230/OASIcs.EVCS.2023.19

Eelco Visser as a Founding Member of the IFIP WG 2.11

Authors: Christian Lengauer and Jacques Carette

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract

Appreciation of Eelco Visser’s contribution to the IFIP WG 2.11 by two of its chairs. Christian Lengauer was chair from 2007 to 2013. Jacques Carette has been chair since 2019.

Cite as

Christian Lengauer and Jacques Carette. Eelco Visser as a Founding Member of the IFIP WG 2.11. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 19:1-19:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lengauer_et_al:OASIcs.EVCS.2023.19,
  author =	{Lengauer, Christian and Carette, Jacques},
  title =	{{Eelco Visser as a Founding Member of the IFIP WG 2.11}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{19:1--19:3},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.19},
  URN =		{urn:nbn:de:0030-drops-177891},
  doi =		{10.4230/OASIcs.EVCS.2023.19},
  annote =	{Keywords: IFIP WG 2.11}
}

Document

DOI: 10.4230/DagRep.10.3.58

Tensor Computations: Applications and Optimization (Dagstuhl Seminar 20111)

Authors: Paolo Bientinesi, David Ham, Furong Huang, Paul H. J. Kelly, Christian Lengauer, and Saday Sadayappan

Published in: Dagstuhl Reports, Volume 10, Issue 3 (2020)

Abstract

Tensors are higher-dimensional analogs of matrices, and represent a key data abstraction for many applications in computational science and data science. In contrast to the wide availability on diverse hardware platforms of high-performance numerical libraries for matrix computations, only limited software infrastructure exists today for high-performance tensor computations. Recent research developments have resulted in the formulation of many machine learning algorithms in terms of tensor computations. Tensor computations have also emerged as fundamental building blocks for many algorithms in data science and computational science. Therefore, several concurrent efforts have targeted the development of libraries, frameworks, and domain-specific compilers to support the rising demand for high-performance tensor computations. However, there is currently very little coordination among the various groups of developers. Further, the groups developing high-performance libraries/frameworks for tensor computations are still rather disconnected from the research community that develops applications using tensors as a key data abstraction. The main goal of this Dagstuhl Seminar has been to bring together the following two communities: first researchers from disciplines developing applications centered around tensor computations, and second researchers developing software infrastructure for efficient tensor computation primitives. Invitees from the former group included experts in machine learning and data analytics, and computational scientists developing tensor-based applications. Invitees from the latter group spanned experts in compiler optimization and experts in numerical methods. A very fruitful exchange of ideas across these four research communities took place, with discussions on the variety of needs and use-cases for tensor computations and the challenges/opportunities in the development of high-performance software to satisfy those needs.

Cite as

Paolo Bientinesi, David Ham, Furong Huang, Paul H. J. Kelly, Christian Lengauer, and Saday Sadayappan. Tensor Computations: Applications and Optimization (Dagstuhl Seminar 20111). In Dagstuhl Reports, Volume 10, Issue 3, pp. 58-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{bientinesi_et_al:DagRep.10.3.58,
  author =	{Bientinesi, Paolo and Ham, David and Huang, Furong and Kelly, Paul H. J. and Lengauer, Christian and Sadayappan, Saday},
  title =	{{Tensor Computations: Applications and Optimization (Dagstuhl Seminar 20111)}},
  pages =	{58--70},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{10},
  number =	{3},
  editor =	{Bientinesi, Paolo and Ham, David and Huang, Furong and Kelly, Paul H. J. and Lengauer, Christian and Sadayappan, Saday},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.10.3.58},
  URN =		{urn:nbn:de:0030-drops-134303},
  doi =		{10.4230/DagRep.10.3.58},
  annote =	{Keywords: compilers, computational science, linear algebra, machine learning, numerical methods}
}

Document

DOI: 10.4230/DagRep.8.3.39

Loop Optimization (Dagstuhl Seminar 18111)

Authors: Sebastian Hack, Paul H. J. Kelly, and Christian Lengauer

Published in: Dagstuhl Reports, Volume 8, Issue 3 (2018)

Abstract

This report documents the programme of Dagstuhl Seminar 18111 "Loop Optimization". The seminar brought together experts from three areas: (1) model-based loop optimization, chiefly, in the polyhedron model, (2) rewriting and program transformation, and (3) metaprogramming and symbolic evaluation. Its aim was to review the 20+ years of progress since the Dagstuhl Seminar 9616 "Loop Parallelization" in 1996 and identify the challenges that remain.

Cite as

Sebastian Hack, Paul H. J. Kelly, and Christian Lengauer. Loop Optimization (Dagstuhl Seminar 18111). In Dagstuhl Reports, Volume 8, Issue 3, pp. 39-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{hack_et_al:DagRep.8.3.39,
  author =	{Hack, Sebastian and Kelly, Paul H. J. and Lengauer, Christian},
  title =	{{Loop Optimization (Dagstuhl Seminar 18111)}},
  pages =	{39--59},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{3},
  editor =	{Hack, Sebastian and Kelly, Paul H. J. and Lengauer, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.3.39},
  URN =		{urn:nbn:de:0030-drops-92960},
  doi =		{10.4230/DagRep.8.3.39},
  annote =	{Keywords: Autotuning, dependence analysis, just-in-time (JIT), loop parallelization, parallel programming, polyhedron model}
}

Document

DOI: 10.4230/DagRep.5.4.56

Advanced Stencil-Code Engineering (Dagstuhl Seminar 15161)

Authors: Christian Lengauer, Matthias Bolten, Robert D. Falgout, and Olaf Schenk

Published in: Dagstuhl Reports, Volume 5, Issue 4 (2015)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 15161 "Advanced Stencil-Code Engineering". The seminar was hosted by the DFG project with the same name (ExaStencils for short) in the DFG priority programme "Software for Exascale Computing" (SPPEXA). It brought together experts from mathematics, computer science and applications to explore the challenges of very high performance and massive parallelism in solving partial differential equations. Its aim was to lay the basis for a new interdisciplinary research community on high-performance stencil codes.

Cite as

Christian Lengauer, Matthias Bolten, Robert D. Falgout, and Olaf Schenk. Advanced Stencil-Code Engineering (Dagstuhl Seminar 15161). In Dagstuhl Reports, Volume 5, Issue 4, pp. 56-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{lengauer_et_al:DagRep.5.4.56,
  author =	{Lengauer, Christian and Bolten, Matthias and Falgout, Robert D. and Schenk, Olaf},
  title =	{{Advanced Stencil-Code Engineering (Dagstuhl Seminar 15161)}},
  pages =	{56--75},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{4},
  editor =	{Lengauer, Christian and Bolten, Matthias and Falgout, Robert D. and Schenk, Olaf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.4.56},
  URN =		{urn:nbn:de:0030-drops-53503},
  doi =		{10.4230/DagRep.5.4.56},
  annote =	{Keywords: Code generation, domain-specific languages, exascale computing, high-performance computing, massive parallelism, multigrid, partial differential equations, program optimization, program parallelization, stencil codes}
}

Document

DOI: 10.4230/DagSemProc.07361.1

07361 Abstracts Collection – Programming Models for Ubiquitous Parallelism

Authors: David Chi-Leung Wong, Albert Cohen, María J. Garzarán, Christian Lengauer, and Samuel P. Midkiff

Published in: Dagstuhl Seminar Proceedings, Volume 7361, Programming Models for Ubiquitous Parallelism (2008)

Abstract

From 02.09. to 07.09.2007, the Dagstuhl Seminar 07361 ``Programming Models for Ubiquitous Parallelism'' 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

David Chi-Leung Wong, Albert Cohen, María J. Garzarán, Christian Lengauer, and Samuel P. Midkiff. 07361 Abstracts Collection – Programming Models for Ubiquitous Parallelism. In Programming Models for Ubiquitous Parallelism. Dagstuhl Seminar Proceedings, Volume 7361, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{wong_et_al:DagSemProc.07361.1,
  author =	{Wong, David Chi-Leung and Cohen, Albert and Garzar\'{a}n, Mar{\'\i}a J. and Lengauer, Christian and Midkiff, Samuel P.},
  title =	{{07361 Abstracts Collection – Programming Models for Ubiquitous Parallelism}},
  booktitle =	{Programming Models for Ubiquitous Parallelism},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7361},
  editor =	{Albert Cohen and Mar{\'\i}a J. Garzar\'{a}n and Christian Lengauer and Samuel P. Midkiff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07361.1},
  URN =		{urn:nbn:de:0030-drops-13770},
  doi =		{10.4230/DagSemProc.07361.1},
  annote =	{Keywords: Parallel programming models, transactional memory, languages, compilers, optimizations, architecture, automatic parallelization}
}

Document

DOI: 10.4230/DagSemProc.07361.2

07361 Introduction – Programming Models for Ubiquitous Parallelism

Authors: David Chi-Leung Wong, Albert Cohen, María J. Garzarán, Christian Lengauer, and Samuel P. Midkiff

Published in: Dagstuhl Seminar Proceedings, Volume 7361, Programming Models for Ubiquitous Parallelism (2008)

Abstract

The goal of the seminar is to present a broad view of the research challenges and ongoing efforts to improve productivity, scalability, efficiency and reliability of general-purpose and embedded parallel programming.

Cite as

David Chi-Leung Wong, Albert Cohen, María J. Garzarán, Christian Lengauer, and Samuel P. Midkiff. 07361 Introduction – Programming Models for Ubiquitous Parallelism. In Programming Models for Ubiquitous Parallelism. Dagstuhl Seminar Proceedings, Volume 7361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{wong_et_al:DagSemProc.07361.2,
  author =	{Wong, David Chi-Leung and Cohen, Albert and Garzar\'{a}n, Mar{\'\i}a J. and Lengauer, Christian and Midkiff, Samuel P.},
  title =	{{07361 Introduction – Programming Models for Ubiquitous Parallelism}},
  booktitle =	{Programming Models for Ubiquitous Parallelism},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7361},
  editor =	{Albert Cohen and Mar{\'\i}a J. Garzar\'{a}n and Christian Lengauer and Samuel P. Midkiff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07361.2},
  URN =		{urn:nbn:de:0030-drops-13736},
  doi =		{10.4230/DagSemProc.07361.2},
  annote =	{Keywords: Programming Models for Ubiquitous Parallelism}
}

Document

DOI: 10.4230/DagSemProc.07361.3

A Case for Deconstructing Hardware Transactional Memory Systems

Authors: Mark D. Hill, Derek Hower, Kevin E. Moore, Michael M. Swift, Haris Volos, and David A. Wood

Published in: Dagstuhl Seminar Proceedings, Volume 7361, Programming Models for Ubiquitous Parallelism (2008)

Abstract

Major hardware and software vendors are curious about transactional memory (TM), but are understandably cautious about committing to hardware changes. Our thesis is that deconstructing transactional memory into separate, interchangeable components facilitates TM adoption in two ways. First, it aids hardware TM refinement, allowing vendors to adopt TM earlier, knowing that they can more easily refine aspects later. Second, it enables the components to be applied to other uses, including reliability, security, performance, and correctness, providing value even if TM is not widely used. We develop some evidence for our thesis via experience with LogTM variants and preliminary case studies of scalable watchpoints and race recording for deterministic replay.

Cite as

Mark D. Hill, Derek Hower, Kevin E. Moore, Michael M. Swift, Haris Volos, and David A. Wood. A Case for Deconstructing Hardware Transactional Memory Systems. In Programming Models for Ubiquitous Parallelism. Dagstuhl Seminar Proceedings, Volume 7361, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hill_et_al:DagSemProc.07361.3,
  author =	{Hill, Mark D. and Hower, Derek and Moore, Kevin E. and Swift, Michael M. and Volos, Haris and Wood, David A.},
  title =	{{A Case for Deconstructing Hardware Transactional Memory Systems}},
  booktitle =	{Programming Models for Ubiquitous Parallelism},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7361},
  editor =	{Albert Cohen and Mar{\'\i}a J. Garzar\'{a}n and Christian Lengauer and Samuel P. Midkiff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07361.3},
  URN =		{urn:nbn:de:0030-drops-13759},
  doi =		{10.4230/DagSemProc.07361.3},
  annote =	{Keywords: Hardware transactional memory}
}

Document

DOI: 10.4230/DagSemProc.07361.4

Parallelism through Digital Circuit Design

Authors: John O'Donnell

Published in: Dagstuhl Seminar Proceedings, Volume 7361, Programming Models for Ubiquitous Parallelism (2008)

Abstract

Two ways to exploit chips with a very large number of transistors are multicore processors and programmable logic chips. Some data parallel algorithms can be executed efficiently on ordinary parallel computers, including multicores. A class of data parallel algorithms is identified which have characteristics that make implementation on multiprocessors inefficient, but they are well suited for direct design as digital circuits. This leads to a programming model called circuit parallelism. The characteristics of circuit parallel algorithms are discussed, and a prototype system for supporting them is described.

Cite as

John O'Donnell. Parallelism through Digital Circuit Design. In Programming Models for Ubiquitous Parallelism. Dagstuhl Seminar Proceedings, Volume 7361, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{odonnell:DagSemProc.07361.4,
  author =	{O'Donnell, John},
  title =	{{Parallelism through Digital Circuit Design}},
  booktitle =	{Programming Models for Ubiquitous Parallelism},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7361},
  editor =	{Albert Cohen and Mar{\'\i}a J. Garzar\'{a}n and Christian Lengauer and Samuel P. Midkiff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07361.4},
  URN =		{urn:nbn:de:0030-drops-13724},
  doi =		{10.4230/DagSemProc.07361.4},
  annote =	{Keywords: Circuit parallelism, data parallelism, FPGA}
}

Document

DOI: 10.4230/DagSemProc.07361.5

Some Experiments on Tiling Loop Programs for Shared-Memory Multicore Architectures

Authors: Armin Größlinger

Published in: Dagstuhl Seminar Proceedings, Volume 7361, Programming Models for Ubiquitous Parallelism (2008)

Abstract

The model-based transformation of loop programs is a way of detecting fine-grained parallelism in sequential programs. One of the challenges is to agglomerate the parallelism to a coarser grain, in order to map the operations of the program to the available cores in a multicore architecture. We consider shared-memory multicores as target architecture for space-time mapped loop programs and make some observations concerning code generation, load balancing and cache effects.

Cite as

Armin Größlinger. Some Experiments on Tiling Loop Programs for Shared-Memory Multicore Architectures. In Programming Models for Ubiquitous Parallelism. Dagstuhl Seminar Proceedings, Volume 7361, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{grolinger:DagSemProc.07361.5,
  author =	{Gr\"{o}{\ss}linger, Armin},
  title =	{{Some Experiments on Tiling Loop Programs for Shared-Memory Multicore Architectures}},
  booktitle =	{Programming Models for Ubiquitous Parallelism},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7361},
  editor =	{Albert Cohen and Mar{\'\i}a J. Garzar\'{a}n and Christian Lengauer and Samuel P. Midkiff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07361.5},
  URN =		{urn:nbn:de:0030-drops-13748},
  doi =		{10.4230/DagSemProc.07361.5},
  annote =	{Keywords: Multicore, automatic parallelization, loop transformations, polyhedron model}
}

Document

DOI: 10.4230/DagSemRep.373

Domain-Specific Program Generation (Dagstuhl Seminar 03131)

Authors: Don Batory, Charles Consel, Christian Lengauer, and Martin Odersky

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

Abstract

Cite as

Don Batory, Charles Consel, Christian Lengauer, and Martin Odersky. Domain-Specific Program Generation (Dagstuhl Seminar 03131). Dagstuhl Seminar Report 373, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{batory_et_al:DagSemRep.373,
  author =	{Batory, Don and Consel, Charles and Lengauer, Christian and Odersky, Martin},
  title =	{{Domain-Specific Program Generation (Dagstuhl Seminar 03131)}},
  pages =	{1--8},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{373},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.373},
  URN =		{urn:nbn:de:0030-drops-152531},
  doi =		{10.4230/DagSemRep.373},
}

21 Search Results for "Lengauer, Christian"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message