84 Search Results for "Chen, Chao"

Document
DOI: 10.4230/LIPIcs.SEA.2026.21
An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem

Authors: Luke Hawranick, Matthew Williamson, Jacob Restanio, K. Subramani, and Cody Klingler

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

Abstract
In this paper, we perform an experimental study of approximation algorithms for the unweighted tree augmentation problem (UTAP). Our goal is to establish a baseline performance for several existing approximation algorithms on actual instances rather than worst-case instances. In particular, we are interested in whether the algorithms' performance in practical instances is consistent with their worst-case guarantee rankings. We are also interested in whether preprocessing times, implementation difficulties, and running times justify the use of an algorithm in practice. We profile and analyze three approximation algorithms from the literature against a simple randomized algorithm. The performance of each algorithm was evaluated using metrics for space usage, running time, and solution quality. We found that the simple randomized algorithm is very competitive with the approximation algorithms and that the algorithms do not necessarily rank according to their theoretical guarantees. The randomized algorithm is easier to implement and understand, using less space than any of the more sophisticated approximation algorithms.
Cite as

Luke Hawranick, Matthew Williamson, Jacob Restanio, K. Subramani, and Cody Klingler. An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hawranick_et_al:LIPIcs.SEA.2026.21,
  author =	{Hawranick, Luke and Williamson, Matthew and Restanio, Jacob and Subramani, K. and Klingler, Cody},
  title =	{{An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{21:1--21:15},
  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.21},
  URN =		{urn:nbn:de:0030-drops-260259},
  doi =		{10.4230/LIPIcs.SEA.2026.21},
  annote =	{Keywords: Graphs, Networks, Tree Augmentation, Approximation Algorithms, Empirical}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.17
Incremental Strongly Connected Components with Predictions

Authors: Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, and Nathan Vosburg

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

Abstract
Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework to design a learned data structure for the incremental strongly connected components (SCC) problem. In this problem, the n vertices of a graph are known a priori and the m directed edges arrive over time. The goal is to efficiently maintain the strongly connected components of the graph after each insert. Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions to support fast inserts. We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error. We also implement our data structure and perform experiments on real datasets. Our empirical results show that the theory is predictive of practical runtime improvements.
Cite as

Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, and Nathan Vosburg. Incremental Strongly Connected Components with Predictions. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.SWAT.2026.17,
  author =	{Deng, Ronald and McCauley, Samuel and Niaparast, Aidin and Niaparast, Helia and Ptak, Bennett and Quintanilla, Shirel and Singh, Shikha and Vosburg, Nathan},
  title =	{{Incremental Strongly Connected Components with Predictions}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{17:1--17:16},
  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.17},
  URN =		{urn:nbn:de:0030-drops-260530},
  doi =		{10.4230/LIPIcs.SWAT.2026.17},
  annote =	{Keywords: algorithms with predictions, learning augmented algorithms, incremental graph algorithms, strongly connected components, data structures}
}
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.SWAT.2026.23
Indexing Range Maximum-Sum Segment Queries with Offsets

Authors: Seungbum Jo and Dominik Köppl

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

Abstract
Given an array of n real numbers, the maximum segment sum (MSS) problem is to find a contiguous subarray that has the largest sum. While the MSS problem can be solved optimally with Kadane’s algorithm in O(n) time, the study of its indexing version spawned new extensions such as (a) retrieving the MSS after subtracting a query offset parameter for all array entries or (b) retrieving the MSS for arbitrary query ranges. We here study the combination of both problems (a) and (b), which requires retrieving the MSS for arbitrary query ranges after subtracting a query offset parameter for all array entries. For that, we present an index whose query time is only slower than the best known for (a) by a factor of O(log n). In detail, our index uses O(n log n) space, supports queries in O(log² n) time, and can be constructed in O(n log³ n) time. As side results, we study our combined problem in the context of run-length compressed input, and also deduce a solution for (a) that works in run-length compressed space and time. Finally we give supportive lower bounds for our query problem, showing that there is only a polylogarithmic gap of improvement left.
Cite as

Seungbum Jo and Dominik Köppl. Indexing Range Maximum-Sum Segment Queries with Offsets. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:LIPIcs.SWAT.2026.23,
  author =	{Jo, Seungbum and K\"{o}ppl, Dominik},
  title =	{{Indexing Range Maximum-Sum Segment Queries with Offsets}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{23:1--23:16},
  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.23},
  URN =		{urn:nbn:de:0030-drops-260597},
  doi =		{10.4230/LIPIcs.SWAT.2026.23},
  annote =	{Keywords: maximum segment sum, data structure, range query}
}
Document
DOI: 10.4230/OASIcs.AEiC.2026.2
Discovering and Repairing Flaws in C Binaries Without Requiring Codebase and Instrumentation

Authors: Diogo Ferreira and Ibéria Medeiros

Published in: OASIcs, Volume 143, 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)

Abstract
Industrial and embedded software systems frequently integrate various third-party components sourced from diverse providers into their codebases. These systems are commonly developed in C, a language known for its lack of variable bounds checking, making it vulnerable to Buffer Overflows (BOs), which, when exploited, can cause severe damage. Consequently, the binary code resulting from vulnerable C programs is also vulnerable and remains so in the final products. Fixing these software systems is challenging because only binary code is available. This paper presents PatchBin, a binary patching tool to automatically fix BO vulnerabilities and validate the effectiveness of fixes while ensuring no new flaws are introduced. The approach involves a combination of fuzzing, reverse static analysis and static rewriting techniques to, respectively, (i) identify possible malicious inputs that can trigger BOs, (ii) find their root cause by employing reverse data flow analysis, and (iii) remove them by rewriting the binary code with effective validation, thus generating a new binary without the original flaws and new ones. Experimental evaluations with synthetic and real-world applications demonstrated that PatchBin detects and fixes BO in binary programs without introducing new vulnerabilities. The results showed that PatchBin is an important aid for industrial partners, enabling them to test and fix their products, including third-party components, without access to source code, but only to binary code.
Cite as

Diogo Ferreira and Ibéria Medeiros. Discovering and Repairing Flaws in C Binaries Without Requiring Codebase and Instrumentation. In 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026). Open Access Series in Informatics (OASIcs), Volume 143, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ferreira_et_al:OASIcs.AEiC.2026.2,
  author =	{Ferreira, Diogo and Medeiros, Ib\'{e}ria},
  title =	{{Discovering and Repairing Flaws in C Binaries Without Requiring Codebase and Instrumentation}},
  booktitle =	{30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)},
  pages =	{2:1--2:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-425-3},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{143},
  editor =	{Filieri, Antonio and Backeman, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AEiC.2026.2},
  URN =		{urn:nbn:de:0030-drops-259209},
  doi =		{10.4230/OASIcs.AEiC.2026.2},
  annote =	{Keywords: Buffer Overflow Vulnerabilities, Binary Patching, Reverse Engineering, Static Analysis, Software Security}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.32
Tensor Computation of Euler Characteristic Functions and Transforms

Authors: Jessi Cisewski-Kehe, Brittany Terese Fasy, Alexander McCleary, and Eli Quist

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

Abstract
The weighted Euler characteristic transform (WECT) and Euler characteristic function (ECF) have proven to be useful tools in a variety of applications. However, current methods for computing these functions are either not optimized for GPU computation or do not scale to higher-dimensional settings. In this work, we present a tensor-based framework for computing such topological descriptors which is highly optimized for GPU architectures and works in full generality across simplicial and cubical complexes of arbitrary dimension. Experimentally, the framework demonstrates significant speedups over existing methods when computing the WECT and ECF across a variety of two- and three-dimensional datasets. Computation of these transforms is implemented in a publicly available Python package called pyECT.
Cite as

Jessi Cisewski-Kehe, Brittany Terese Fasy, Alexander McCleary, and Eli Quist. Tensor Computation of Euler Characteristic Functions and Transforms. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cisewskikehe_et_al:LIPIcs.SoCG.2026.32,
  author =	{Cisewski-Kehe, Jessi and Fasy, Brittany Terese and McCleary, Alexander and Quist, Eli},
  title =	{{Tensor Computation of Euler Characteristic Functions and Transforms}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{32:1--32:17},
  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.32},
  URN =		{urn:nbn:de:0030-drops-258380},
  doi =		{10.4230/LIPIcs.SoCG.2026.32},
  annote =	{Keywords: Topological data analysis, weighted Euler characteristic transform, Euler characteristic function, tensor computation, GPU computation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.71
Approximating Euclidean Shallow-Light Trees

Authors: Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, and Tianyi Zhang

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

Abstract
For a weighted graph G = (V, E, w) and a designated source vertex s ∈ V, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source s and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an (α, β)-SLT of G w.r.t. s ∈ V is a spanning tree of G with root-stretch α (preserving all distances between s and all other vertices up to a factor of α) and lightness β (its weight is at most β times the weight of a minimum spanning tree of G). It was shown in the early 1990s that (1) for any graph, any source, and any ε > 0, there is a (1 + ε, O(1/ε))-SLT, and (2) there exist graphs for which β = Ω(1/ε) for any (1+ε,β)-SLT. The focus of this work is on SLTs in low-dimensional Euclidean spaces, which are of special interest for some applications of SLTs, in geometric network optimization problems. The aforementioned existential lower bound applies to Euclidean plane, as well. It was shown more than a decade ago that (1) by using Steiner points, one can reduce the lightness bound from O(1/ε) to O(√{1/ε}), and (2) there exist point sets in the plane for which β = Ω(√{1/ε}) for any Steiner (1+ε,β)-SLT. These tight existential bounds for the Euclidean case yield approximation factors of O(1/ε) and O(√{1/ε}) on the minimum weight of any non-Steiner and Steiner tree with root-stretch 1+ε, respectively. Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards resolving this question by presenting two bicriteria approximation algorithms. For any ε > 0, a set P of n points in constant-dimensional Euclidean space and a source s ∈ P, our first (respectively, second) algorithm returns, in O(n log n ⋅ polylog(ε^{-1})) time, a non-Steiner (resp., Steiner) tree with root-stretch 1+O(ε log ε^{-1}) and weight at most O(opt_ε ⋅ log² ε^{-1}) (resp., O(opt_ε ⋅ log ε^{-1})), where opt_ε denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch 1+ε.
Cite as

Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, and Tianyi Zhang. Approximating Euclidean Shallow-Light Trees. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2026.71,
  author =	{Le, Hung and Solomon, Shay and Than, Cuong and T\'{o}th, Csaba D. and Zhang, Tianyi},
  title =	{{Approximating Euclidean Shallow-Light Trees}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{71:1--71:16},
  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.71},
  URN =		{urn:nbn:de:0030-drops-258789},
  doi =		{10.4230/LIPIcs.SoCG.2026.71},
  annote =	{Keywords: geometric network design, optimization, shallow-light tree, Steiner point}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.87
Robustness of Persistent Topological Features and Minimum Homological Cuts

Authors: Pepijn Roos Hoefgeest and Lucas Slot

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

Abstract
Persistent homology is a popular method for computing topological features of (metric) data. Standard approaches based on the Čech or Rips filtration are stable under small perturbations of the data, but highly sensitive to outliers. This lack of robustness has been frequently addressed in the literature. In this paper, we take a novel perspective by asking the following question: When can we guarantee that an observed persistent feature (a bar) is inherent to the underlying data in the presence of a limited number of unknown, arbitrary outliers. We formalize this question by introducing the notion of adversarial robustness, and study the problem of deciding whether a given bar in the barcode of a filtered simplicial complex is adversarially robust. We show that this problem is essentially equivalent to a homological variant of the minimum cut problem in simplicial complexes, which we believe to be of independent interest. As our main technical contribution, we provide the first computational complexity results for this problem, consisting of an efficient algorithm in 0-dimensional homology, NP-hardness for the general problem, and an efficient algorithm for codimension-1 in n-dimensional complexes embedded in ℝⁿ. We also analyze its natural linear programming relaxation, whose dual defines a homological analog of the max-flow problem in graphs. We show that a max-flow/min-cut theorem does not hold in our setting, implying that the LP relaxation is not tight in general. Finally, in the special case of the Rips filtration, we provide a global heuristic based on the Hausdorff distance that guarantees adversarial robustness of sufficiently long bars. This connects adversarial robustness to standard stability theorems in persistent homology.
Cite as

Pepijn Roos Hoefgeest and Lucas Slot. Robustness of Persistent Topological Features and Minimum Homological Cuts. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rooshoefgeest_et_al:LIPIcs.SoCG.2026.87,
  author =	{Roos Hoefgeest, Pepijn and Slot, Lucas},
  title =	{{Robustness of Persistent Topological Features and Minimum Homological Cuts}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{87:1--87:15},
  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.87},
  URN =		{urn:nbn:de:0030-drops-258636},
  doi =		{10.4230/LIPIcs.SoCG.2026.87},
  annote =	{Keywords: Topological Data Analysis, Persistent Homology, Min-cut Max-flow, Robustness, Vietoris-Rips Filtration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.94
Mixup Barcodes: Quantifying Geometric-Topological Interactions Between Point Clouds

Authors: Hubert Wagner, Nickolas Arustamyan, Matthew Wheeler, and Peter Bubenik

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

Abstract
We propose a novel geometric-topological descriptor called a mixup barcode. Intuitively, it characterizes the shape of a point cloud as well as its spatial relationship with another point cloud embedded in the same ambient space. More technically, it enriches a standard persistence barcode with information on the image persistent homology. In three dimensions it captures natural spatial relationships like overlap and surrounding; in higher dimensions more intricate spatial relationships are captured. We provide a theoretical setup and a simple algorithm for mixup barcodes. As a proof of concept, we explore data arising in a geometric-topological problem from machine learning. Specifically, we take first steps towards verifying a hypothesis stating that geometric-topological relationships within intermediate point cloud representations in an artificial neural network can hinder its training. More broadly, our experiments suggest that mixup barcodes are useful for characterizing spatial relationships and spatial interactions (i.e. the evolution of spatial relationships) that are hard to directly visualize or capture using standard methods.
Cite as

Hubert Wagner, Nickolas Arustamyan, Matthew Wheeler, and Peter Bubenik. Mixup Barcodes: Quantifying Geometric-Topological Interactions Between Point Clouds. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 94:1-94:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wagner_et_al:LIPIcs.SoCG.2026.94,
  author =	{Wagner, Hubert and Arustamyan, Nickolas and Wheeler, Matthew and Bubenik, Peter},
  title =	{{Mixup Barcodes: Quantifying Geometric-Topological Interactions Between Point Clouds}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{94:1--94:19},
  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.94},
  URN =		{urn:nbn:de:0030-drops-259009},
  doi =		{10.4230/LIPIcs.SoCG.2026.94},
  annote =	{Keywords: mixup barcode, persistent homology, persistence barcode, persistence diagram, image persistent homology, image persistence, deep learning, multilayer perceptron, topology of neural network embeddings, disentanglement}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.10
Fast Free Resolutions of Bifiltered Chain Complexes

Authors: Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls

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

Abstract
In a k-critical bifiltration, every simplex enters along a staircase with at most k steps. Examples with k > 1 include degree-Rips bifiltrations and models of the multicover bifiltration. We consider the problem of converting a k-critical bifiltration into a 1-critical (i.e. free) chain complex with equivalent homology. This is known as computing a free resolution of the underlying chain complex and is a first step toward post-processing such bifiltrations. We present two algorithms. The first one computes free resolutions corresponding to path graphs and assembles them to a chain complex by computing additional maps. The simple combinatorial structure of path graphs leads to good performance in practice, as demonstrated by extensive experiments. However, its worst-case bound is quadratic in the input size because long paths might yield dense boundary matrices in the output. Our second algorithm replaces the simplex-wise path graphs with ones that maintain short paths which leads to almost linear runtime and output size. We demonstrate that pre-computing a free resolution speeds up the task of computing a minimal presentation of the homology of a k-critical bifiltration in a fixed dimension. Furthermore, our findings show that a chain complex that is minimal in terms of generators can be asymptotically larger than the non-minimal output complex of our second algorithm in terms of description size.
Cite as

Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls. Fast Free Resolutions of Bifiltered Chain Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2026.10,
  author =	{Bauer, Ulrich and Dey, Tamal K. and Kerber, Michael and Russold, Florian and S\"{o}ls, Matthias},
  title =	{{Fast Free Resolutions of Bifiltered Chain Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{10:1--10:21},
  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.10},
  URN =		{urn:nbn:de:0030-drops-258161},
  doi =		{10.4230/LIPIcs.SoCG.2026.10},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Multi-Critical Bifiltrations}
}
Document
DOI: 10.4230/OASIcs.FMBC.2026.8
Detecting Cross-Function Reentrancy from EVM Traces

Authors: Semia Guesmi, Carla Piazza, Andrea Gasparetto, Matteo Rizzo, and Sabina Rossi

Published in: OASIcs, Volume 142, 7th International Workshop on Formal Methods for Blockchains (FMBC 2026)

Abstract
Reentrancy remains one of the most critical vulnerabilities affecting Ethereum smart contracts. While many existing analysis tools focus on detecting classical single-function reentrancy, more complex forms such as cross-function reentrancy are harder to identify because they depend on execution semantics and interactions between multiple functions. In this work, we study reentrancy at the level of Ethereum Virtual Machine (EVM) execution traces. We extend the TxSpector framework with new Datalog-based detection rules designed to capture cross-function reentrancy patterns. To support this analysis, we also modernize the trace extraction component by adapting it to recent versions of the Ethereum client and updated EVM instructions. The proposed approach is evaluated on real Ethereum on-chain transaction traces. The results show that our method is able to detect cross-function reentrancy behaviors that are not captured by the original TxSpector rules, demonstrating the effectiveness of pattern-based logic detection at the EVM execution level.
Cite as

Semia Guesmi, Carla Piazza, Andrea Gasparetto, Matteo Rizzo, and Sabina Rossi. Detecting Cross-Function Reentrancy from EVM Traces. In 7th International Workshop on Formal Methods for Blockchains (FMBC 2026). Open Access Series in Informatics (OASIcs), Volume 142, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{guesmi_et_al:OASIcs.FMBC.2026.8,
  author =	{Guesmi, Semia and Piazza, Carla and Gasparetto, Andrea and Rizzo, Matteo and Rossi, Sabina},
  title =	{{Detecting Cross-Function Reentrancy from EVM Traces}},
  booktitle =	{7th International Workshop on Formal Methods for Blockchains (FMBC 2026)},
  pages =	{8:1--8:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-424-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{142},
  editor =	{Bartoletti, Massimo and Marmsoler, Diego},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FMBC.2026.8},
  URN =		{urn:nbn:de:0030-drops-257058},
  doi =		{10.4230/OASIcs.FMBC.2026.8},
  annote =	{Keywords: Blockchain, smart contract, Reentrancy detection, EVM, design Patterns, logic rules}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.9
Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video

Authors: Pantea Karimi, Sadjad Fouladi, Vibhaalakshmi Sivaraman, and Mohammad Alizadeh

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

Abstract
Real-time video streaming relies on rate control to match video bitrate to network capacity while keeping latency low. Existing deployed video rate controllers react slowly to network changes, causing under-utilization and latency spikes. In contrast, modern delay-sensitive congestion control algorithms (CCAs) adapt on round-trip-time timescales, maintaining a tight feedback loop that achieves both high utilization and low latency. We introduce Vidaptive, a lightweight framework that enables real-time video to leverage responsive CCAs without codec changes. Vidaptive decouples encoding from transmission: it paces video frames at the CCA’s rate and injects dummy packets when the encoder output is insufficient, preserving a continuous feedback loop. An online algorithm dynamically adjusts the encoder’s target bitrate to align with CCA capacity while bounding frame latency. Implemented in Google WebRTC, Vidaptive improves both video quality and tail latency on diverse cellular traces. Compared to GCC, it delivers 1.5× higher bitrate, +40% VMAF, +1.4 dB SSIM, +1.3 dB PSNR, and reduces 95th-percentile frame latency by 57% (2.2 seconds). Against Salsify, it achieves lower tail latency without invasive codec modifications. These results show that coupling existing CCAs with a thin adaptation layer can outperform specialized video rate controllers while remaining deployable in practice.
Cite as

Pantea Karimi, Sadjad Fouladi, Vibhaalakshmi Sivaraman, and Mohammad Alizadeh. Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 9:1-9:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karimi_et_al:OASIcs.NINeS.2026.9,
  author =	{Karimi, Pantea and Fouladi, Sadjad and Sivaraman, Vibhaalakshmi and Alizadeh, Mohammad},
  title =	{{Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-255942},
  doi =		{10.4230/OASIcs.NINeS.2026.9},
  annote =	{Keywords: real-time video, congestion control, transport protocols, video rate control, low-latency video communication, tight feedback loop}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.12
No Signal to Rule Them All: A Systematic Analysis of In-Network Congestion Signals

Authors: Sarah McClure, Nandita Dukkipati, Sylvia Ratnasamy, and Scott Shenker

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

Abstract
In this paper, we address the following question: what in-network signals should a network provide to congestion control algorithms? To answer this guiding question, we use prior work to automatically generate congestion control algorithms optimized for a given performance objective and set of in-network congestion signals. We then make observations about the relative value of these congestion signals across a range of performance objectives. Our analysis yields a surprising central finding: for the average case, sophisticated In-Network Telemetry (INT) offers minimal performance benefits over traditional end-to-end (E2E) signals, with performance typically within 3%. We also find no single "best" INT signal, but rather a clear trade-off that manifests in many scenarios: link-based signals often excel at controlling delay, while queue-based signals are better for maximizing throughput. To make these findings concrete, we validate them by examining the extent to which in-network signals improve the performance of the BBR congestion control algorithm.
Cite as

Sarah McClure, Nandita Dukkipati, Sylvia Ratnasamy, and Scott Shenker. No Signal to Rule Them All: A Systematic Analysis of In-Network Congestion Signals. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 12:1-12:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mcclure_et_al:OASIcs.NINeS.2026.12,
  author =	{McClure, Sarah and Dukkipati, Nandita and Ratnasamy, Sylvia and Shenker, Scott},
  title =	{{No Signal to Rule Them All: A Systematic Analysis of In-Network Congestion Signals}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{12:1--12:30},
  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.12},
  URN =		{urn:nbn:de:0030-drops-255974},
  doi =		{10.4230/OASIcs.NINeS.2026.12},
  annote =	{Keywords: Congestion control, in-network telemetry}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.15
BISCAY: Practical Radio KPI Driven Congestion Control for Mobile Networks

Authors: Jon Larrea, Tanya Shreedhar, Atte Niemi, Adel Sefiane, and Mahesh K. Marina

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

Abstract
Mobile application performance is often bottlenecked by cellular links with rapid bandwidth fluctuations. We show that radio KPIs from the device chipset can precisely and promptly measure available cellular bandwidth. Building on this, we propose Biscay, a practical KPI-driven congestion control for mobile networks. Biscay leverages OpenDiag, an in-kernel, real-time KPI extractor we introduce along with a KPI-based bandwidth estimator to adjust the congestion window, utilizing available bandwidth while minimizing delay. We implement Biscay and OpenDiag on unrooted Android 5G phones. Across trace-driven emulations and real-world 4G/5G experiments, Biscay outperforms state-of-the-art CCAs (e.g., BBR, CUBIC), typically reducing average and tail delay by >90% while matching or improving throughput. These gains stem from OpenDiag’s 100× finer on-device KPI granularity than existing alternatives like MobileInsight.
Cite as

Jon Larrea, Tanya Shreedhar, Atte Niemi, Adel Sefiane, and Mahesh K. Marina. BISCAY: Practical Radio KPI Driven Congestion Control for Mobile Networks. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 15:1-15:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{larrea_et_al:OASIcs.NINeS.2026.15,
  author =	{Larrea, Jon and Shreedhar, Tanya and Niemi, Atte and Sefiane, Adel and Marina, Mahesh K.},
  title =	{{BISCAY: Practical Radio KPI Driven Congestion Control for Mobile Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-256002},
  doi =		{10.4230/OASIcs.NINeS.2026.15},
  annote =	{Keywords: Cellular Networks, Congestion Control, LTE/5G}
}
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}
}
  • Refine by Type
  • 84 Document/PDF
  • 75 Document/HTML

  • Refine by Publication Year
  • 23 2026
  • 46 2025
  • 2 2024
  • 5 2023
  • 4 2022
  • Show More...

  • Refine by Author
  • 4 Chen, Chao
  • 2 Biswas, Gautam
  • 2 Biswas, Russa
  • 2 Chen, Jiaoyan
  • 2 Coursey, Austin
  • Show More...

  • Refine by Series/Journal
  • 53 LIPIcs
  • 20 OASIcs
  • 2 LITES
  • 9 TGDK

  • Refine by Classification
  • 5 Computing methodologies → Knowledge representation and reasoning
  • 4 Mathematics of computing → Algebraic topology
  • 4 Networks → Transport protocols
  • 4 Theory of computation → Computational geometry
  • 3 Computer systems organization → Real-time systems
  • Show More...

  • Refine by Keyword
  • 4 Knowledge Graphs
  • 4 persistent homology
  • 3 Knowledge graphs
  • 3 Large Language Models
  • 2 Approximation Algorithms
  • 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