56 Search Results for "Miller, Mark S."

Document
DOI: 10.4230/LIPIcs.STACS.2026.5
On the Complexity of Language Membership for Probabilistic Words

Authors: Antoine Amarilli, Mikaël Monet, Paul Raphaël, and Sylvain Salvati

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study the membership problem to context-free languages L (CFLs) on probabilistic words, that specify for each position a probability distribution on the letters (assuming independence across positions). Our task is to compute, given a probabilistic word, what is the probability that a word drawn according to the distribution belongs to L. This problem generalizes the problem of counting how many words of length n belong to L, or of counting how many completions of a partial word belong to L. We show that this problem is in polynomial time for unambiguous context-free languages (uCFLs), but can be #P-hard already for unions of two linear uCFLs. More generally, we show that the problem is in polynomial time for so-called poly-slicewise-unambiguous languages, where given a length n we can tractably compute an uCFL for the words of length n in the language. This class includes some inherently ambiguous languages, and implies the tractability of bounded CFLs and of languages recognized by unambiguous polynomial-time counter automata; but we show that the problem can be #P-hard for nondeterministic counter automata, even for Parikh automata with a single counter. We then introduce classes of circuits from knowledge compilation which we use for tractable counting, and show that this covers the tractability of poly-slicewise-unambiguous languages and of some CFLs that are not poly-slicewise-unambiguous. Extending these circuits with negation further allows us to show tractability for the language of primitive words, and for the language of concatenations of two palindromes. We finally show the conditional undecidability of the meta-problem that asks, given a CFG, whether the probabilistic membership problem for that CFG is tractable or #P-hard.
Cite as

Antoine Amarilli, Mikaël Monet, Paul Raphaël, and Sylvain Salvati. On the Complexity of Language Membership for Probabilistic Words. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.STACS.2026.5,
  author =	{Amarilli, Antoine and Monet, Mika\"{e}l and Rapha\"{e}l, Paul and Salvati, Sylvain},
  title =	{{On the Complexity of Language Membership for Probabilistic Words}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.5},
  URN =		{urn:nbn:de:0030-drops-254943},
  doi =		{10.4230/LIPIcs.STACS.2026.5},
  annote =	{Keywords: Automaton, probabilistic words, context-free grammar, membership problem}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.15
How to Use Nondeterminism in Cryptography

Authors: Marshall Ball and Peter Crawford-Kahrl

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

Abstract
Nondeterministic reductions have yielded powerful results in the theory of computational complexity, yet are effectively useless in a cryptographic context. The reason for this is simple, a nondeterministic polynomial time adversary can trivially break almost any cryptographic primitive by simply guessing the "key." In order to use this powerful nondeterministic tool kit in the cryptographic context, we initiate the study of cryptography against adversaries with limited nondeterminism: polynomial time nondeterministic algorithms that are restricted to just a few bits of nondeterminism. We demonstrate that limited nondeterministic security is sufficient to prove two foundational results that have eluded our grasp for decades: dream hardness amplification, and extracting ω(log n) hardcore bits.
Cite as

Marshall Ball and Peter Crawford-Kahrl. How to Use Nondeterminism in Cryptography. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2026.15,
  author =	{Ball, Marshall and Crawford-Kahrl, Peter},
  title =	{{How to Use Nondeterminism in Cryptography}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{15:1--15:22},
  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.15},
  URN =		{urn:nbn:de:0030-drops-253024},
  doi =		{10.4230/LIPIcs.ITCS.2026.15},
  annote =	{Keywords: limited nondeterminism, cryptography, computational complexity, hardness amplification, pseudorandom generators, hardcore bits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.3
Linear Matroid Intersection Is in Catalytic Logspace

Authors: Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra

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

Abstract
Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of {P}. We address this problem for the class catalytic logspace (CL) with a polynomial time bound (CLP). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class CLP ⊆ {P}. This was the first subclass of {P} shown to contain bipartite matching, and additionally the first problem outside TC¹ shown to be contained in CL. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in CLP.
Cite as

Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear Matroid Intersection Is in Catalytic Logspace. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.3,
  author =	{Agarwala, Aryan and Alekseev, Yaroslav and Vinciguerra, Antoine},
  title =	{{Linear Matroid Intersection Is in Catalytic Logspace}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-252908},
  doi =		{10.4230/LIPIcs.ITCS.2026.3},
  annote =	{Keywords: Catalytic Computing, Computational Complexity, Matroid Theory, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.87
Range Longest Increasing Subsequence and Its Relatives

Authors: Karthik C. S. and Saladi Rahul

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

Abstract
Longest increasing subsequence (LIS) is a classical textbook problem which is still actively studied in various computational models. In this work, we present a few results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to Range-LIS is a sequence 𝒮 of n real numbers and a collection 𝒬 of m query ranges and for each query in 𝒬, the goal is to report the LIS of the sequence 𝒮 restricted to that query. Our two main results are for the following generalizations of the Range-LIS problem: 2D Range Queries: In this variant of the Range-LIS problem, each query is a pair of ranges, one of indices and the other of values, and we provide a randomized algorithm with running time Õ(mn^{1/2}+ n^{3/2})+O(k), where k is the cumulative length of the m output subsequences. This improves on the elementary Õ(mn) runtime algorithm when m = Ω(√n). Previously, the only known result breaking the quadratic barrier was of Tiskin [SODA'10] which could only handle 1D range queries (i.e., each query was a range of indices) and also just outputted the length of the LIS (instead of reporting the subsequence achieving that length). Subsequent to our paper, Gawrychowski, Gorbachev, and Kociumaka in a preprint have extended Tiskin’s approach to handle reporting 1D range queries in O(n(log n)³+m+k) time. Colored Sequences: In this variant of the Range-LIS problem, each element in 𝒮 is colored and for each query in 𝒬, the goal is to report a monochromatic LIS contained in the sequence 𝒮 restricted to that query. For 2D queries, we provide a randomized algorithm for this colored version with running time Õ(mn^{2/3}+ n^{5/3})+O(k). Moreover, for 1D queries, we provide an improved algorithm with running time Õ(mn^{1/2}+ n^{3/2})+O(k). Thus, we again improve on the elementary Õ(mn) runtime algorithm. Additionally, we prove that assuming the well-known Combinatorial Boolean Matrix Multiplication Hypothesis, that the runtime for 1D queries is essentially tight for combinatorial algorithms. Our algorithms combine several tools such as dynamic programming (to precompute increasing subsequences with some desirable properties), geometric data structures (to efficiently compute the dynamic programming entries), random sampling (to capture elements which are part of the LIS), classification of query ranges into large LIS and small LIS, and classification of colors into light and heavy. We believe that our techniques will be of interest to tackle other variants of LIS problem and other range-searching problems.
Cite as

Karthik C. S. and Saladi Rahul. Range Longest Increasing Subsequence and Its Relatives. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 87:1-87:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karthikc.s._et_al:LIPIcs.ITCS.2026.87,
  author =	{Karthik C. S. and Rahul, Saladi},
  title =	{{Range Longest Increasing Subsequence and Its Relatives}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{87:1--87:20},
  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.87},
  URN =		{urn:nbn:de:0030-drops-253740},
  doi =		{10.4230/LIPIcs.ITCS.2026.87},
  annote =	{Keywords: Longest Increasing Subsequence, Range Query, Fine-Grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.33
Resolving Conflicts with Grace: Dynamically Concurrent Universality

Authors: Petr Kuznetsov and Nathan Josia Schrodt

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Synchronization is the major obstacle to scalability in distributed computing. Concurrent operations on the shared data engage in synchronization when they encounter a conflict, i.e., their effects depend on the order in which they are applied. Ideally, one would like to detect conflicts in a dynamic manner, i.e., adjusting to the current system state. Indeed, it is very common that two concurrent operations conflict only in some rarely occurring states. In this paper, we define the notion of dynamic concurrency: an operation employs strong synchronization primitives only if it has to arbitrate with concurrent operations, given the current system state. We then present a dynamically concurrent universal construction.
Cite as

Petr Kuznetsov and Nathan Josia Schrodt. Resolving Conflicts with Grace: Dynamically Concurrent Universality. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 33:1-33:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.OPODIS.2025.33,
  author =	{Kuznetsov, Petr and Schrodt, Nathan Josia},
  title =	{{Resolving Conflicts with Grace: Dynamically Concurrent Universality}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{33:1--33:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.33},
  URN =		{urn:nbn:de:0030-drops-252068},
  doi =		{10.4230/LIPIcs.OPODIS.2025.33},
  annote =	{Keywords: Universal Construction, Consensus, Dynamic Concurrency}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.32
The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Authors: Mario Grobler and Sebastian Siebertz

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Mario Grobler and Sebastian Siebertz. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.IPEC.2025.32,
  author =	{Grobler, Mario and Siebertz, Sebastian},
  title =	{{The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.32},
  URN =		{urn:nbn:de:0030-drops-251644},
  doi =		{10.4230/LIPIcs.IPEC.2025.32},
  annote =	{Keywords: PACE 2025 Report, Dominating Set, Hitting Set, Algorithm Engineering, FPT, Heuristics}
}
Document
Resource
DOI: 10.4230/TGDK.3.3.3
Supporting Psychometric Instrument Usage Through the POEM Ontology

Authors: Kelsey Rook, Henrique Santos, Deborah L. McGuinness, Manuel S. Sprung, Paulo Pinheiro, and Bruce F. Chorpita

Published in: TGDK, Volume 3, Issue 3 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 3

Abstract
Psychometrics is the field relating to the measurement of concepts within psychology, particularly the assessment of various social and psychological dimensions in humans. The relationship between psychometric entities is critical to finding an appropriate assessment instrument, especially in the context of clinical psychology and mental healthcare in which providing the best care based on empirical evidence is crucial. We aim to model these entities, which include psychometric questionnaires and their component elements, the subject and respondent, and the latent variables being assessed. The current standard for questionnaire-based assessment relies on text-based distributions of instruments; so, a structured representation is necessary to capture these relationships to enhance accessibility and use of existing measures, encourage reuse of questionnaires and their component elements, and enable sophisticated reasoning over assessment instruments and results by increasing interoperability. We present the design process and architecture of such a domain ontology, the Psychometric Ontology of Experiences and Measures, situating it within the context of related ontologies, and demonstrating its practical utility through evaluation against a series of competency questions concerning the creation, use, and reuse of psychometric questionnaires in clinical, research, and development settings.
Cite as

Kelsey Rook, Henrique Santos, Deborah L. McGuinness, Manuel S. Sprung, Paulo Pinheiro, and Bruce F. Chorpita. Supporting Psychometric Instrument Usage Through the POEM Ontology. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 3, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{rook_et_al:TGDK.3.3.3,
  author =	{Rook, Kelsey and Santos, Henrique and McGuinness, Deborah L. and Sprung, Manuel S. and Pinheiro, Paulo and Chorpita, Bruce F.},
  title =	{{Supporting Psychometric Instrument Usage Through the POEM Ontology}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:19},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{3},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.3.3},
  URN =		{urn:nbn:de:0030-drops-252148},
  doi =		{10.4230/TGDK.3.3.3},
  annote =	{Keywords: ontology, ontology development, psychometric assessment, psychometric ontology}
}
Document
Invited Paper
DOI: 10.4230/OASIcs.RW.2024/2025.7
Modern Datalog: Concepts, Methods, Applications (Invited Paper)

Authors: Markus Krötzsch

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract
Pure Datalog is arguably the most fundamental rule language, elegant and simple, but also often too limited to be useful in practice. This has motivated the introduction of many new expressive features, ranging from datatypes and related functions, over aggregates and semi-ring generalisations, to existential quantifiers and complex terms. In spite of their variety, all these approaches remain true to the nature of Datalog as a direct, pattern-based way of computing on structured data. We therefore find that a modern notion of Datalog is emerging, distinctly different from other approaches of logic programming and with its own set of related methods and applications. In this course, we introduce Datalog and its most common extensions, and explain when and how these features can be used together (which is often, but not always, safe to do). We further look at modern Datalog systems and some of their primary use cases. Hands-on work with Datalog and its extensions is done with the free Datalog engine https://knowsys.github.io/nemo-doc/. The course is accessible to all audiences and does not assume specific prior knowledge.
Cite as

Markus Krötzsch. Modern Datalog: Concepts, Methods, Applications (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 7:1-7:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{krotzsch:OASIcs.RW.2024/2025.7,
  author =	{Kr\"{o}tzsch, Markus},
  title =	{{Modern Datalog: Concepts, Methods, Applications}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{7:1--7:41},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.7},
  URN =		{urn:nbn:de:0030-drops-250524},
  doi =		{10.4230/OASIcs.RW.2024/2025.7},
  annote =	{Keywords: Datalog, query language, knowlegde representation and reasoning, logic programming, Horn logic, SPARQL, datatypes and aggregation, lecture notes, tutorial}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.7
Same Quality Metrics, Different Graph Drawings

Authors: Simon van Wageningen, Tamara Mchedlidze, and Alexandru C. Telea

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

Abstract
Graph drawings are commonly used to visualize relational data. User understanding and performance are linked to the quality of such drawings, which is measured by quality metrics. The tacit knowledge in the graph drawing community about these quality metrics is that they are not always able to accurately capture the quality of graph drawings. In particular, such metrics may rate drawings with very poor quality as very good. In this work we make this tacit knowledge explicit by showing that we can modify existing graph drawings into arbitrary target shapes while keeping one or more quality metrics almost identical. This supports the claim that more advanced quality metrics are needed to capture the "goodness" of a graph drawing and that we cannot confidently rely on the value of a single (or several) certain quality metrics.
Cite as

Simon van Wageningen, Tamara Mchedlidze, and Alexandru C. Telea. Same Quality Metrics, Different Graph Drawings. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanwageningen_et_al:LIPIcs.GD.2025.7,
  author =	{van Wageningen, Simon and Mchedlidze, Tamara and Telea, Alexandru C.},
  title =	{{Same Quality Metrics, Different Graph Drawings}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.7},
  URN =		{urn:nbn:de:0030-drops-249935},
  doi =		{10.4230/LIPIcs.GD.2025.7},
  annote =	{Keywords: graph drawing, quality metrics, assumptions, fooling}
}
Document
DOI: 10.4230/OASIcs.DX.2025.1
Beyond Static Diagnosis: A Temporal ASP Framework for HVAC Fault Detection

Authors: Roxane Koitz-Hristov, Liliana Marie Prikler, and Franz Wotawa

Published in: OASIcs, Volume 136, 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)

Abstract
Improving sustainability in the building sector requires more efficient operation of energy-intensive systems such as Heating, Ventilation, and Air Conditioning (HVAC). We present a novel diagnostic framework for HVAC systems that integrates Answer Set Programming (ASP) with Functional Event Calculus (FEC). Our approach exploits the declarative nature of ASP for modeling and incorporates FEC to capture temporal system dynamics. We demonstrate the feasibility of our approach through a case study on a real-world heating system, where we model key components and system constraints. Our evaluation on nominal and faulty traces shows that exploiting ASP in combination with FEC can identify plausible diagnoses. Moreover, we explore the difference between static and rolling-window strategies and provide insights into runtime versus soundness on those variants. Our work provides a step toward the practical application of ASP-based temporal reasoning in building diagnostics.
Cite as

Roxane Koitz-Hristov, Liliana Marie Prikler, and Franz Wotawa. Beyond Static Diagnosis: A Temporal ASP Framework for HVAC Fault Detection. In 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025). Open Access Series in Informatics (OASIcs), Volume 136, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koitzhristov_et_al:OASIcs.DX.2025.1,
  author =	{Koitz-Hristov, Roxane and Prikler, Liliana Marie and Wotawa, Franz},
  title =	{{Beyond Static Diagnosis: A Temporal ASP Framework for HVAC Fault Detection}},
  booktitle =	{36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)},
  pages =	{1:1--1:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-394-2},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{136},
  editor =	{Quinones-Grueiro, Marcos and Biswas, Gautam and Pill, Ingo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2025.1},
  URN =		{urn:nbn:de:0030-drops-247901},
  doi =		{10.4230/OASIcs.DX.2025.1},
  annote =	{Keywords: Model-based diagnosis, Answer set programming, HVAC, Modeling for diagnosis, Experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.42
Kudzu: Fast and Simple High-Throughput BFT

Authors: Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen

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

Abstract
We present Kudzu, a high-throughput atomic broadcast protocol with an integrated fast path. Our contribution is based on the combination of two lines of work. Firstly, our protocol achieves finality in just two rounds of communication if all but p out of n = 3f + 2p + 1 participating replicas behave correctly, where f is the number of Byzantine faults that are tolerated. Due to the seamless integration of the fast path, even in the presence of more than p faults, our protocol maintains state-of-the-art characteristics. Secondly, our protocol utilizes the bandwidth of participating replicas in a balanced way, alleviating the bottleneck at the leader, and thus enabling high throughput. This is achieved by disseminating blocks using erasure codes. Despite combining a novel set of advantages, Kudzu is remarkably simple: intricacies such as "progress certificates", complex view changes, and speculative execution are avoided.
Cite as

Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen. Kudzu: Fast and Simple High-Throughput BFT. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shoup_et_al:LIPIcs.DISC.2025.42,
  author =	{Shoup, Victor and Sliwinski, Jakub and Vonlanthen, Yann},
  title =	{{Kudzu: Fast and Simple High-Throughput BFT}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{42:1--42:19},
  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.42},
  URN =		{urn:nbn:de:0030-drops-248597},
  doi =		{10.4230/LIPIcs.DISC.2025.42},
  annote =	{Keywords: Consensus, Blockchain, Byzantine Fault Tolerance, Fast Path, State Machine Replication}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.1
Cache Timing Leakages in Zero-Knowledge Protocols

Authors: Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
The area of modern zero-knowledge proof systems has seen a significant rise in popularity over the last couple of years, with new techniques and optimized constructions emerging on a regular basis. As the field matures, the aspect of implementation attacks becomes more relevant, however side-channel attacks on zero-knowledge proof systems have seen surprisingly little treatment so far. In this paper, we give an overview of potential attack vectors and show that some of the underlying finite field libraries, and implementations of heavily used components like hash functions using them, are vulnerable w.r.t. cache attacks on CPUs. On the positive side, we demonstrate that the computational overhead to protect against these attacks is relatively small.
Cite as

Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger. Cache Timing Leakages in Zero-Knowledge Protocols. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.AFT.2025.1,
  author =	{Mukherjee, Shibam and Rechberger, Christian and Schofnegger, Markus},
  title =	{{Cache Timing Leakages in Zero-Knowledge Protocols}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.1},
  URN =		{urn:nbn:de:0030-drops-247201},
  doi =		{10.4230/LIPIcs.AFT.2025.1},
  annote =	{Keywords: zero-knowledge, protocol, cache timing, side-channel, leakage}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.32
Linear-Time Multilevel Graph Partitioning via Edge Sparsification

Authors: Lars Gottesbüren, Nikolai Maas, Dominik Rosch, Peter Sanders, and Daniel Seemaier

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

Abstract
The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as single-level algorithms and streaming algorithms. We demonstrate how to achieve the best of both worlds with a linear time multilevel algorithm. Multilevel algorithms construct a hierarchy of increasingly smaller graphs by repeatedly contracting clusters of nodes. Our approach preserves their distinct advantage, allowing refinement of the partition over multiple levels with increasing detail. At the same time, we use edge sparsification to guarantee geometric size reduction between the levels and thus linear running time. We provide a proof of the linear running time as well as additional insights into the behavior of multilevel algorithms, showing that graphs with low modularity are most likely to trigger worst-case running time. We evaluate multiple approaches for edge sparsification and integrate our algorithm into the state-of-the-art multilevel partitioner KaMinPar, maintaining its excellent parallel scalability. As demonstrated in detailed experiments, this results in a 1.49× average speedup (up to 4× for some instances) with only 1% loss in solution quality. Moreover, our algorithm clearly outperforms state-of-the-art single-level and streaming approaches.
Cite as

Lars Gottesbüren, Nikolai Maas, Dominik Rosch, Peter Sanders, and Daniel Seemaier. Linear-Time Multilevel Graph Partitioning via Edge Sparsification. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.ESA.2025.32,
  author =	{Gottesb\"{u}ren, Lars and Maas, Nikolai and Rosch, Dominik and Sanders, Peter and Seemaier, Daniel},
  title =	{{Linear-Time Multilevel Graph Partitioning via Edge Sparsification}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{32:1--32:20},
  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.32},
  URN =		{urn:nbn:de:0030-drops-245007},
  doi =		{10.4230/LIPIcs.ESA.2025.32},
  annote =	{Keywords: Graph Partitioning, Graph Algorithms, Linear Time Algorithms, Graph Sparsification}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.1
Human-AI Interaction in Space: Insights from a Mars Analog Mission with the Harmony Large Language Model

Authors: Hippolyte Hilgers, Jean Vanderdonckt, and Radu-Daniel Vatavu

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
The operational complexities of space missions require reliable, context-aware technical assistance for astronauts, especially when technical expertise is not available onboard and communication with Earth is delayed or limited. In this context, Large Language Models present a promising opportunity to augment human capabilities. To this end, we present Harmony, a model designed to provide astronauts with real-time technical assistance, fostering human-AI collaboration during analog missions. We report empirical results from an experiment involving seven analog astronauts that evaluated their user experience with Harmony in both a conventional environment and an isolated, confined, and extreme physical setting at the Mars Desert Research Station over four sessions, and discuss how the Mars analog environment impacted their experience. Our findings reveal the extent to which human-AI interactions evolve across various user experience dimensions and suggest how Harmony can be further adapted to suit extreme environments, with a focus on SpaceCHI.
Cite as

Hippolyte Hilgers, Jean Vanderdonckt, and Radu-Daniel Vatavu. Human-AI Interaction in Space: Insights from a Mars Analog Mission with the Harmony Large Language Model. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hilgers_et_al:OASIcs.SpaceCHI.2025.1,
  author =	{Hilgers, Hippolyte and Vanderdonckt, Jean and Vatavu, Radu-Daniel},
  title =	{{Human-AI Interaction in Space: Insights from a Mars Analog Mission with the Harmony Large Language Model}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{1:1--1:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.1},
  URN =		{urn:nbn:de:0030-drops-239912},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.1},
  annote =	{Keywords: Extreme user experience, Human-AI interaction, Isolated-confined-extreme environment, Interaction design, Large Language Models, Mars Desert Research Station, Space mission, Technical assistance, Technical documentation, User experience}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.13
Exploring the Symbiotic Collaboration Paradigm in Virtual Reality and Its Potential Applications to Human Spaceflight

Authors: Florian Dufresne, Geoffrey Gorisse, and Olivier Christmann

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
As the quest to go back to the Moon and beyond continues, preparation for such critical missions relies in part on the use of immersive technologies. Especially, Virtual Reality (VR) unique affordances allow to simulate scenarios in a convincing digitally recreated space. But the potential of VR is not limited to solely emulating real-world environments. Indeed, some works from the Human-Computer Interaction (HCI) community explored new ways to collaborate virtually by inhabiting the same virtual representation, namely an avatar. Taking this paradigm further, one could offer new ways to collaborate between an immersed VR user and an external supervisor being granted access to the virtual environment by way of non-immersive devices like a computer or a smartphone. The non-immersed user could for instance inhabit some body parts of the VR user’s avatar to benefit from unique viewpoints and leverage mutual spatial awareness, as well as social interactions, alike a symbiotic relationship that benefits both actors. Therefore, this paper introduces our on-going research project exploring this new paradigm of symbiotic co-embodiment as a tool leveraging social presence during supervised embodied sessions in VR. It especially discusses how this paradigm could benefit human spaceflight, both in mission preparation and during spaceflight.
Cite as

Florian Dufresne, Geoffrey Gorisse, and Olivier Christmann. Exploring the Symbiotic Collaboration Paradigm in Virtual Reality and Its Potential Applications to Human Spaceflight. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dufresne_et_al:OASIcs.SpaceCHI.2025.13,
  author =	{Dufresne, Florian and Gorisse, Geoffrey and Christmann, Olivier},
  title =	{{Exploring the Symbiotic Collaboration Paradigm in Virtual Reality and Its Potential Applications to Human Spaceflight}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{13:1--13:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.13},
  URN =		{urn:nbn:de:0030-drops-240034},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.13},
  annote =	{Keywords: Virtual Reality, Co-Embodiment, Human Spaceflight, Supervised Training, On-field Activities}
}
  • Refine by Type
  • 56 Document/PDF
  • 44 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 33 2025
  • 3 2024
  • 5 2023
  • 2 2020
  • Show More...

  • Refine by Author
  • 3 Miller, Mark S.
  • 2 Allen, Bradley P.
  • 2 Biswas, Russa
  • 2 Blažauskas, Tomas
  • 2 Bonifati, Angela
  • Show More...

  • Refine by Series/Journal
  • 31 LIPIcs
  • 17 OASIcs
  • 8 TGDK

  • Refine by Classification
  • 4 Computing methodologies → Natural language processing
  • 3 Computing methodologies → Knowledge representation and reasoning
  • 3 Mathematics of computing → Graph algorithms
  • 3 Software and its engineering → General programming languages
  • 3 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 4 Large Language Models
  • 3 knowledge graphs
  • 2 Consensus
  • 2 Datalog
  • 2 Maximum Matching
  • 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