37 Search Results for "Probst, Christian W."

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.60
Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation

Authors: Yannic Maus and Tijn de Vos

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We give new, improved bounds for approximating the sparsest cut value or in other words the conductance ϕ of a graph in the CONGEST model. As our main result, we present an algorithm running in O(log² n/ϕ) rounds in which every vertex outputs a value ̃ ϕ satisfying ϕ ≤ ̃ ϕ ≤ √{2.01ϕ}. In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to k-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix L: = I-Deg^{-1/2}ADeg^ {-1/2}, where, A is the adjacency matrix and Deg is the diagonal matrix with the weighted degrees on the diagonal. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of L, even in the stronger LOCAL model The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the CONGEST model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs.
Cite as

Yannic Maus and Tijn de Vos. Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 60:1-60:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maus_et_al:LIPIcs.DISC.2025.60,
  author =	{Maus, Yannic and de Vos, Tijn},
  title =	{{Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{60:1--60:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.60},
  URN =		{urn:nbn:de:0030-drops-248763},
  doi =		{10.4230/LIPIcs.DISC.2025.60},
  annote =	{Keywords: CONGEST, Sparsest Cut, Laplacian, Eigenvalues, Spectral Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.26
Faster Dynamic 2-Edge Connectivity in Directed Graphs

Authors: Loukas Georgiadis, Konstantinos Giannis, and Giuseppe F. Italiano

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Let G be a directed graph with n vertices and m edges. We present a deterministic algorithm that maintains the 2-edge-connected components of G under a sequence of m edge insertions, with a total running time of O(n² log n). This significantly improves upon the previous best bound of O(mn) for graphs that are not very sparse. After each insertion, our algorithm supports the following queries with asymptotically optimal efficiency: - Test in constant time whether two query vertices v and w are 2-edge-connected in G. - Report in O(n) time all the 2-edge-connected components of G. Our approach builds on the recent framework of Georgiadis, Italiano, and Kosinas [FOCS 2024] for computing the 3-edge-connected components of a directed graph in linear time, which leverages the minset-poset technique of Gabow [TALG 2016]. Additionally, we provide a deterministic decremental algorithm for maintaining 2-edge-connectivity in strongly connected directed graphs. Given a sequence of m edge deletions, our algorithm maintains the 2-edge-connected components in total time n^(2+o(1)), while supporting the same queries as the incremental algorithm. This result assumes that the edges of a fixed spanning tree of G and of its reverse graph G^R are not deleted. Previously, the best known bound for the decremental problem was O(mn log n), obtained by a randomized algorithm without restrictions on the deletions. In contrast to prior dynamic algorithms for 2-edge-connectivity in directed graphs, our method avoids the incremental computation of dominator trees, thereby circumventing the known conditional lower bound of Ω(mn).
Cite as

Loukas Georgiadis, Konstantinos Giannis, and Giuseppe F. Italiano. Faster Dynamic 2-Edge Connectivity in Directed Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2025.26,
  author =	{Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F.},
  title =	{{Faster Dynamic 2-Edge Connectivity in Directed Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.26},
  URN =		{urn:nbn:de:0030-drops-244945},
  doi =		{10.4230/LIPIcs.ESA.2025.26},
  annote =	{Keywords: Connectivity, dynamic algorithms, directed graphs}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.12
Testing Whether a Subgraph Is Convex or Isometric

Authors: Sergio Cabello

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

Abstract
We consider the following two algorithmic problems: given a graph G and a subgraph H ⊆ G, decide whether H is an isometric or a geodesically convex subgraph of G. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with n vertices and Θ(n) edges, we cannot expect to solve the problem in O(n^{2-ε}) time for any constant ε > 0. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where G is a plane graph and H is defined by a few cycles in G.
Cite as

Sergio Cabello. Testing Whether a Subgraph Is Convex or Isometric. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cabello:LIPIcs.WADS.2025.12,
  author =	{Cabello, Sergio},
  title =	{{Testing Whether a Subgraph Is Convex or Isometric}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{12:1--12:16},
  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.12},
  URN =		{urn:nbn:de:0030-drops-242439},
  doi =		{10.4230/LIPIcs.WADS.2025.12},
  annote =	{Keywords: convex subgraph, isometric subgraph, plane graph}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.12
SAT-Metropolis: Combining Markov Chain Monte Carlo with SAT/SMT Sampling

Authors: Maja Aaslyng Dall, Raúl Pardo, Thomas Lumley, and Andrzej Wąsowski

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Probabilistic inference via Markov Chain Monte Carlo (MCMC) is at the core of statistical analysis and has a myriad of applications. However, probabilistic inference in the presence of hard constraints, so constraints that must hold with probability one, remains a difficult task. The reason is that hard constraints make the state space of the target distribution sparse, and may even divide it into disjoint areas separated by probability-zero states. As a consequence, the random walk performed by MCMC algorithms fails to effectively sample from the complete set of states in the target distribution. In this paper, we propose the use of SAT/SMT sampling to adapt a classic and widely used MCMC algorithm, namely Metropolis sampling. We use SAT/SMT samplers as proposal distributions. In this way, the algorithm ignores probability-zero states. Our method, sat-metropolis, effectively works in problems with multivariate polynomial hard constraints where regular Metropolis fails. We evaluate the convergence and scalability of sat-metropolis using three different state-of-the-art SAT/SMT samplers: SPUR, CMSGen, and MegaSampler. The evaluation shows how different features of the SAT/SMT sampling tools affect the effectiveness of probabilistic inference. We conclude that SAT/SMT sampling is a viable and promising technology for probabilistic inference under hard constraints.
Cite as

Maja Aaslyng Dall, Raúl Pardo, Thomas Lumley, and Andrzej Wąsowski. SAT-Metropolis: Combining Markov Chain Monte Carlo with SAT/SMT Sampling. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dall_et_al:LIPIcs.SAT.2025.12,
  author =	{Dall, Maja Aaslyng and Pardo, Ra\'{u}l and Lumley, Thomas and W\k{a}sowski, Andrzej},
  title =	{{SAT-Metropolis: Combining Markov Chain Monte Carlo with SAT/SMT Sampling}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.12},
  URN =		{urn:nbn:de:0030-drops-237462},
  doi =		{10.4230/LIPIcs.SAT.2025.12},
  annote =	{Keywords: SAT/SMT sampling, Probabilistic inference, Markov Chain Monte Carlo}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.10
Algorithm Engineering of SSSP with Negative Edge Weights

Authors: Alejandro Cassis, Andreas Karrenbauer, André Nusser, and Paolo Luigi Rinaldi

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Computing shortest paths is one of the most fundamental algorithmic graph problems. It is known since decades that this problem can be solved in near-linear time if all weights are nonnegative. A recent break-through by [Aaron Bernstein et al., 2022] presented a randomized near-linear time algorithm for this problem. A subsequent improvement in [Karl Bringmann et al., 2023] significantly reduced the number of logarithmic factors and thereby also simplified the algorithm. It is surprising and exciting that both of these algorithms are combinatorial and do not contain any fundamental obstacles for being practical. We launch the, to the best of our knowledge, first extensive investigation towards a practical implementation of [Karl Bringmann et al., 2023]. To this end, we give an accessible overview of the algorithm and discuss what adaptions are necessary to obtain a fast algorithm in practice. We manifest these adaptions in an efficient implementation. We test our implementation on a benchmark data set that is adapted to be more difficult for our implementation in order to allow for a fair comparison. As in [Karl Bringmann et al., 2023] as well as in our implementation there are multiple parameters to tune, we empirically evaluate their effect and thereby determine the best choices. Our implementation is then extensively compared to one of the state-of-the-art algorithms for this problem [Andrew V. Goldberg and Tomasz Radzik, 1993]. On the hardest instance type, we are faster by up to almost two orders of magnitude.
Cite as

Alejandro Cassis, Andreas Karrenbauer, André Nusser, and Paolo Luigi Rinaldi. Algorithm Engineering of SSSP with Negative Edge Weights. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cassis_et_al:LIPIcs.SEA.2025.10,
  author =	{Cassis, Alejandro and Karrenbauer, Andreas and Nusser, Andr\'{e} and Rinaldi, Paolo Luigi},
  title =	{{Algorithm Engineering of SSSP with Negative Edge Weights}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.10},
  URN =		{urn:nbn:de:0030-drops-232486},
  doi =		{10.4230/LIPIcs.SEA.2025.10},
  annote =	{Keywords: Single Source Shortest Paths, Negative Weights, Near-Linear Time}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.117
Incremental Approximate Single-Source Shortest Paths with Predictions

Authors: Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh

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

Abstract
The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing interest in leveraging predictions for designing data structures with improved beyond-worst-case running times. In this paper, we study the fundamental data structure problem of maintaining approximate shortest paths in incremental graphs in the algorithms-with-predictions model. Given a sequence σ of edges that are inserted one at a time, the goal is to maintain approximate shortest paths from the source to each vertex in the graph at each time step. Before any edges arrive, the data structure is given a prediction of the online edge sequence σ̂ which is used to "warm start" its state. As our main result, we design a learned algorithm that maintains (1+ε)-approximate single-source shortest paths, which runs in Õ(m η log W/ε) time, where W is the weight of the heaviest edge and η is the prediction error. We show these techniques immediately extend to the all-pairs shortest-path setting as well. Our algorithms are consistent (performing nearly as fast as the offline algorithm) when predictions are nearly perfect, have a smooth degradation in performance with respect to the prediction error and, in the worst case, match the best offline algorithm up to logarithmic factors. That is, the algorithms are "ideal" in the algorithms-with-predictions model. As a building block, we study the offline incremental approximate single-source shortest-path (SSSP) problem. In the offline incremental SSSP problem, the edge sequence σ is known a priori and the goal is to construct a data structure that can efficiently return the length of the shortest paths in the intermediate graph G_t consisting of the first t edges, for all t. Note that the offline incremental problem is defined in the worst-case setting (without predictions) and is of independent interest.
Cite as

Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh. Incremental Approximate Single-Source Shortest Paths with Predictions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 117:1-117:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mccauley_et_al:LIPIcs.ICALP.2025.117,
  author =	{McCauley, Samuel and Moseley, Benjamin and Niaparast, Aidin and Niaparast, Helia and Singh, Shikha},
  title =	{{Incremental Approximate Single-Source Shortest Paths with Predictions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{117:1--117: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.117},
  URN =		{urn:nbn:de:0030-drops-234946},
  doi =		{10.4230/LIPIcs.ICALP.2025.117},
  annote =	{Keywords: Algorithms with Predictions, Shortest Paths, Approximation Algorithms, Dynamic Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.16
A Lightweight Method for Generating Multi-Tier JIT Compilation Virtual Machine in a Meta-Tracing Compiler Framework

Authors: Yusuke Izawa, Hidehiko Masuhara, and Carl Friedrich Bolz-Tereick

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
Meta-compiler frameworks, such as RPython and Graal/Truffle, generate high-performance virtual machines (VMs) from interpreter definitions. Although they generate VMs with high-quality just-in-time (JIT) compilers, they still lack an important feature that dedicated VMs (i.e., VMs that are developed for specific languages) have, namely multi-tier compilation. Multi-tier compilation uses light-weight compilers at early stages and highly optimizing compilers at later stages in order to balance between compilation overheads and code quality. We propose a novel approach to enabling multi-tier compilation in the VMs generated by a meta-compiler framework. Instead of extending the JIT compiler backend of the framework, our approach drives an existing (heavyweight) compiler backend in the framework to quickly generate unoptimized native code by merely embedding directives and compile-time operations into interpreter definitions. As a validation of the approach, we developed 2SOM, a Simple Object Machine with a two-tier JIT compiler based on RPython. 2SOM first applies the tier-1 threaded code generator that is generated by our proposed technique, then, to the loops that exceed a threshold, applies the tier-2 tracing JIT compiler that is generated by the original RPython framework. Our performance evaluation that runs a program with a realistic workload showed that 2SOM improved, when compared against an RPython-based VM, warm-up performance by 15%, with merely a 5% reduction in peak performance.
Cite as

Yusuke Izawa, Hidehiko Masuhara, and Carl Friedrich Bolz-Tereick. A Lightweight Method for Generating Multi-Tier JIT Compilation Virtual Machine in a Meta-Tracing Compiler Framework. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{izawa_et_al:LIPIcs.ECOOP.2025.16,
  author =	{Izawa, Yusuke and Masuhara, Hidehiko and Bolz-Tereick, Carl Friedrich},
  title =	{{A Lightweight Method for Generating Multi-Tier JIT Compilation Virtual Machine in a Meta-Tracing Compiler Framework}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.16},
  URN =		{urn:nbn:de:0030-drops-233090},
  doi =		{10.4230/LIPIcs.ECOOP.2025.16},
  annote =	{Keywords: virtual machine, JIT compiler, multi-tier JIT compiler, meta-tracing JIT compiler, RPython}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.13
Low Sensitivity Hopsets

Authors: Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, and Nicole Wein

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

Abstract
Given a weighted graph G = (V,E,w), a (β, ε)-hopset H is an edge set such that for any s,t ∈ V, where s can reach t in G, there is a path from s to t in G ∪ H which uses at most β hops whose length is in the range [dist_G(s,t), (1+ε)dist_G(s,t)]. We break away from the traditional question that asks for a hopset H that achieves small |H| and small diameter β and instead study the sensitivity of H, a new quality measure. The sensitivity of a vertex (or edge) given a hopset H is, informally, the number of times a single hop in G ∪ H bypasses it; a bit more formally, assuming shortest paths in G are unique, it is the number of hopset edges (s,t) ∈ H such that the vertex (or edge) is contained in the unique st-path in G having length exactly dist_G(s,t). The sensitivity associated with H is then the maximum sensitivity over all vertices (or edges). The highlights of our results are: - A construction for (Õ(√n), 0)-hopsets on undirected graphs with O(log n) sensitivity, complemented with a lower bound showing that Õ(√n) is tight up to polylogarithmic factors for any construction with polylogarithmic sensitivity. - A construction for (n^o(1), ε)-hopsets on undirected graphs with n^o(1) sensitivity for any ε > 0 that is at least inverse polylogarithmic, complemented with a lower bound on the tradeoff between β, ε, and the sensitivity. - We define a notion of sensitivity for β-shortcut sets (which are the reachability analogues of hopsets) and give a construction for Õ(√n)-shortcut sets on directed graphs with O(log n) sensitivity, complemented with a lower bound showing that β = Ω̃(n^{1/3}) for any construction with polylogarithmic sensitivity. We believe hopset sensitivity is a natural measure in and of itself, and could potentially find use in a diverse range of contexts. More concretely, the notion of hopset sensitivity is also directly motivated by the Differentially Private All Sets Range Queries problem [Deng et al. WADS 23]. Our result for O(log n) sensitivity (Õ(√n), 0)-hopsets on undirected graphs immediately improves the current best-known upper bound on utility from Õ(n^{1/3}) to Õ(n^{1/4}) in the pure-DP setting, which is tight up to polylogarithmic factors.
Cite as

Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, and Nicole Wein. Low Sensitivity Hopsets. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ashvinkumar_et_al:LIPIcs.ITCS.2025.13,
  author =	{Ashvinkumar, Vikrant and Bernstein, Aaron and Deng, Chengyuan and Gao, Jie and Wein, Nicole},
  title =	{{Low Sensitivity Hopsets}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{13:1--13:23},
  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.13},
  URN =		{urn:nbn:de:0030-drops-226418},
  doi =		{10.4230/LIPIcs.ITCS.2025.13},
  annote =	{Keywords: Hopsets, Shortcuts, Sensitivity, Differential Privacy}
}
Document
DOI: 10.4230/DagRep.6.11.63
Assessing ICT Security Risks in Socio-Technical Systems (Dagstuhl Seminar 16461)

Authors: Tyler W. Moore, Christian W. Probst, Kai Rannenberg, and Michel van Eeten

Published in: Dagstuhl Reports, Volume 6, Issue 11 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16461 "Assessing ICT Security Risks in Socio-Technical Systems". As we progress from classic mechanical or electrical production systems, over ICT systems, to socio-technical systems, risk assessment becomes increasingly complex and difficult. Risk assessment for traditional engineering systems assumes the systems to be deterministic. In non-deterministic systems, standard procedure is to fix those factors that are not deterministic. These techniques do not scale to ICT systems where many risks are hard to trace due to the immaterial nature of information. Beyond ICT systems, socio-technical systems also contain human actors as integral parts of the system. In such socio-technical systems there may occur unforeseen interactions between the system, the environment, and the human actors, especially insiders. Assessing ICT security risks for socio-technical systems and their economic environment requires methods and tools that integrate relevant socio-technical security metrics. In this seminar we investigated systematic methods and tools to estimate those ICT security risks in socio-technical systems and their economic environment. In particular, we searched for novel security risk assessment methods that integrate different types of socio-technical security metrics.
Cite as

Tyler W. Moore, Christian W. Probst, Kai Rannenberg, and Michel van Eeten. Assessing ICT Security Risks in Socio-Technical Systems (Dagstuhl Seminar 16461). In Dagstuhl Reports, Volume 6, Issue 11, pp. 63-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{moore_et_al:DagRep.6.11.63,
  author =	{Moore, Tyler W. and Probst, Christian W. and Rannenberg, Kai and van Eeten, Michel},
  title =	{{Assessing ICT Security Risks in Socio-Technical Systems (Dagstuhl Seminar 16461)}},
  pages =	{63--89},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{11},
  editor =	{Moore, Tyler W. and Probst, Christian W. and Rannenberg, Kai and van Eeten, Michel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.11.63},
  URN =		{urn:nbn:de:0030-drops-70390},
  doi =		{10.4230/DagRep.6.11.63},
  annote =	{Keywords: economics of risk assessment, human factor, return on security investment, security risk management, socio-technical security}
}
Document
DOI: 10.4230/DagRep.1.12.11
Secure Architectures in the Cloud (Dagstuhl Seminar 11492)

Authors: Sabrina De Capitani di Vimercati, Wolter Pieters, and Christian W. Probst

Published in: Dagstuhl Reports, Volume 1, Issue 12 (2012)

Abstract
This report documents the outcomes of Dagstuhl Seminar 11492 ``Secure Architectures in the Cloud''. In cloud computing, data storage and processing are offered as services, and data are managed by external providers that reside outside the control of the data owner. The use of such services reduces the burden of the owners in managing their data, and may provide significant cost savings. However, cloud computing introduces new security and privacy concerns. In fact, there is little consensus on how to guarantee the confidentiality, integrity, and availability of data in cloud computing scenarios. Also, it is unclear to what extent parties can be held accountable in case something goes wrong. In this seminar, we searched for architectures, modelling approaches, and mechanisms that can help in providing guarantees for cloud security. We proposed the concept of verification-as-a-service that can guide architectures for verification of cloud architectures and configurations, as well as results of computations. We also proposed architectures for organising customisability of security and privacy for cloud customers.
Cite as

Sabrina De Capitani di Vimercati, Wolter Pieters, and Christian W. Probst. Secure Architectures in the Cloud (Dagstuhl Seminar 11492). In Dagstuhl Reports, Volume 1, Issue 12, pp. 11-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{decapitanidivimercati_et_al:DagRep.1.12.11,
  author =	{De Capitani di Vimercati, Sabrina and Pieters, Wolter and Probst, Christian W.},
  title =	{{Secure Architectures in the Cloud (Dagstuhl Seminar 11492)}},
  pages =	{11--26},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{12},
  editor =	{De Capitani di Vimercati, Sabrina and Pieters, Wolter and Probst, Christian W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.12.11},
  URN =		{urn:nbn:de:0030-drops-33843},
  doi =		{10.4230/DagRep.1.12.11},
  annote =	{Keywords: attestation, auditing, cloud computing, security architectures, security modelling, verification}
}
Document
DOI: 10.4230/OASIcs.PPES.2011.11
Towards a Time-predictable Dual-Issue Microprocessor: The Patmos Approach

Authors: Martin Schoeberl, Pascal Schleuniger, Wolfgang Puffitsch, Florian Brandner, and Christian W. Probst

Published in: OASIcs, Volume 18, Bringing Theory to Practice: Predictability and Performance in Embedded Systems (2011)

Abstract
Current processors are optimized for average case performance, often leading to a high worst-case execution time (WCET). Many architectural features that increase the average case performance are hard to be modeled for the WCET analysis. In this paper we present Patmos, a processor optimized for low WCET bounds rather than high average case performance. Patmos is a dual-issue, statically scheduled RISC processor. The instruction cache is organized as a method cache and the data cache is organized as a split cache in order to simplify the cache WCET analysis. To fill the dual-issue pipeline with enough useful instructions, Patmos relies on a customized compiler. The compiler also plays a central role in optimizing the application for the WCET instead of average case performance.
Cite as

Martin Schoeberl, Pascal Schleuniger, Wolfgang Puffitsch, Florian Brandner, and Christian W. Probst. Towards a Time-predictable Dual-Issue Microprocessor: The Patmos Approach. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 11-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{schoeberl_et_al:OASIcs.PPES.2011.11,
  author =	{Schoeberl, Martin and Schleuniger, Pascal and Puffitsch, Wolfgang and Brandner, Florian and Probst, Christian W.},
  title =	{{Towards a Time-predictable Dual-Issue Microprocessor: The Patmos Approach}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{11--21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.11},
  URN =		{urn:nbn:de:0030-drops-30774},
  doi =		{10.4230/OASIcs.PPES.2011.11},
  annote =	{Keywords: Time-predictable architecture, WCET analysis, WCET-aware compilation}
}
Document
DOI: 10.4230/DagSemProc.10341.1
10341 Abstracts Collection – Insider Threats: Strategies for Prevention, Mitigation, and Response

Authors: Matt Bishop, Lizzie Coles-Kemp, Dieter Gollmann, Jeffrey Hunker, and Christian W. Probst

Published in: Dagstuhl Seminar Proceedings, Volume 10341, Insider Threats: Strategies for Prevention, Mitigation, and Response (2010)

Abstract
From August 22 to 26, 2010, the Dagstuhl Seminar 10341 ``Insider Threats: Strategies for Prevention, Mitigation, and Response'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. 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

Matt Bishop, Lizzie Coles-Kemp, Dieter Gollmann, Jeffrey Hunker, and Christian W. Probst. 10341 Abstracts Collection – Insider Threats: Strategies for Prevention, Mitigation, and Response. In Insider Threats: Strategies for Prevention, Mitigation, and Response. Dagstuhl Seminar Proceedings, Volume 10341, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bishop_et_al:DagSemProc.10341.1,
  author =	{Bishop, Matt and Coles-Kemp, Lizzie and Gollmann, Dieter and Hunker, Jeffrey and Probst, Christian W.},
  title =	{{10341 Abstracts Collection – Insider Threats: Strategies for Prevention, Mitigation, and Response}},
  booktitle =	{Insider Threats: Strategies for Prevention, Mitigation, and Response},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10341},
  editor =	{Matt Bishop and Lizzie Coles-Kemp and Dieter Gollmann and Jeff Hunker and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10341.1},
  URN =		{urn:nbn:de:0030-drops-29046},
  doi =		{10.4230/DagSemProc.10341.1},
  annote =	{Keywords: Insider Threat, Security Policies, Threat Modelling}
}
Document
DOI: 10.4230/DagSemProc.10341.2
10341 Report – Insider Threats: Strategies for Prevention, Mitigation, and Response

Authors: Matt Bishop, Lizzie Coles-Kemp, Dieter Gollmann, Jeffrey Hunker, and Christian W. Probst

Published in: Dagstuhl Seminar Proceedings, Volume 10341, Insider Threats: Strategies for Prevention, Mitigation, and Response (2010)

Abstract
This article summarizes the objectives and structure of a seminar with the same title, held from August 22nd to 26th, 2010, at Schloss Dagstuhl, Germany. The seminar brought together researchers and policy-makers from quite diverse communities, to make progress towards an integrated framework for understanding insider threats and their interaction with organizations and policies. During the seminar, social and organizational factors relevant to insider threats, were discussed, as well as urgent questions in four areas: synthesizing social science and technical research, metrics and assurance, language formulations and ontology, and the threats facing intangible systems. This report gives an overview of the discussions and presentations during the week, as well as the outcome of these discussions.
Cite as

Matt Bishop, Lizzie Coles-Kemp, Dieter Gollmann, Jeffrey Hunker, and Christian W. Probst. 10341 Report – Insider Threats: Strategies for Prevention, Mitigation, and Response. In Insider Threats: Strategies for Prevention, Mitigation, and Response. Dagstuhl Seminar Proceedings, Volume 10341, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bishop_et_al:DagSemProc.10341.2,
  author =	{Bishop, Matt and Coles-Kemp, Lizzie and Gollmann, Dieter and Hunker, Jeffrey and Probst, Christian W.},
  title =	{{10341 Report – Insider Threats: Strategies for Prevention, Mitigation, and Response}},
  booktitle =	{Insider Threats: Strategies for Prevention, Mitigation, and Response},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10341},
  editor =	{Matt Bishop and Lizzie Coles-Kemp and Dieter Gollmann and Jeff Hunker and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10341.2},
  URN =		{urn:nbn:de:0030-drops-29033},
  doi =		{10.4230/DagSemProc.10341.2},
  annote =	{Keywords: Insider Threat, Security Policies, Threat Modelling}
}
Document
DOI: 10.4230/DagSemProc.08302.1
08302 Abstracts Collection – Countering Insider Threats

Authors: Matt Bishop, Dieter Gollmann, Jeffrey Hunker, and Christian W. Probst

Published in: Dagstuhl Seminar Proceedings, Volume 8302, Countering Insider Threats (2008)

Abstract
From July 20 to July 25, 2008, the Dagstuhl Seminar 08302 ``Countering Insider Threats '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. 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

Matt Bishop, Dieter Gollmann, Jeffrey Hunker, and Christian W. Probst. 08302 Abstracts Collection – Countering Insider Threats. In Countering Insider Threats. Dagstuhl Seminar Proceedings, Volume 8302, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bishop_et_al:DagSemProc.08302.1,
  author =	{Bishop, Matt and Gollmann, Dieter and Hunker, Jeffrey and Probst, Christian W.},
  title =	{{08302 Abstracts Collection – Countering Insider Threats}},
  booktitle =	{Countering Insider Threats},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8302},
  editor =	{Matt Bishop and Dieter Gollmann and Jeffrey Hunke and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08302.1},
  URN =		{urn:nbn:de:0030-drops-17960},
  doi =		{10.4230/DagSemProc.08302.1},
  annote =	{Keywords: Insider Threat, Security Policies, Threat Modelling}
}
Document
DOI: 10.4230/DagSemProc.08302.2
08302 Summary – Countering Insider Threats

Authors: Christian W. Probst, Jeffrey Hunker, Matt Bishop, and Dieter Gollmann

Published in: Dagstuhl Seminar Proceedings, Volume 8302, Countering Insider Threats (2008)

Abstract
This article summarizes the objectives and structure of a seminar with the same title, held from July 20th to July 25th, 2008, at Schloss Dagstuhl, Germany. The seminar brought together researchers and policy-makers from all involved communities, to clarify what it is that identifies an insider threat, and to develop a common vision of how an insider can be categorized as well as an integrated approach that allows a qualitative reasoning about the threat and the possibilities of attacks. This report gives an overview of the discussions and presentations during the week, as well as the outcome of these discussions.
Cite as

Christian W. Probst, Jeffrey Hunker, Matt Bishop, and Dieter Gollmann. 08302 Summary – Countering Insider Threats. In Countering Insider Threats. Dagstuhl Seminar Proceedings, Volume 8302, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{probst_et_al:DagSemProc.08302.2,
  author =	{Probst, Christian W. and Hunker, Jeffrey and Bishop, Matt and Gollmann, Dieter},
  title =	{{08302 Summary – Countering Insider Threats}},
  booktitle =	{Countering Insider Threats},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8302},
  editor =	{Matt Bishop and Dieter Gollmann and Jeffrey Hunke and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08302.2},
  URN =		{urn:nbn:de:0030-drops-17937},
  doi =		{10.4230/DagSemProc.08302.2},
  annote =	{Keywords: Insider threat, workshop report}
}
  • Refine by Type
  • 37 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 8 2025
  • 1 2017
  • 1 2012
  • 1 2011
  • 2 2010
  • Show More...

  • Refine by Author
  • 13 Probst, Christian W.
  • 6 Kremer, Ulrich
  • 5 Steger, Christian
  • 4 Benini, Luca
  • 4 Bishop, Matt
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs
  • 1 OASIcs
  • 2 DagRep
  • 26 DagSemProc

  • Refine by Classification
  • 3 Theory of computation → Shortest paths
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Graph algorithms
  • 1 Software and its engineering → Interpreters
  • Show More...

  • Refine by Keyword
  • 3 Insider Threat
  • 3 Security Policies
  • 3 Threat Modelling
  • 2 Insider threat
  • 2 compiler optimization
  • 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