27 Search Results for "Mass, David"

Document
DOI: 10.4230/LIPIcs.CSL.2026.43
Kamp Theorem for Pomset Languages of Higher Dimensional Automata

Authors: Emily Clement, Enzo Erlich, and Jérémy Ledent

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
Temporal logics are a powerful tool to specify properties of computational systems. For concurrent programs, Higher Dimensional Automata (HDA) are a very expressive model of non-interleaving concurrency. HDA recognize languages of partially ordered multisets, or pomsets. Recent work has shown that Monadic Second Order (MSO) logic is as expressive as HDA for pomset languages. In the case of words, Kamp’s theorem states that First Order (FO) logic is as expressive as Linear Temporal Logic (LTL). In this paper, we extend this result to pomsets. To do so, we first investigate the class of pomset languages that are definable in FO. As expected, this is a strict subclass of MSO-definable languages. Then, we define a Linear Temporal Logic for pomsets (LTL_Poms), and show that it is equivalent to FO.
Cite as

Emily Clement, Enzo Erlich, and Jérémy Ledent. Kamp Theorem for Pomset Languages of Higher Dimensional Automata. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 43:1-43:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{clement_et_al:LIPIcs.CSL.2026.43,
  author =	{Clement, Emily and Erlich, Enzo and Ledent, J\'{e}r\'{e}my},
  title =	{{Kamp Theorem for Pomset Languages of Higher Dimensional Automata}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{43:1--43:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.43},
  URN =		{urn:nbn:de:0030-drops-254685},
  doi =		{10.4230/LIPIcs.CSL.2026.43},
  annote =	{Keywords: Higher dimensional automata, temporal logic, Kamp’s theorem}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.11
Parameterized Algorithms for Diversity of Networks with Ecological Dependencies

Authors: Mark Jones and Jannik Schestag

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

Abstract
For a phylogenetic tree, the phylogenetic diversity of a set A of taxa is the total weight of edges on paths to A. Finding small sets of maximal diversity is crucial for conservation planning, as it indicates where limited resources can be invested most efficiently. In recent years, efficient algorithms have been developed to find sets of taxa that maximize phylogenetic diversity either in a phylogenetic network or in a phylogenetic tree subject to ecological constraints, such as a food web. However, these aspects have mostly been studied independently. Since both factors are biologically important, it seems natural to consider them together. In this paper, we introduce decision problems where, given a phylogenetic network, a food web, and integers k, and D, the task is to find a set of k taxa with phylogenetic diversity of at least D under the maximize all paths measure, while also satisfying viability conditions within the food web. Here, we consider different definitions of viability, which all demand that a "sufficient" number of prey species survive to support surviving predators. We investigate the parameterized complexity of these problems and present several fixed-parameter tractable (FPT) algorithms. Specifically, we provide a complete complexity dichotomy characterizing which combinations of parameters - out of the size constraint k, the acceptable diversity loss D̄, the scanwidth of the food web sw_ℱ, the maximum in-degree δ in the network, and the network height h - lead to W[1]-hardness and which admit FPT algorithms. Our primary methodological contribution is a novel algorithmic framework for solving phylogenetic diversity problems in networks where dependencies (such as those from a food web) impose an order, using a color coding approach.
Cite as

Mark Jones and Jannik Schestag. Parameterized Algorithms for Diversity of Networks with Ecological Dependencies. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.IPEC.2025.11,
  author =	{Jones, Mark and Schestag, Jannik},
  title =	{{Parameterized Algorithms for Diversity of Networks with Ecological Dependencies}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{11:1--11:21},
  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.11},
  URN =		{urn:nbn:de:0030-drops-251439},
  doi =		{10.4230/LIPIcs.IPEC.2025.11},
  annote =	{Keywords: Phylogenetic Diversity, Fixed-Parameter Tractability, Phylogenetic Networks, Food Webs, Color Coding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.28
Pathfinding in Self-Deleting Graphs

Authors: Michal Dvořák, Dušan Knop, Michal Opler, Jan Pokorný, Ondřej Suchý, and Krisztina Szilágyi

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. [Sarah Carmesin et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v. We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.
Cite as

Michal Dvořák, Dušan Knop, Michal Opler, Jan Pokorný, Ondřej Suchý, and Krisztina Szilágyi. Pathfinding in Self-Deleting Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2025.28,
  author =	{Dvo\v{r}\'{a}k, Michal and Knop, Du\v{s}an and Opler, Michal and Pokorn\'{y}, Jan and Such\'{y}, Ond\v{r}ej and Szil\'{a}gyi, Krisztina},
  title =	{{Pathfinding in Self-Deleting Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.28},
  URN =		{urn:nbn:de:0030-drops-249365},
  doi =		{10.4230/LIPIcs.ISAAC.2025.28},
  annote =	{Keywords: Parameterized complexity, self-deleting graphs, pathfinding}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.19
Robust Predicate and Function Computation in Continuous Chemical Reaction Networks

Authors: Kim Calabrese, David Doty, and Mina Latifi

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

Abstract
We initiate the study of "rate-constant-independent" computation of Boolean predicates (decision problems) and numerical functions in the continuous model of chemical reaction networks (CRNs), which model the amount of a chemical species as a nonnegative, real-valued concentration, representing an average count per unit volume. Real-valued numerical functions have previously been studied [Chen et al., 2023], finding that exactly the continuous, piecewise rational linear (meaning linear with rational slopes) functions f: ℝ_{>0}^k → ℝ_{>0} can be computed stably (a.k.a., rate-independently), meaning roughly that the CRN gets the answer correct no matter the rate at which reactions occur. For example the reactions X₁ → Y and X₂+Y → ∅, starting with inputs X₁ ≥ X₂, converge to output Y having concentration equal to the initial difference of inputs X₁ - X₂, no matter the relative rate at which each reaction proceeds. We first show that, contrary to the case of real-valued functions, continuous CRNs are severely limited in the Boolean predicates they can stably decide, reporting a yes/no answer based only on which inputs are 0 or positive, but not on the exact positive value of any input. This limitation motivates a slightly relaxed notion of rate-independent computation in CRNs that we call robust computation. The standard mass-action rate model is used, in which each reaction (e.g., A+B →^k C) is assigned a rate (A ⋅ B ⋅ k in this example) equal to the product of its reactant concentrations and its rate constant k. We say the computation is correct in this model if it converges to the correct output for any positive choice of rate constants. This adversary is weaker than the adversary defining stable computation, the latter being able to run reactions at rates that are not those of mass-action for any choice of rate constants (e.g., the stable adversary may deactivate a reaction temporarily, even if all reactants are positive). We show that CRNs can robustly decide every predicate that is a finite Boolean combination of threshold predicates, where a threshold predicate is defined by taking a rational weighted sum of the inputs x ∈ ℝ^k_{≥ 0} and comparing to a constant, answering the question "Is ∑_{i = 1}^k w_i ⋅ x(i) > h?", for rational weights w_i and real threshold h. Turning to function computation, we show that CRNs can robustly compute any piecewise affine function with rational coefficients, where threshold predicates determine which affine piece to evaluate for a given input x.
Cite as

Kim Calabrese, David Doty, and Mina Latifi. Robust Predicate and Function Computation in Continuous Chemical Reaction Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{calabrese_et_al:LIPIcs.DISC.2025.19,
  author =	{Calabrese, Kim and Doty, David and Latifi, Mina},
  title =	{{Robust Predicate and Function Computation in Continuous Chemical Reaction Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{19:1--19:23},
  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.19},
  URN =		{urn:nbn:de:0030-drops-248368},
  doi =		{10.4230/LIPIcs.DISC.2025.19},
  annote =	{Keywords: chemical reaction networks, analog computation, mean-field limit}
}
Document
Survey
DOI: 10.4230/TGDK.3.2.1
Resilience in Knowledge Graph Embeddings

Authors: Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo

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

Abstract
In recent years, knowledge graphs have gained interest and witnessed widespread applications in various domains, such as information retrieval, question-answering, recommendation systems, amongst others. Large-scale knowledge graphs to this end have demonstrated their utility in effectively representing structured knowledge. To further facilitate the application of machine learning techniques, knowledge graph embedding models have been developed. Such models can transform entities and relationships within knowledge graphs into vectors. However, these embedding models often face challenges related to noise, missing information, distribution shift, adversarial attacks, etc. This can lead to sub-optimal embeddings and incorrect inferences, thereby negatively impacting downstream applications. While the existing literature has focused so far on adversarial attacks on KGE models, the challenges related to the other critical aspects remain unexplored. In this paper, we, first of all, give a unified definition of resilience, encompassing several factors such as generalisation, in-distribution generalization, distribution adaption, and robustness. After formalizing these concepts for machine learning in general, we define them in the context of knowledge graphs. To find the gap in the existing works on resilience in the context of knowledge graphs, we perform a systematic survey, taking into account all these aspects mentioned previously. Our survey results show that most of the existing works focus on a specific aspect of resilience, namely robustness. After categorizing such works based on their respective aspects of resilience, we discuss the challenges and future research directions.
Cite as

Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo. Resilience in Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 2, pp. 1:1-1:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sharma_et_al:TGDK.3.2.1,
  author =	{Sharma, Arnab and Kouagou, N'Dah Jean and Ngomo, Axel-Cyrille Ngonga},
  title =	{{Resilience in Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:38},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.2.1},
  URN =		{urn:nbn:de:0030-drops-248117},
  doi =		{10.4230/TGDK.3.2.1},
  annote =	{Keywords: Knowledge graphs, Resilience, Robustness}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.3
Multidimensional Usability Assessment in Spaceflight Analog Missions

Authors: Shivang Shelat, Katherine E. Homer, John A. Karasinski, and Jessica J. Marquez

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

Abstract
Software planning tools enable the self-scheduling of operational timelines during spaceflight, reducing reliance on ground support crews. Here, we assess analog crew perceptions of a planning tool’s usability across two space mission analogs with two validated questionnaires: the unidimensional System Usability Scale and the multidimensional User Experience Questionnaire. Critically, half the missions had assistive countermeasures integrated into the planning software interface whereas the other half did not. Correlation tests revealed high convergence between usability measures in the spaceflight analog setting. Group comparisons showed that the interface countermeasures enhanced several dimensions of usability, particularly for perceptions of the tool’s efficiency and dependability. These findings highlight the utility of a multidimensional approach to characterizing usability in order to capture fine-grained shifts in human-software dynamics, especially in spaceflight environments.
Cite as

Shivang Shelat, Katherine E. Homer, John A. Karasinski, and Jessica J. Marquez. Multidimensional Usability Assessment in Spaceflight Analog Missions. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 3:1-3:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shelat_et_al:OASIcs.SpaceCHI.2025.3,
  author =	{Shelat, Shivang and Homer, Katherine E. and Karasinski, John A. and Marquez, Jessica J.},
  title =	{{Multidimensional Usability Assessment in Spaceflight Analog Missions}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{3:1--3:9},
  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.3},
  URN =		{urn:nbn:de:0030-drops-239934},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.3},
  annote =	{Keywords: space usability, crew autonomy, self-scheduling software}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.26
Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks

Authors: David Andrew Green

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

Abstract
The Artemis programme seeks to develop and test concepts, hardware and approaches to support long term habitation of the Lunar surface, and future missions to Mars. In preparation for the Artemis missions determination of tasks to be performed, the functional requirements of such tasks and as mission duration extends whether physiological deconditioning becomes functionally significant, compromising the crew member’s ability to perform critical tasks on the surface, and/or upon return to earth [MoLo-LUNA – leveraging the Molo programme (and several other activities) - could become a key supporting activity for LUNA incl. validation of the Puppeteer offloading system itself via creation of a complementary MoLo-LUNA-LAB. Furthermore, the MoLo-LUNA programme could become a key facilitator of simulator suit instrumentation/definition, broader astronaut training activities and mission architecture development – including Artemis mission simulations. By employing a Puppeteer system external to the LUNA chamber hall it will optimise utilisation and cost-effectiveness of LUNA, and as such represents a critical service to future LUNA stakeholders. Furthermore, MoLo-LUNA would generate a unique data set that can be leveraged to predict de-conditioning on the Lunar surface - and thereby optimise functionality, and minimise mission risk – including informing the need for, and prescription of exercise countermeasures on the Lunar Surface and in transit. Thus, MoLo-LUNA offers a unique opportunity to place LUNA, and ESA as a key ongoing provider of evidence to define, optimise and support crew Artemis surface missions.
Cite as

David Andrew Green. Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{green:OASIcs.SpaceCHI.2025.26,
  author =	{Green, David Andrew},
  title =	{{Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{26:1--26:11},
  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.26},
  URN =		{urn:nbn:de:0030-drops-240166},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.26},
  annote =	{Keywords: Locomotion, hypogravity, modelling, Lunar}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.4
Differentiable Programming of Indexed Chemical Reaction Networks and Reaction-Diffusion Systems

Authors: Inhoo Lee, Salvador Buse, and Erik Winfree

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

Abstract
Many molecular systems are best understood in terms of prototypical species and reactions. The central dogma and related biochemistry are rife with examples: gene i is transcribed into RNA i, which is translated into protein i; kinase n phosphorylates substrate m; protein p dimerizes with protein q. Engineered nucleic acid systems also often have this form: oligonucleotide i hybridizes to complementary oligonucleotide j; signal strand n displaces the output of seesaw gate m; hairpin p triggers the opening of target q. When there are many variants of a small number of prototypes, it can be conceptually cleaner and computationally more efficient to represent the full system in terms of indexed species (e.g. for dimerization, M_p, D_pq) and indexed reactions (M_p + M_q → D_pq). Here, we formalize the Indexed Chemical Reaction Network (ICRN) model and describe a Python software package designed to simulate such systems in the well-mixed and reaction-diffusion settings, using a differentiable programming framework originally developed for large-scale neural network models, taking advantage of GPU acceleration when available. Notably, this framework makes it straightforward to train the models’ initial conditions and rate constants to optimize a target behavior, such as matching experimental data, performing a computation, or exhibiting spatial pattern formation. The natural map of indexed chemical reaction networks onto neural network formalisms provides a tangible yet general perspective for translating concepts and techniques from the theory and practice of neural computation into the design of biomolecular systems.
Cite as

Inhoo Lee, Salvador Buse, and Erik Winfree. Differentiable Programming of Indexed Chemical Reaction Networks and Reaction-Diffusion Systems. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.DNA.31.4,
  author =	{Lee, Inhoo and Buse, Salvador and Winfree, Erik},
  title =	{{Differentiable Programming of Indexed Chemical Reaction Networks and Reaction-Diffusion Systems}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.4},
  URN =		{urn:nbn:de:0030-drops-238534},
  doi =		{10.4230/LIPIcs.DNA.31.4},
  annote =	{Keywords: Differentiable Programming, Chemical Reaction Networks, Reaction-Diffusion Systems}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.10
Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems

Authors: Hamidreza Akef, Minki Hhan, and David Soloveichik

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

Abstract
Computing equilibrium concentrations of molecular complexes is generally analytically intractable and requires numerical approaches. In this work we focus on the polymer-monomer level, where indivisible molecules (monomers) combine to form complexes (polymers). Rather than employing free-energy parameters for each polymer, we focus on the athermic setting where all interactions preserve enthalpy. This setting aligns with the strongly bonded (domain-based) regime in DNA nanotechnology when strands can bind in different ways, but always with maximum overall bonding - and is consistent with the saturated configurations in the Thermodynamic Binding Networks (TBNs) model. Within this context, we develop an iterative algorithm for assigning polymer concentrations to satisfy detailed-balance, where on-target (desired) polymers are in high concentrations and off-target (undesired) polymers are in low. Even if not directly executed, our algorithm provides effective insights into upper bounds on concentration of off-target polymers, connecting combinatorial arguments about discrete configurations such as those in the TBN model to real-valued concentrations. We conclude with an application of our method to decreasing leak in DNA logic and signal propagation. Our results offer a new framework for design and verification of equilibrium concentrations when configurations are distinguished by entropic forces.
Cite as

Hamidreza Akef, Minki Hhan, and David Soloveichik. Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akef_et_al:LIPIcs.DNA.31.10,
  author =	{Akef, Hamidreza and Hhan, Minki and Soloveichik, David},
  title =	{{Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.10},
  URN =		{urn:nbn:de:0030-drops-238595},
  doi =		{10.4230/LIPIcs.DNA.31.10},
  annote =	{Keywords: Equilibrium concentrations, Thermodynamic Binding Networks, Monomer-polymer model, Detailed balance}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.17
An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT

Authors: Ahsan Sanaullah, Degui Zhi, and Shaojie Zhang

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
String matching problems in bioinformatics are typically for finding exact substring matches between a query and a reference text. Previous formulations often focus on maximum exact matches (MEMs). However, multiple occurrences of substrings of the query in the text that are long enough but not maximal may not be captured by MEMs. Such long matches can be informative, especially when the text is a collection of similar sequences such as genomes. In this paper, we describe a new type of match between a pattern and a text that aren't necessarily maximal in the query, but still contain useful matching information: locally maximal exact matches (LEMs). There are usually a large amount of LEMs, so we only consider those above some length threshold ℒ. These are referred to as long LEMs. The purpose of long LEMs is to capture substring matches between a query and a text that are not necessarily maximal in the pattern but still long enough to be important. Therefore efficient long LEMs finding algorithms are desired for these datasets. However, these datasets are too large to query on traditional string indexes. Fortunately, these datasets are very repetitive. Recently, compressed string indexes that take advantage of the redundancy in the data but retain efficient querying capability have been proposed as a solution. We therefore give an efficient algorithm for computing all the long LEMs of a query and a text in a BWT runs compressed string index. We describe an O(m+occ) expected time algorithm that relies on an O(r) words space string index for outputting all long LEMs of a pattern with respect to a text given the matching statistics of the pattern with respect to the text. Here m is the length of the query, occ is the number of long LEMs outputted, and r is the number of runs in the BWT of the text. The O(r) space string index we describe relies on an adaptation of the move data structure by Nishimoto and Tabei. We are able to support LCP[i] queries in constant time given SA[i]. In other words, we answer PLCP[i] queries in constant time. These PLCP queries enable the efficient long LEM query. Long LEMs may provide useful similarity information between a pattern and a text that MEMs may ignore. This information is particularly useful in pangenome and biobank scale haplotype panel contexts.
Cite as

Ahsan Sanaullah, Degui Zhi, and Shaojie Zhang. An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sanaullah_et_al:LIPIcs.WABI.2025.17,
  author =	{Sanaullah, Ahsan and Zhi, Degui and Zhang, Shaojie},
  title =	{{An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.17},
  URN =		{urn:nbn:de:0030-drops-239433},
  doi =		{10.4230/LIPIcs.WABI.2025.17},
  annote =	{Keywords: BWT, LEM, Long LEM, MEM, Run Length Compressed BWT, Move Data Structure, Pangenome}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.7
Sparser Abelian High Dimensional Expanders

Authors: Yotam Dikstein, Siqi Liu, and Avi Wigderson

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
The focus of this paper is the development of new elementary techniques for the construction and analysis of high dimensional expanders. Specifically, we present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group 𝔽₂ⁿ. Our expansion proofs use only linear algebra and combinatorial arguments. The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree exp(n^ε) for every ε > 0, improving on a construction by Golowich [Golowich, 2023] which achieves ε = 1/2. [Golowich, 2023] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmann posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph. Our second construction gives a 2-dimensional HDX of any polynomial degree exp(ε n) for any constant ε > 0, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [Liu et al., 2023]. Establishing coboundary expansion through Gromov’s "cone method" and the associated isoperimetric inequalities is the most intricate aspect of this construction. While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such "Hadamard-like" constructions in the hope that it will yield new HDXs.
Cite as

Yotam Dikstein, Siqi Liu, and Avi Wigderson. Sparser Abelian High Dimensional Expanders. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 7:1-7:98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.CCC.2025.7,
  author =	{Dikstein, Yotam and Liu, Siqi and Wigderson, Avi},
  title =	{{Sparser Abelian High Dimensional Expanders}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{7:1--7:98},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.7},
  URN =		{urn:nbn:de:0030-drops-237013},
  doi =		{10.4230/LIPIcs.CCC.2025.7},
  annote =	{Keywords: Local spectral expander, coboundary expander, Grassmannian expander}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.159
The Ultimate Signs of Second-Order Holonomic Sequences

Authors: Fugen Hagihara and Akitoshi Kawamura

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

Abstract
A real-valued sequence f = {f(n)}_{n ∈ ℕ} is said to be second-order holonomic if it satisfies a linear recurrence f (n + 2) = P (n) f (n + 1) + Q (n) f (n) for all sufficiently large n, where P, Q ∈ ℝ(x) are rational functions. We study the ultimate sign of such a sequence, i.e., the repeated pattern that the signs of f (n) follow for sufficiently large n. For each P, Q we determine all ultimate signs that f can have, and show how they partition the space of initial values of f. This completes the prior work by Neumann, Ouaknine and Worrell, who have settled some restricted cases. As a corollary, it follows that when P, Q have rational coefficients, f either has an ultimate sign of length 1, 2, 3, 4, 6, 8 or 12, or never falls into a repeated sign pattern. We also give a partial algorithm that finds the ultimate sign of f (or tells that there is none) in almost all cases.
Cite as

Fugen Hagihara and Akitoshi Kawamura. The Ultimate Signs of Second-Order Holonomic Sequences. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 159:1-159:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hagihara_et_al:LIPIcs.ICALP.2025.159,
  author =	{Hagihara, Fugen and Kawamura, Akitoshi},
  title =	{{The Ultimate Signs of Second-Order Holonomic Sequences}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{159:1--159: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.159},
  URN =		{urn:nbn:de:0030-drops-235363},
  doi =		{10.4230/LIPIcs.ICALP.2025.159},
  annote =	{Keywords: Holonomic sequences, ultimate signs, Skolem Problem, Positivity Problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.61
How to Compute the Volume in Low Dimension?

Authors: Arjan Cornelissen, Simon Apers, and Sander Gribling

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

Abstract
Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant.
Cite as

Arjan Cornelissen, Simon Apers, and Sander Gribling. How to Compute the Volume in Low Dimension?. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 61:1-61:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cornelissen_et_al:LIPIcs.ICALP.2025.61,
  author =	{Cornelissen, Arjan and Apers, Simon and Gribling, Sander},
  title =	{{How to Compute the Volume in Low Dimension?}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{61:1--61:18},
  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.61},
  URN =		{urn:nbn:de:0030-drops-234381},
  doi =		{10.4230/LIPIcs.ICALP.2025.61},
  annote =	{Keywords: Query complexity, computational geometry, quantum computing, volume estimation, high-precision limit}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.42
Range Counting Oracles for Geometric Problems

Authors: Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size n in a discrete space [Δ]^d, where queries can be made to an oracle that responds to orthogonal range counting requests. The query complexity of an optimization problem is measured by the number of oracle queries required to compute an estimator for the problem. We investigate two problems in this framework, the Euclidean Minimum Spanning Tree (MST) and Earth Mover Distance (EMD). For EMD, we show the existence of an estimator that approximates the cost of EMD with O(log Δ)-relative error and O(nΔ/(s^{1+1/d}))-additive error using O(s polylog Δ) range counting queries for any parameter s with 1 ≤ s ≤ n. Moreover, we prove that this bound is tight. For MST, we demonstrate that the weight of MST can be estimated within a factor of (1 ± ε) using Õ(√n) range counting queries.
Cite as

Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff. Range Counting Oracles for Geometric Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{driemel_et_al:LIPIcs.SoCG.2025.42,
  author =	{Driemel, Anne and Monemizadeh, Morteza and Oh, Eunjin and Staals, Frank and Woodruff, David P.},
  title =	{{Range Counting Oracles for Geometric Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{42:1--42:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.42},
  URN =		{urn:nbn:de:0030-drops-231941},
  doi =		{10.4230/LIPIcs.SoCG.2025.42},
  annote =	{Keywords: Range counting oracles, minimum spanning trees, Earth Mover’s Distance}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.56
Incompressible Functional Encryption

Authors: Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, and Aman Verma

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

Abstract
Incompressible encryption (Dziembowski, Crypto'06; Guan, Wichs, Zhandry, Eurocrypt'22) protects from attackers that learn the entire decryption key, but cannot store the full ciphertext. In incompressible encryption, the attacker must try to compress a ciphertext within pre-specified memory bound S before receiving the secret key. In this work, we generalize the notion of incompressibility to functional encryption. In incompressible functional encryption, the adversary can corrupt non-distinguishing keys at any point, but receives the distinguishing keys only after compressing the ciphertext to within S bits. An important efficiency measure for incompressible encryption is the ciphertext-rate (i.e., rate = |m|/|ct|). We give many new results for incompressible functional encryption for circuits, from minimal assumption of (non-incompressible) functional encryption, with 1) ct-rate-1/2 and short secret keys, 2) ct-rate-1 and large secret keys. Along the way, we also give a new incompressible attribute-based encryption for circuits from standard assumptions, with ct-rate-1/2 and short secret keys. Our results achieve optimal efficiency, as incompressible attribute-based/functional encryption with ct-rate-1 as well as short secret keys has strong barriers for provable security from standard assumptions. Moreover, our assumptions are minimal as incompressible attribute-based/functional encryption are strictly stronger than their non-incompressible counterparts.
Cite as

Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, and Aman Verma. Incompressible Functional Encryption. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 56:1-56:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.ITCS.2025.56,
  author =	{Goyal, Rishab and Koppula, Venkata and Rajasree, Mahesh Sreekumar and Verma, Aman},
  title =	{{Incompressible Functional Encryption}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{56:1--56:22},
  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.56},
  URN =		{urn:nbn:de:0030-drops-226849},
  doi =		{10.4230/LIPIcs.ITCS.2025.56},
  annote =	{Keywords: functional encryption, attribute-based encryption, incompressible encryption}
}
  • Refine by Type
  • 27 Document/PDF
  • 16 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 14 2025
  • 1 2024
  • 3 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 6 Kaufman, Tali
  • 4 Mass, David
  • 1 Akef, Hamidreza
  • 1 Apers, Simon
  • 1 Berens, Philipp
  • Show More...

  • Refine by Series/Journal
  • 22 LIPIcs
  • 2 OASIcs
  • 2 TGDK
  • 1 DagRep

  • Refine by Classification
  • 3 Theory of computation → Computational complexity and cryptography
  • 3 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Spectra of graphs
  • 2 Theory of computation → Dynamic programming
  • 2 Theory of computation → Fixed parameter tractability
  • Show More...

  • Refine by Keyword
  • 4 High dimensional expanders
  • 2 High Dimensional Expanders
  • 2 modelling
  • 1 Agreement testing
  • 1 Application to brachytherapy
  • 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