12 Search Results for "Thomson, Paul"


Document
Building a Digital Health Twin for Personalized Intervention: The EPI Project

Authors: Jamila Alsayed Kassem, Corinne Allaart, Saba Amiri, Milen Kebede, Tim Müller, Rosanne Turner, Adam Belloum, L. Thomas van Binsbergen, Peter Grunwald, Aart van Halteren, Paola Grosso, Cees de Laat, and Sander Klous

Published in: OASIcs, Volume 124, Commit2Data (2024)


Abstract
The Enabling Personalized Interventions (EPI) project, part of the COMMIT2DATA top sector initiative, brings together research on data science, software-defined network infrastructure, and secure and trustworthy data sharing, executed within the healthcare domain. The project applies the digital twin paradigm, in which data science-driven algorithms monitor and perform functions on a digital counterpart of a real-world entity, to enable proactive responses based on predicted outcomes. The EPI project applies this paradigm in the healthcare context by developing and testing applications that can act as personalized digital health twins for self/-joint management. The EPI project addresses several challenges to digital twin applications in the healthcare domain, such as: 1) strict health data sharing policies often lead to data being locked in silos, 2) legal, policy and privacy requirements make data processing increasingly more complex, and 3) significant limitations on infrastructure resources may apply. In this paper, we report on the use cases the EPI used as the basis to develop possible solutions to these challenges. In particular, we describe algorithms and tools for algorithmic real-time response and analysis of distributed data at scale. We discuss the automatic enforcement of legal interpretations and data-sharing conditions as executable policies. Finally, we investigate infrastructural challenges by implementing and experimenting with the EPI Framework - consisting of a distributed analysis infrastructure and BRANE for orchestrating multi-site applications. We conclude by describing our Proof of Concept (PoC) and showing its application to one of the EPI use cases.

Cite as

Jamila Alsayed Kassem, Corinne Allaart, Saba Amiri, Milen Kebede, Tim Müller, Rosanne Turner, Adam Belloum, L. Thomas van Binsbergen, Peter Grunwald, Aart van Halteren, Paola Grosso, Cees de Laat, and Sander Klous. Building a Digital Health Twin for Personalized Intervention: The EPI Project. In Commit2Data. Open Access Series in Informatics (OASIcs), Volume 124, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{alsayedkassem_et_al:OASIcs.Commit2Data.2,
  author =	{Alsayed Kassem, Jamila and Allaart, Corinne and Amiri, Saba and Kebede, Milen and M\"{u}ller, Tim and Turner, Rosanne and Belloum, Adam and van Binsbergen, L. Thomas and Grunwald, Peter and van Halteren, Aart and Grosso, Paola and de Laat, Cees and Klous, Sander},
  title =	{{Building a Digital Health Twin for Personalized Intervention: The EPI Project}},
  booktitle =	{Commit2Data},
  pages =	{2:1--2:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-351-5},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{124},
  editor =	{Haverkort, Boudewijn R. and de Jongste, Aldert and van Kuilenburg, Pieter and Vromans, Ruben D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Commit2Data.2},
  URN =		{urn:nbn:de:0030-drops-213596},
  doi =		{10.4230/OASIcs.Commit2Data.2},
  annote =	{Keywords: Healthcare, Data Sharing, Personalised Medicine, Real-time Data Analysis, Digital Health Twin, Data Policies}
}
Document
1-Planar Unit Distance Graphs

Authors: Panna Gehér and Géza Tóth

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)


Abstract
A matchstick graph is a plane graph with edges drawn as unit distance line segments. This class of graphs was introduced by Harborth who conjectured that a matchstick graph on n vertices can have at most ⌊3n-√{12n-3}⌋ edges. Recently his conjecture was settled by Lavollée and Swanepoel. In this paper we consider 1-planar unit distance graphs. We say that a graph is a 1-planar unit distance graph if it can be drawn in the plane such that all edges are drawn as unit distance line segments while each of them are involved in at most one crossing. We show that such graphs on n vertices can have at most 3n-∜{n}/10 edges.

Cite as

Panna Gehér and Géza Tóth. 1-Planar Unit Distance Graphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 6:1-6:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{geher_et_al:LIPIcs.GD.2024.6,
  author =	{Geh\'{e}r, Panna and T\'{o}th, G\'{e}za},
  title =	{{1-Planar Unit Distance Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{6:1--6:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.6},
  URN =		{urn:nbn:de:0030-drops-212900},
  doi =		{10.4230/LIPIcs.GD.2024.6},
  annote =	{Keywords: unit distance graph, 1-planar, matchstick graph}
}
Document
The Parameterized Complexity Of Extending Stack Layouts

Authors: Thomas Depian, Simon D. Fink, Robert Ganian, and Martin Nöllenburg

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)


Abstract
An 𝓁-page stack layout (also known as an 𝓁-page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into 𝓁 stacks (or pages), such that the endpoints of no two edges on the same stack alternate. We study the problem of extending a given partial 𝓁-page stack layout into a complete one, which can be seen as a natural generalization of the classical NP-hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. Our results paint a detailed and surprisingly rich complexity-theoretic landscape of the problem which includes the identification of paraNP-hard, W[1]-hard and XP-tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations.

Cite as

Thomas Depian, Simon D. Fink, Robert Ganian, and Martin Nöllenburg. The Parameterized Complexity Of Extending Stack Layouts. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.GD.2024.12,
  author =	{Depian, Thomas and Fink, Simon D. and Ganian, Robert and N\"{o}llenburg, Martin},
  title =	{{The Parameterized Complexity Of Extending Stack Layouts}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.12},
  URN =		{urn:nbn:de:0030-drops-212960},
  doi =		{10.4230/LIPIcs.GD.2024.12},
  annote =	{Keywords: Stack Layout, Drawing Extension, Parameterized Complexity, Book Embedding}
}
Document
Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor

Authors: Vida Dujmović and Camille La Rose

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)


Abstract
The rectilinear crossing number of G is the minimum number of crossings in a straight-line drawing of G. A single-crossing graph is a graph whose crossing number is at most one. We prove that every n-vertex graph G that excludes a single-crossing graph as a minor has rectilinear crossing number O(Δ n), where Δ is the maximum degree of G. This dependence on n and Δ is best possible. The result applies, for example, to K₅-minor-free graphs, and bounded treewidth graphs. Prior to our work, the only bounded degree minor-closed families known to have linear rectilinear crossing number were bounded degree graphs of bounded treewidth as well as bounded degree K_{3,3}-minor-free graphs. In the case of bounded treewidth graphs, our O(Δ n) result is again tight and it improves on the previous best known bound of O(Δ² n) by Wood and Telle, 2007.

Cite as

Vida Dujmović and Camille La Rose. Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{dujmovic_et_al:LIPIcs.GD.2024.37,
  author =	{Dujmovi\'{c}, Vida and La Rose, Camille},
  title =	{{Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.37},
  URN =		{urn:nbn:de:0030-drops-213219},
  doi =		{10.4230/LIPIcs.GD.2024.37},
  annote =	{Keywords: (rectilinear) crossing number, graph minors, maximum degree, clique-sums}
}
Document
Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem

Authors: Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)


Abstract
We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial (α,μ)-approximation is possible, i.e., a solution that with budget B+α for all B ∈ ℝ_{≥ 0} is a multiplicative μ-approximation compared to the optimum solution with budget B. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a (χ,1)-approximation, where χ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is (γ,2)-competitive where γ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a (γ,3)-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a (3χ,8)-approximation and, more generally, a ((4𝓁 - 1)χ, (2^{𝓁 + 2})/(2^𝓁 -1))-approximation for every fixed 𝓁 ∈ ℕ.

Cite as

Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz. Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ESA.2024.47,
  author =	{Disser, Yann and Griesbach, Svenja M. and Klimm, Max and Lutz, Annette},
  title =	{{Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.47},
  URN =		{urn:nbn:de:0030-drops-211188},
  doi =		{10.4230/LIPIcs.ESA.2024.47},
  annote =	{Keywords: incremental optimization, competitive analysis, prize-collecting Steiner-tree}
}
Document
Taking a Closer Look: An Outlier-Driven Approach to Compilation-Time Optimization

Authors: Florian Huemer, David Leopoldseder, Aleksandar Prokopec, Raphael Mosaner, and Hanspeter Mössenböck

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)


Abstract
Improving compilation time in optimizing compilers is challenging due to their large number of interconnected components. This includes compiler optimizations, compiler tiers, heuristics, and profiling information. Despite this complexity, research in compilation-time optimization is often guided by analyzing metrics of entire program runs, such as the total compilation time and overall memory footprint. This coarse-grained perspective hides relevant information, such as source program functions for which the compiler allocates a lot of memory or compiler optimizations with a high impact on the total compilation time. This leaves high-level metrics as the only reference point for driving optimization design. Consequently, compilation-time regressions in one program function that are obscured by improvements in other functions stay undetected, while the impacts of compiler changes on untouched parts of the compiler are mainly unknown. Furthermore, developers overlook long-standing compiler defects because their high-level metrics do not change over time. To address these limitations, we propose ICON, a new data-driven approach to compilation-time optimization that breaks up high-level metrics into individual source program functions, compiler optimizations, or even into individual instructions in the compiler source code. Our methodology enables an iterative in-depth compilation-time analysis, focusing on outliers to identify optimization opportunities. We show that outliers, both in terms of time spent in a particular compiler optimization, and in terms of individual compilations that take substantially longer, can reveal potential problems in the compiler implementation. We applied our approach to GraalVM and extracted data for multiple of its language runtimes. We analyzed the resulting data, present the first detailed look into the distribution of compilation time in the GraalVM compiler, a state-of-the-art multi-language compiler, and identified defects that led to regressions in overall compilation time or the compilation time of specific languages. We furthermore designed two optimizations based on the identified outliers that improve compilation time between 2.25% and 9.45%. We believe that our approach can guide compiler developers in finding usually overlooked optimization potential and defects, and focus future research efforts in making compilers more efficient.

Cite as

Florian Huemer, David Leopoldseder, Aleksandar Prokopec, Raphael Mosaner, and Hanspeter Mössenböck. Taking a Closer Look: An Outlier-Driven Approach to Compilation-Time Optimization. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 20:1-20:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{huemer_et_al:LIPIcs.ECOOP.2024.20,
  author =	{Huemer, Florian and Leopoldseder, David and Prokopec, Aleksandar and Mosaner, Raphael and M\"{o}ssenb\"{o}ck, Hanspeter},
  title =	{{Taking a Closer Look: An Outlier-Driven Approach to Compilation-Time Optimization}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{20:1--20:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.20},
  URN =		{urn:nbn:de:0030-drops-208693},
  doi =		{10.4230/LIPIcs.ECOOP.2024.20},
  annote =	{Keywords: Compilation time, outliers, dynamic languages, virtual machines, GraalVM, ICON}
}
Document
Failure Transparency in Stateful Dataflow Systems

Authors: Aleksey Veresov, Jonas Spenger, Paris Carbone, and Philipp Haller

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)


Abstract
Failure transparency enables users to reason about distributed systems at a higher level of abstraction, where complex failure-handling logic is hidden. This is especially true for stateful dataflow systems, which are the backbone of many cloud applications. In particular, this paper focuses on proving failure transparency in Apache Flink, a popular stateful dataflow system. Even though failure transparency is a critical aspect of Apache Flink, to date it has not been formally proven. Showing that the failure transparency mechanism is correct, however, is challenging due to the complexity of the mechanism itself. Nevertheless, this complexity can be effectively hidden behind a failure transparent programming interface. To show that Apache Flink is failure transparent, we model it in small-step operational semantics. Next, we provide a novel definition of failure transparency based on observational explainability, a concept which relates executions according to their observations. Finally, we provide a formal proof of failure transparency for the implementation model; i.e., we prove that the failure-free model correctly abstracts from the failure-related details of the implementation model. We also show liveness of the implementation model under a fair execution assumption. These results are a first step towards a verified stack for stateful dataflow systems.

Cite as

Aleksey Veresov, Jonas Spenger, Paris Carbone, and Philipp Haller. Failure Transparency in Stateful Dataflow Systems. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 42:1-42:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{veresov_et_al:LIPIcs.ECOOP.2024.42,
  author =	{Veresov, Aleksey and Spenger, Jonas and Carbone, Paris and Haller, Philipp},
  title =	{{Failure Transparency in Stateful Dataflow Systems}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{42:1--42:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.42},
  URN =		{urn:nbn:de:0030-drops-208911},
  doi =		{10.4230/LIPIcs.ECOOP.2024.42},
  annote =	{Keywords: Failure transparency, stateful dataflow, operational semantics, checkpoint recovery}
}
Document
The Complexity of Symmetry Breaking Beyond Lex-Leader

Authors: Markus Anders, Sofia Brenner, and Gaurav Rattan

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)


Abstract
Symmetry breaking is a widely popular approach to enhance solvers in constraint programming, such as those for SAT or MIP. Symmetry breaking predicates (SBPs) typically impose an order on variables and single out the lexicographic leader (lex-leader) in each orbit of assignments. Although it is NP-hard to find complete lex-leader SBPs, incomplete lex-leader SBPs are widely used in practice. In this paper, we investigate the complexity of computing complete SBPs, lex-leader or otherwise, for SAT. Our main result proves a natural barrier for efficiently computing SBPs: efficient certification of graph non-isomorphism. Our results explain the difficulty of obtaining short SBPs for important CP problems, such as matrix-models with row-column symmetries and graph generation problems. Our results hold even when SBPs are allowed to introduce additional variables. We show polynomial upper bounds for breaking certain symmetry groups, namely automorphism groups of trees and wreath products of groups with efficient SBPs.

Cite as

Markus Anders, Sofia Brenner, and Gaurav Rattan. The Complexity of Symmetry Breaking Beyond Lex-Leader. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{anders_et_al:LIPIcs.CP.2024.3,
  author =	{Anders, Markus and Brenner, Sofia and Rattan, Gaurav},
  title =	{{The Complexity of Symmetry Breaking Beyond Lex-Leader}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.3},
  URN =		{urn:nbn:de:0030-drops-206881},
  doi =		{10.4230/LIPIcs.CP.2024.3},
  annote =	{Keywords: symmetry breaking, boolean satisfiability, matrix models, graph isomorphism}
}
Document
Track A: Algorithms, Complexity and Games
Lower Bounds on 0-Extension with Steiner Nodes

Authors: Yu Chen and Zihan Tan

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
In the 0-Extension problem, we are given an edge-weighted graph G = (V,E,c), a set T ⊆ V of its vertices called terminals, and a semi-metric D over T, and the goal is to find an assignment f of each non-terminal vertex to a terminal, minimizing the sum, over all edges (u,v) ∈ E, the product of the edge weight c(u,v) and the distance D(f(u),f(v)) between the terminals that u,v are mapped to. Current best approximation algorithms on 0-Extension are based on rounding a linear programming relaxation called the semi-metric LP relaxation. The integrality gap of this LP, is upper bounded by O(log|T|/log log|T|) and lower bounded by Ω((log|T|)^{2/3}), has been shown to be closely related to the quality of cut and flow vertex sparsifiers. We study a variant of the 0-Extension problem where Steiner vertices are allowed. Specifically, we focus on the integrality gap of the same semi-metric LP relaxation to this new problem. Following from previous work, this new integrality gap turns out to be closely related to the quality achievable by cut/flow vertex sparsifiers with Steiner nodes, a major open problem in graph compression. We show that the new integrality gap stays superconstant Ω(log log |T|) even if we allow a super-linear O(|T|log^{1-ε}|T|) number of Steiner nodes.

Cite as

Yu Chen and Zihan Tan. Lower Bounds on 0-Extension with Steiner Nodes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2024.47,
  author =	{Chen, Yu and Tan, Zihan},
  title =	{{Lower Bounds on 0-Extension with Steiner Nodes}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{47:1--47:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.47},
  URN =		{urn:nbn:de:0030-drops-201905},
  doi =		{10.4230/LIPIcs.ICALP.2024.47},
  annote =	{Keywords: Graph Algorithms, Zero Extension, Integrality Gap}
}
Document
Track A: Algorithms, Complexity and Games
NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials

Authors: Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
An s-sparse polynomial has at most s monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial f is equivalent to (i.e., in the orbit of) some s-sparse polynomial. In other words, given f ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-3 arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest s₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{1/3 - ε} is NP-hard for any ε > 0; observe that s-factor approximation is trivial as the input is s-sparse. Finally, we show that for any constant σ ≥ 6, checking if a polynomial (given in sparse representation) is in the orbit of some support-σ polynomial is NP-hard. Support of a polynomial f is the maximum number of variables present in any monomial of f. These results are obtained via direct reductions from the 3-SAT problem.

Cite as

Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16,
  author =	{Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit},
  title =	{{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16},
  URN =		{urn:nbn:de:0030-drops-201598},
  doi =		{10.4230/LIPIcs.ICALP.2024.16},
  annote =	{Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT}
}
Document
Experience Report
Putting Randomized Compiler Testing into Production (Experience Report)

Authors: Alastair F. Donaldson, Hugues Evrard, and Paul Thomson

Published in: LIPIcs, Volume 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020)


Abstract
We describe our experience over the last 18 months on a compiler testing technology transfer project: taking the GraphicsFuzz research project on randomized metamorphic testing of graphics shader compilers, and building the necessary tooling around it to provide a highly automated process for improving the Khronos Vulkan Conformance Test Suite (CTS) with test cases that expose fuzzer-found compiler bugs, or that plug gaps in test coverage. We present this tooling for test automation - gfauto - in detail, as well as our use of differential coverage and test case reduction as a method for automatically synthesizing tests that fill coverage gaps. We explain the value that GraphicsFuzz has provided in automatically testing the ecosystem of tools for transforming, optimizing and validating Vulkan shaders, and the challenges faced when testing a tool ecosystem rather than a single tool. We discuss practical issues associated with putting automated metamorphic testing into production, related to test case validity, bug de-duplication and floating-point precision, and provide illustrative examples of bugs found during our work.

Cite as

Alastair F. Donaldson, Hugues Evrard, and Paul Thomson. Putting Randomized Compiler Testing into Production (Experience Report). In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 22:1-22:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{donaldson_et_al:LIPIcs.ECOOP.2020.22,
  author =	{Donaldson, Alastair F. and Evrard, Hugues and Thomson, Paul},
  title =	{{Putting Randomized Compiler Testing into Production}},
  booktitle =	{34th European Conference on Object-Oriented Programming (ECOOP 2020)},
  pages =	{22:1--22:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-154-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{166},
  editor =	{Hirschfeld, Robert and Pape, Tobias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.22},
  URN =		{urn:nbn:de:0030-drops-131791},
  doi =		{10.4230/LIPIcs.ECOOP.2020.22},
  annote =	{Keywords: Compilers, metamorphic testing, 3D graphics, experience report}
}
Document
Artifact
Putting Randomized Compiler Testing into Production (Artifact)

Authors: Alastair F. Donaldson, Hugues Evrard, and Paul Thomson

Published in: DARTS, Volume 6, Issue 2, Special Issue of the 34th European Conference on Object-Oriented Programming (ECOOP 2020)


Abstract
This artifact accompanies our experience report for our compiler testing technology transfer project: taking the GraphicsFuzz research project on randomized metamorphic testing of graphics shader compilers, and building the necessary tooling around it to provide a highly automated process for improving the Khronos Vulkan Conformance Test Suite (CTS) with test cases that expose fuzzer-found compiler bugs, or that plug gaps in test coverage. The artifact consists of two Dockerfiles and associated files that can be used to build two Docker containers. The containers include our main tool for performing fuzzing: gfauto. The containers allow the user to fuzz SwiftShader, a software Vulkan implementation, finding 4 bugs. The user will also perform some line coverage analysis of SwiftShader using our tools to synthesize a small test that increases line coverage. Ubuntu, gfauto, SwiftShader, and other dependencies inside the Docker containers are fixed at specific versions, and all random seeds are set to specific values. Thus, all examples should reproduce faithfully on any machine.

Cite as

Alastair F. Donaldson, Hugues Evrard, and Paul Thomson. Putting Randomized Compiler Testing into Production (Artifact). In Special Issue of the 34th European Conference on Object-Oriented Programming (ECOOP 2020). Dagstuhl Artifacts Series (DARTS), Volume 6, Issue 2, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@Article{donaldson_et_al:DARTS.6.2.3,
  author =	{Donaldson, Alastair F. and Evrard, Hugues and Thomson, Paul},
  title =	{{Putting Randomized Compiler Testing into Production (Artifact)}},
  pages =	{3:1--3:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2020},
  volume =	{6},
  number =	{2},
  editor =	{Donaldson, Alastair F. and Evrard, Hugues and Thomson, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.6.2.3},
  URN =		{urn:nbn:de:0030-drops-132005},
  doi =		{10.4230/DARTS.6.2.3},
  annote =	{Keywords: Compilers, metamorphic testing, 3D graphics, experience report}
}
  • Refine by Author
  • 2 Donaldson, Alastair F.
  • 2 Evrard, Hugues
  • 2 Thomson, Paul
  • 1 Allaart, Corinne
  • 1 Alsayed Kassem, Jamila
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graphs and surfaces
  • 2 Software and its engineering → Compilers
  • 2 Software and its engineering → Software testing and debugging
  • 1 General and reference → Measurement
  • 1 General and reference → Performance
  • Show More...

  • Refine by Keyword
  • 2 3D graphics
  • 2 Compilers
  • 2 experience report
  • 2 metamorphic testing
  • 1 (rectilinear) crossing number
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 10 2024
  • 2 2020

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