102 Search Results for "Wu, Nicolas"

Document
DOI: 10.4230/LIPIcs.SEA.2026.2
Different Scales of Randomness: Empirical Mixing Times of the Edge Switching and Curveball MCMC

Authors: Deepak Ajwani, Melvin Kallmayer, Alexander Leonhardt, Ulrich Meyer, Ryan O'Connor, and Manuel Penschuck

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The Fixed Degree Sequence Model (FDSM) asks for a uniform sample from the set of all simple graphs that match a prescribed degree sequence. It is typically implemented using Markov-Chain Monte-Carlo (MCMC) processes, such as Edge Switching or Curveball (and their variants). Yet despite decades of research, rigorous bounds on the mixing times of such processes remain impractical. Consequently, several experimental techniques have been used to derive "empirical lower bounds" on the mixing time. We address the following research questions: (1) Which commonly studied graph-theoretic properties serve as reliable empirical predictors for mixing of FDSM MCMC processes? (2) At what structural scales do these properties operate primarily (i. e., are they predominantly local or global in nature)? (3) How can these properties be characterised and quantified most effectively? To this end, we propose Claim, a novel systematic method to establish empirical lower bounds using learnt classifiers, and compare it to existing methods. Apart from interesting insights into the usage of machine learning for this problem, we also derive robust graph properties with respect to different randomisation algorithms. Although experimental in nature, these results may influence both theorist’s and algorithm engineer’s work on improved bounds and better algorithm respectively.
Cite as

Deepak Ajwani, Melvin Kallmayer, Alexander Leonhardt, Ulrich Meyer, Ryan O'Connor, and Manuel Penschuck. Different Scales of Randomness: Empirical Mixing Times of the Edge Switching and Curveball MCMC. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ajwani_et_al:LIPIcs.SEA.2026.2,
  author =	{Ajwani, Deepak and Kallmayer, Melvin and Leonhardt, Alexander and Meyer, Ulrich and O'Connor, Ryan and Penschuck, Manuel},
  title =	{{Different Scales of Randomness: Empirical Mixing Times of the Edge Switching and Curveball MCMC}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{2:1--2:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.2},
  URN =		{urn:nbn:de:0030-drops-260062},
  doi =		{10.4230/LIPIcs.SEA.2026.2},
  annote =	{Keywords: Mixing Time, Graph Randomization, Machine Learning, Edge Switching}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.19
Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

Authors: Nicole Funk, Annika Hennes, Johanna Hillebrand, and Sarah Sturm

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern, and Pena [John P. Dickerson et al., 2023] denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen [Matthew Jones et al., 2020]. For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.
Cite as

Nicole Funk, Annika Hennes, Johanna Hillebrand, and Sarah Sturm. Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{funk_et_al:LIPIcs.SWAT.2026.19,
  author =	{Funk, Nicole and Hennes, Annika and Hillebrand, Johanna and Sturm, Sarah},
  title =	{{Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.19},
  URN =		{urn:nbn:de:0030-drops-260551},
  doi =		{10.4230/LIPIcs.SWAT.2026.19},
  annote =	{Keywords: Clustering, Fairness, Approximation Algorithms, k-center, k-median, k-means}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.7
When to Ask a Question: Understanding Communication Strategies in Generative AI Tools

Authors: Charlotte Park, Kate Donahue, and Manish Raghavan

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Generative AI models differ from traditional machine learning tools in that they allow users to provide as much or as little information as they choose in their inputs. This flexibility often leads users to omit certain details, relying on the models to infer and fill in under-specified information based on distributional knowledge of user preferences. Such inferences may privilege majority viewpoints and disadvantage users with atypical preferences, raising concerns about fairness. Unlike more traditional recommender systems, LLMs can explicitly solicit more information from users through natural language. However, while directly eliciting user preferences could increase personalization and mitigate inequality, excessive querying places a burden on users who value efficiency. We develop a stylized model of user-LLM interaction and develop an objective that captures tradeoff between user burden and preference representation. Building on the observation that individual preferences are often correlated, we analyze how AI systems should balance inference and elicitation, characterizing the optimal amount of information to solicit before content generation. Ultimately, we show that information elicitation can mitigate the systematic biases of preference inference, enabling the design of generative tools that better incorporate diverse user perspectives while maintaining efficiency. We complement this theoretical analysis with an empirical evaluation illustrating the model’s predictions and exploring their practical implications.
Cite as

Charlotte Park, Kate Donahue, and Manish Raghavan. When to Ask a Question: Understanding Communication Strategies in Generative AI Tools. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{park_et_al:LIPIcs.FORC.2026.7,
  author =	{Park, Charlotte and Donahue, Kate and Raghavan, Manish},
  title =	{{When to Ask a Question: Understanding Communication Strategies in Generative AI Tools}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{7:1--7:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.7},
  URN =		{urn:nbn:de:0030-drops-259782},
  doi =		{10.4230/LIPIcs.FORC.2026.7},
  annote =	{Keywords: human-AI interaction, user modeling, personalization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.66
Fast Nearest Neighbor Search for 𝓁_p Metrics

Authors: Robert Krauthgamer and Nir Petruschka

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an n-point dataset X lying in a metric space ℳ, so that given a query point q ∈ ℳ, one can quickly return a point of X minimizing the distance to q. The efficiency of such a data structure is evaluated primarily by the amount of space it uses and the time required to answer a query. We focus on the fast query-time regime, which is crucial for modern large-scale applications, where datasets are massive and queries must be processed online, and is often modeled by query time poly(d log n) when ℳ is a d-dimensional normed space. Our main result is such a randomized data structure for NNS in 𝓁_p^d spaces, p > 2, that achieves p^{O(1) + log log p} approximation with fast query time and poly(dn) space. Our data structure improves, or is incomparable to, the state-of-the-art for the fast query-time regime from [Bartal and Gottlieb, TCS 2019] and [Krauthgamer, Petruschka and Sapir, FOCS 2025].
Cite as

Robert Krauthgamer and Nir Petruschka. Fast Nearest Neighbor Search for 𝓁_p Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{krauthgamer_et_al:LIPIcs.SoCG.2026.66,
  author =	{Krauthgamer, Robert and Petruschka, Nir},
  title =	{{Fast Nearest Neighbor Search for 𝓁\underlinep Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{66:1--66:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.66},
  URN =		{urn:nbn:de:0030-drops-258737},
  doi =		{10.4230/LIPIcs.SoCG.2026.66},
  annote =	{Keywords: Nearest neighbor search, metric embeddings, 𝓁\underlinep norm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.15
Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Authors: Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) obtained nearly three decades ago. We also establish an almost matching lower bound: There exist n points in the plane for which any Euclidean noncrossing Steiner (1+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.
Cite as

Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong. Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.15,
  author =	{Bhore, Sujoy and Kisfaludi‑Bak, S\'{a}ndor and Milenkovi\'{c}, Lazar and T\'{o}th, Csaba D. and W\k{e}grzycki, Karol and Wong, Sampson},
  title =	{{Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.15},
  URN =		{urn:nbn:de:0030-drops-258210},
  doi =		{10.4230/LIPIcs.SoCG.2026.15},
  annote =	{Keywords: geometric network design, spanners, crossing number, incidences}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.16
Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Authors: Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set P of n points in general position in the plane, the flip graph ℱ(P) has a vertex for each non-crossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by the exchange of a single edge (coined a flip). This flip graph has been intensively studied, lately with an emphasis on determining its diameter diam(ℱ(P)) for sets P of n points in convex position. For this case, the current best bounds are 14/9⋅n - O(1) ≤ diam(ℱ(P)) < 15/9⋅n - 3, obtained in a recent breakthrough work [Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber; SODA 2025]. The crucial tool for both the upper and lower bound are so-called conflict graphs, which the authors stated might be the key ingredient for determining the diameter (up to lower-order terms). In this paper, we pick up the concept of conflict graphs from the above-mentioned work and show that this tool is even more versatile than previously hoped. As our first main result, we use conflict graphs to show that computing the flip distance between two non-crossing spanning trees is NP-hard, even for point sets in convex position. Interestingly, the result still holds for more constrained flip operations, concretely, compatible flips (where the removed and the added edge do not cross) and rotations (where the removed and the added edge share an endpoint). Additionally, we present new insights on the diameter of the flip graph, by this directly extending the line of research from [BKUV SODA25]. Their lower bound is based on a constant-size pair of trees, one of which is of a type we refer to as stacked. We show that if one of the trees is stacked, then the lower bound is indeed optimal up to a constant term, that is, there exists a flip sequence of length at most 14/9⋅(n-1) to any other tree. Lastly, we improve the lower bound on the diameter of the flip graph ℱ(P) for n points in convex position to 11/7⋅n-o(n).
Cite as

Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist, Torsten Ueckerdt, and Birgit Vogtenhuber. Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bjerkevik_et_al:LIPIcs.SoCG.2026.16,
  author =	{Bjerkevik, H\r{a}vard Bakke and Dorfer, Joseph and Kleist, Linda and Ueckerdt, Torsten and Vogtenhuber, Birgit},
  title =	{{Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.16},
  URN =		{urn:nbn:de:0030-drops-258225},
  doi =		{10.4230/LIPIcs.SoCG.2026.16},
  annote =	{Keywords: Non-crossing, spanning tree, plane graph, flip graph, reconfiguration, diameter, complexity, NP-hard, edge exchange, compatible flip, rotation, happy edge property}
}
Document
DOI: 10.4230/OASIcs.PARMA-DITAM.2026.8
Performance Modeling & Mapping of LLM Inference on Heterogeneous Vectorized CGRAs

Authors: Dionysios Kefallinos, Georgios Alexandris, Alexis Maras, Panagiotis Chaidos, Manil Dev Gomony, Henk Corporaal, Dimitrios Soudris, and Sotirios Xydis

Published in: OASIcs, Volume 141, 17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026)

Abstract
Since the emergence of transformer-based models, the computational demands for Large Language Model (LLM) inference have been increasing exponentially, primarily due to their compounding parameter sizes, their structural complexity, and the use of non-linear functions. This tendency leads to the necessity of deploying them on low-power edge devices and DNN accelerators, to fuel next-generation agentic AI systems. Coarse-Grained Reconfigurable Architectures (CGRAs) have proven to be a compelling paradigm for edge acceleration, combining the programmability of general-purpose platforms with the high performance and energy efficiency associated with ASICs. In this work, we introduce an end-to-end performance modeling and mapping framework for LLM inference on heterogeneous CGRAs. Our methodology enables rapid exploration of the micro-architectural design space parameters, i.e., the number of processing elements, vector sizes, and memory configurations, by providing an accurate, explainable, and analytical CGRA performance modeling methodology, with an average cycle error of 0.9%. Architecturally, we build upon R-Blocks, a heterogeneous CGRA platform, and extend it to support floating-point arithmetic operations as well as a full-stack compilation and mapping flow for both full (FP32) and quantized (INT8) Llama2 models. The proposed methodology, evaluated on a 22nm technology node, achieves superior peak performance per Watt compared to related works such as REVAMP and CFEACT (1.8× and 2.8× respectively).
Cite as

Dionysios Kefallinos, Georgios Alexandris, Alexis Maras, Panagiotis Chaidos, Manil Dev Gomony, Henk Corporaal, Dimitrios Soudris, and Sotirios Xydis. Performance Modeling & Mapping of LLM Inference on Heterogeneous Vectorized CGRAs. In 17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026). Open Access Series in Informatics (OASIcs), Volume 141, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kefallinos_et_al:OASIcs.PARMA-DITAM.2026.8,
  author =	{Kefallinos, Dionysios and Alexandris, Georgios and Maras, Alexis and Chaidos, Panagiotis and Gomony, Manil Dev and Corporaal, Henk and Soudris, Dimitrios and Xydis, Sotirios},
  title =	{{Performance Modeling \& Mapping of LLM Inference on Heterogeneous Vectorized CGRAs}},
  booktitle =	{17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026)},
  pages =	{8:1--8:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-416-1},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{141},
  editor =	{Baroffio, Davide and Busia, Paola and Denisov, Lev and Shukla, Nitin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.PARMA-DITAM.2026.8},
  URN =		{urn:nbn:de:0030-drops-256752},
  doi =		{10.4230/OASIcs.PARMA-DITAM.2026.8},
  annote =	{Keywords: Edge AI, LLM, CGRA, Heterogeneous Architectures, Performance Modeling, Hardware Acceleration, Low Power Computing}
}
Document
Research
DOI: 10.4230/TGDK.4.1.1
On the Computational Cost of Knowledge Graph Embeddings

Authors: Victor Charpenay, Mansour Zoubeirou A Mayaki, and Antoine Zimmermann

Published in: TGDK, Volume 4, Issue 1 (2026). Transactions on Graph Data and Knowledge, Volume 4, Issue 1

Abstract
Over a decade, numerous Knowledge Graph Embedding (KGE) models have been designed and evaluated on reference datasets, always with increasing performance. In this paper, we re-evaluate these models with respect to their computational efficiency during training, by estimating the computational cost of the procedure expressed in floating-point operations. We design a cost model based on analytical expressions and apply it on a collection of 20 KGE models, representative of the state-of-the-art. We show that dimensionality or parameter efficiency, used in the literature to compare models with each other, are not suitable to evaluate the true cost of models. Through fixed-budget experiments, a novel approach to evaluate KGE models based on cost estimates, we re-assess the relative performance of model families compared to the state-of-the-art. Bilinear models such as ComplEx underperform with a low computational budget while hyperbolic linear models appear to offer no particular benefit compared to simpler Euclidian models, especially the MuRE model. Neural models, such as ConvE or CompGCN, achieve reasonable performance in the literature but their high computational cost appears unnecessary when compared with other models. The trade-off between efficiency and expressivity of both linear and neural models is to be further explored.
Cite as

Victor Charpenay, Mansour Zoubeirou A Mayaki, and Antoine Zimmermann. On the Computational Cost of Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 4, Issue 1, pp. 1:1-1:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{charpenay_et_al:TGDK.4.1.1,
  author =	{Charpenay, Victor and Zoubeirou A Mayaki, Mansour and Zimmermann, Antoine},
  title =	{{On the Computational Cost of Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:30},
  ISSN =	{2942-7517},
  year =	{2026},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.4.1.1},
  URN =		{urn:nbn:de:0030-drops-256863},
  doi =		{10.4230/TGDK.4.1.1},
  annote =	{Keywords: Knowledge Graph Embedding, Parameter Efficiency, Computational Budget, Green AI}
}
Document
Survey
DOI: 10.4230/TGDK.4.1.2
Temporal Modelling in Cultural Heritage Knowledge Graphs: Use Cases, Requirements, Evaluation, and Decision Support

Authors: Oleksandra Bruns, Jörg Waitelonis, Jeff Z. Pan, and Harald Sack

Published in: TGDK, Volume 4, Issue 1 (2026). Transactions on Graph Data and Knowledge, Volume 4, Issue 1

Abstract
Our culture, history and world are in constant motion, continuously shaped by the flow of time, evolving narratives, and shifting relationships. Capturing this temporal complexity within cultural heritage (CH) knowledge graphs is essential for preserving the dynamic nature of human heritage. However, standard RDF predicates fail to effectively model the temporal aspects of cultural data, such as changing facts, evolving relationships, and temporal concepts. Over the past two decades, a variety of RDF-based approaches have been proposed to address this limitation, yet guidance is missing on which method best suits specific CH contexts. This paper presents a systematic evaluation of temporal RDF modelling approaches from a CH perspective. Based on an analysis of real-world CH use cases, core temporal requirements are identified that reflect both modelling expressivity and practical concerns. Six prominent approaches - RDF*, tRDF, Named Graphs, Singleton Property, N-ary Relations, and 4D Fluents - are assessed across these requirements. Our findings reveal that no single solution fits all scenarios, but suitable approaches can be selected based on project-specific priorities. To support practitioners, a decision-support tool is introduced to guide them in selecting the most suitable extension for their specific needs. This work provides practical guidance for CH modelling and contributes to the broader development of temporally aware Linked Data.
Cite as

Oleksandra Bruns, Jörg Waitelonis, Jeff Z. Pan, and Harald Sack. Temporal Modelling in Cultural Heritage Knowledge Graphs: Use Cases, Requirements, Evaluation, and Decision Support. In Transactions on Graph Data and Knowledge (TGDK), Volume 4, Issue 1, pp. 2:1-2:46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{bruns_et_al:TGDK.4.1.2,
  author =	{Bruns, Oleksandra and Waitelonis, J\"{o}rg and Pan, Jeff Z. and Sack, Harald},
  title =	{{Temporal Modelling in Cultural Heritage Knowledge Graphs: Use Cases, Requirements, Evaluation, and Decision Support}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{2:1--2:46},
  ISSN =	{2942-7517},
  year =	{2026},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.4.1.2},
  URN =		{urn:nbn:de:0030-drops-256871},
  doi =		{10.4230/TGDK.4.1.2},
  annote =	{Keywords: Temporal Data Representation, RDF Extensions, Cultural Heritage, Knowledge Graphs}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.7
What Obstructed Skies Teach Us About Satellite Internet

Authors: Bhaskar Kataria, Hammas Bin Tanveer, Rishab Nithyanand, and Rachee Singh

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Low Earth Orbit satellite networks can extend Internet connectivity to remote areas where traditional broadband infrastructure is unavailable. However physical obstructions, e.g., dense forest cover, can interfere with satellite communication by blocking the user terminal’s line of sight to the satellite constellation. Unfortunately the impact of such obstructions on the connectivity of user terminals is not well studied. We bridge this gap by conducting an experimental study of how physical obstructions influence satellite network connectivity. Through controlled experiments using a purpose-built hardware testbed, we quantify the performance degradation caused by physical obstructions to user terminals. Our results show that obstructions increase round-trip latency by an average of 4% and packet loss by 0.3%. Obstructions cause user terminals to connect to a different satellite than the unobstructed terminal approximately 15% of the time. We find evidence of a previously undocumented adaptive mechanism we call responsive routing, where the satellite network switches obstructed terminals to alternative satellites within the standard 15-second interval between typical handovers. Our data is publicly available as supplementary material to this article.
Cite as

Bhaskar Kataria, Hammas Bin Tanveer, Rishab Nithyanand, and Rachee Singh. What Obstructed Skies Teach Us About Satellite Internet. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kataria_et_al:OASIcs.NINeS.2026.7,
  author =	{Kataria, Bhaskar and Tanveer, Hammas Bin and Nithyanand, Rishab and Singh, Rachee},
  title =	{{What Obstructed Skies Teach Us About Satellite Internet}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{7:1--7:25},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.7},
  URN =		{urn:nbn:de:0030-drops-255923},
  doi =		{10.4230/OASIcs.NINeS.2026.7},
  annote =	{Keywords: Satellite Internet, Starlink, Network Measurement, LEO Satellites, Obstructions}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.11
Stealthy Low Earth Orbit Satellite-To-Ground Quantum Communication

Authors: Guanqun Song and Ting Zhu

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Quantum key distribution (QKD) leveraging satellites holds promise for global-scale secure communication. However, its practical deployment is threatened by the inherent predictability of satellite orbits, which exposes quantum channels to targeted eavesdropping attacks, compromising the physical-layer security guarantees of QKD. Through security analysis, we demonstrate that such attacks can drastically increase the quantum bit error rate (QBER) from 4.7% to 27.5%, effectively disrupting secure key generation. To address this fundamental vulnerability, we introduce a novel defense framework that integrates two strategies: (1) Stealthy Deployment, which obfuscates quantum satellites within massive LEO constellations to drastically increase an adversary’s search space, and (2) Dynamic Re-routing, which is an adaptive countermeasure that re-establishes QKD sessions via alternative paths upon eavesdropping detection. Evaluated through large-scale simulations incorporating real-world satellite data, our framework demonstrates up to a 90% improvement in key generation rate under active attack, ensuring robust and resilient satellite-based QKD without modifications to the underlying quantum hardware.
Cite as

Guanqun Song and Ting Zhu. Stealthy Low Earth Orbit Satellite-To-Ground Quantum Communication. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 11:1-11:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{song_et_al:OASIcs.NINeS.2026.11,
  author =	{Song, Guanqun and Zhu, Ting},
  title =	{{Stealthy Low Earth Orbit Satellite-To-Ground Quantum Communication}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{11:1--11:26},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.11},
  URN =		{urn:nbn:de:0030-drops-255963},
  doi =		{10.4230/OASIcs.NINeS.2026.11},
  annote =	{Keywords: LEO satellites, QKD, quantum communication}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.17
Don’t Get Caught, Keep Your Onions in a Vault

Authors: Humza Ikram, Rumaisa Habib, Muaz Ali, and Zartash Afzal Uzmi

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
When web applications wish to operate anonymously, they routinely host themselves as "Hidden Services" in the Tor network. However, these services are frequently threatened by deanonymization attacks, whereby their IP address and location may be inferred by the authorities. We present VaulTor, a novel architecture for the Tor network that ensures an extra layer of security for the Hidden Services against deanonymization attacks. In this new architecture, a volunteer (vault) is incentivized to host the web application content on behalf of the Hidden Service. The vault runs the hosted application in a Trusted Execution Environment (TEE) and becomes the point of contact for interested clients. This setup can substantially reduce the uptime requirement of the original Hidden Service provider, thereby significantly decreasing the chance of deanonymization attacks against them. Using a vault node in place of the hidden service node does not cause any noticeable performance degradation when accessing the hosted content.
Cite as

Humza Ikram, Rumaisa Habib, Muaz Ali, and Zartash Afzal Uzmi. Don’t Get Caught, Keep Your Onions in a Vault. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ikram_et_al:OASIcs.NINeS.2026.17,
  author =	{Ikram, Humza and Habib, Rumaisa and Ali, Muaz and Uzmi, Zartash Afzal},
  title =	{{Don’t Get Caught, Keep Your Onions in a Vault}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{17:1--17:24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.17},
  URN =		{urn:nbn:de:0030-drops-256027},
  doi =		{10.4230/OASIcs.NINeS.2026.17},
  annote =	{Keywords: Tor, anonymity, Hidden Services, Trusted Execution Environments}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.18
TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control

Authors: Peter Schafhalter, Alexander Krentsel, Hongbo Wei, Joseph E. Gonzalez, Sylvia Ratnasamy, Scott Shenker, and Ion Stoica

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Autonomous driving system progress has been driven by improvements in machine learning (ML) models, whose computational demands now exceed what edge devices alone can provide. The cloud offers abundant compute, but the network has long been treated as an unreliable bottleneck rather than a co-equal part of the autonomous vehicle control loop. We argue that this separation is no longer tenable: safety-critical autonomy requires co-design of control, models, and network resource allocation itself. We introduce TURBO, a cloud-augmented control framework that addresses this challenge, formulating bandwidth allocation and control pipeline configuration across both the car and cloud as a joint optimization problem. TURBO maximizes benefit to the car while guaranteeing safety in the face of highly variable network conditions. We implement TURBO and evaluate it in both simulation and real-world deployment, showing it can improve average accuracy by up to 15.6%pt over existing on-vehicle-only pipelines. Our code is made available at www.github.com/NetSys/turbo.
Cite as

Peter Schafhalter, Alexander Krentsel, Hongbo Wei, Joseph E. Gonzalez, Sylvia Ratnasamy, Scott Shenker, and Ion Stoica. TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 18:1-18:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schafhalter_et_al:OASIcs.NINeS.2026.18,
  author =	{Schafhalter, Peter and Krentsel, Alexander and Wei, Hongbo and Gonzalez, Joseph E. and Ratnasamy, Sylvia and Shenker, Scott and Stoica, Ion},
  title =	{{TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{18:1--18:34},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.18},
  URN =		{urn:nbn:de:0030-drops-256039},
  doi =		{10.4230/OASIcs.NINeS.2026.18},
  annote =	{Keywords: autonomous vehicles, bandwidth allocation, cloud computing, edge computing, machine learning}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.24
SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing

Authors: Siddhant Ray, Xi Jiang, Jack Luo, Nick Feamster, and Junchen Jiang

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Low Latency, Low Loss, and Scalable Throughput (L4S), as an emerging router-queue management technique, has seen steady deployment in the industry. An L4S-enabled router assigns each packet to the queue based on the packet header marking. Currently, L4S employs per-flow queue selection, i.e., all packets of a flow are marked the same way and thus use the same queues, even though each packet is marked separately. However, this may hurt tail latency and latency-sensitive applications because transient congestion and queue buildups may only affect a fraction of packets in a flow. We present SwiftQueue, a new L4S queue-selection strategy in which a sender uses a novel per-packet latency predictor to pinpoint which packets likely have latency spikes or drops. The insight is that many packet-level latency variations result from complex interactions among recent packets at shared router queues. Yet, these intricate packet-level latency patterns are hard to learn efficiently by traditional models. Instead, SwiftQueue uses a custom Transformer, which is well-studied for its expressiveness on sequential patterns, to predict the next packet’s latency based on the latencies of recently received ACKs. Based on the predicted latency of each outgoing packet, SwiftQueue’s sender dynamically marks the L4S packet header to assign packets to potentially different queues, even within the same flow. Using real network traces, we show that SwiftQueue is 45-65% more accurate in predicting latency and its variations than state-of-art methods. Based on its latency prediction, SwiftQueue reduces the tail latency for L4S-enabled flows by 36-45%, compared with the existing L4S queue-selection method.
Cite as

Siddhant Ray, Xi Jiang, Jack Luo, Nick Feamster, and Junchen Jiang. SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 24:1-24:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ray_et_al:OASIcs.NINeS.2026.24,
  author =	{Ray, Siddhant and Jiang, Xi and Luo, Jack and Feamster, Nick and Jiang, Junchen},
  title =	{{SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{24:1--24:29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.24},
  URN =		{urn:nbn:de:0030-drops-256093},
  doi =		{10.4230/OASIcs.NINeS.2026.24},
  annote =	{Keywords: Latency prediction, L4S Queue Management}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.5
OrbitalBrain: A Distributed Framework for Training ML Models in Space

Authors: Om Chabra, Chenning Li, Kevin Hsieh, Santiago Segarra, Behnaz Arzani, Peder Olsen, and Ranveer Chandra

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Earth observation nanosatellites capture high-resolution photos of the Earth in near real-time. These images increasingly support ML applications that are critical for safety and response, such as forest fire and flood detection. However, the downlink bandwidth is limited, resulting in days or weeks of delay from image capture to training. In this work, we propose OrbitalBrain, an efficient in-space distributed ML training framework that leverages limited and predictable satellite compute, bandwidth, and power to intelligently balance data transfer, model aggregation, and local training. Our evaluations demonstrate that OrbitalBrain achieves 1.52×-12.4× speedup in time-to-accuracy while always reaching a higher final model accuracy compared to state-of-the-art ground-based or federated learning baselines. Furthermore, our approach is complementary to satellite imagery capturing and downloading, enhancing the overall efficiency of satellite-based applications.
Cite as

Om Chabra, Chenning Li, Kevin Hsieh, Santiago Segarra, Behnaz Arzani, Peder Olsen, and Ranveer Chandra. OrbitalBrain: A Distributed Framework for Training ML Models in Space. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chabra_et_al:OASIcs.NINeS.2026.5,
  author =	{Chabra, Om and Li, Chenning and Hsieh, Kevin and Segarra, Santiago and Arzani, Behnaz and Olsen, Peder and Chandra, Ranveer},
  title =	{{OrbitalBrain: A Distributed Framework for Training ML Models in Space}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{5:1--5:32},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.5},
  URN =		{urn:nbn:de:0030-drops-255907},
  doi =		{10.4230/OASIcs.NINeS.2026.5},
  annote =	{Keywords: Satellite networks, Distributed machine learning, Federated learning, Earth observation, In-orbit computing}
}
  • Refine by Type
  • 102 Document/PDF
  • 92 Document/HTML

  • Refine by Publication Year
  • 24 2026
  • 63 2025
  • 3 2024
  • 6 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 3 Lissandrini, Matteo
  • 3 Wattenhofer, Roger
  • 2 Bhore, Sujoy
  • 2 Biswas, Russa
  • 2 Bonifati, Angela
  • Show More...

  • Refine by Series/Journal
  • 69 LIPIcs
  • 16 OASIcs
  • 3 LITES
  • 13 TGDK
  • 1 DagMan

  • Refine by Classification
  • 5 Information systems → Graph-based database models
  • 4 Computing methodologies → Knowledge representation and reasoning
  • 3 Computer systems organization → Distributed architectures
  • 3 Computing methodologies → Artificial intelligence
  • 3 Computing methodologies → Machine learning approaches
  • Show More...

  • Refine by Keyword
  • 5 Large Language Models
  • 4 Knowledge Graphs
  • 4 blockchain
  • 2 Approximation Algorithms
  • 2 Ethereum
  • 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