176 Search Results for "Spain, Michael"

Document
DOI: 10.4230/LIPIcs.LICS.2026.15
Complete Relational Logic for Infinite-Dimensional Quantum Programs with Unbounded Assertions

Authors: Gilles Barthe, Minbo Gao, Jam Kabeer Ali Khan, Matthijs Muis, Ivan Renison, Keiya Sakabe, Michael Walter, Yingte Xu, Tianshi Yu, and Li Zhou

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
We present sound and complete relational program logics for infinite-dimensional quantum and classical-quantum programs. The logics model assertions as self-adjoint unbounded linear relations, which simultaneously support quantitative and qualitative reasoning. Our main theoretical results include new convergence theorems and infinite-dimensional duality theorems for infinite-dimensional quantum states, which we use to establish completeness.
Cite as

Gilles Barthe, Minbo Gao, Jam Kabeer Ali Khan, Matthijs Muis, Ivan Renison, Keiya Sakabe, Michael Walter, Yingte Xu, Tianshi Yu, and Li Zhou. Complete Relational Logic for Infinite-Dimensional Quantum Programs with Unbounded Assertions. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 15:1-15:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{barthe_et_al:LIPIcs.LICS.2026.15,
  author =	{Barthe, Gilles and Gao, Minbo and Khan, Jam Kabeer Ali and Muis, Matthijs and Renison, Ivan and Sakabe, Keiya and Walter, Michael and Xu, Yingte and Yu, Tianshi and Zhou, Li},
  title =	{{Complete Relational Logic for Infinite-Dimensional Quantum Programs with Unbounded Assertions}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{15:1--15:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.15},
  URN =		{urn:nbn:de:0030-drops-268020},
  doi =		{10.4230/LIPIcs.LICS.2026.15},
  annote =	{Keywords: relational program logics, infinite-dimensional quantum programs, classical-quantum programs, linear relations, quantum optimal transport}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.63
Learning Multinomial Logits in O(n log n) Time

Authors: Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Erasmo Tani, and Andrew Tomkins

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
A Multinomial Logit (MNL) model is composed of a finite universe of items [n] = {1,…,n}, each assigned a positive weight. A query specifies an admissible subset - called a slate - and the model chooses one item from that slate with probability proportional to its weight. This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature. Although MNLs have been studied extensively, a basic computational question remains open: given query access to slates, how efficiently can we learn weights so that, for every slate, the induced choice distribution is within total variation distance ε of the ground truth? This question is central to MNL learning and has direct implications for modern recommender system interfaces. We provide two algorithms for this task, one with adaptive queries and one with non‑adaptive queries. Each algorithm outputs an MNL M̂ that induces, for each slate S, a distribution M̂_S on S that is within ε total variation distance of the true distribution. Our adaptive algorithm makes O(n/ε³ log n) queries, while our non-adaptive algorithm makes O(n²/ε³ log n log(n/ε)) queries. Both algorithms query only slates of size two and run in time proportional to their query complexity. We complement these upper bounds with lower bounds of Ω(n/ε² log n) for adaptive queries and Ω(n²/ε² log n) for non‑adaptive queries, thus proving that our adaptive algorithm is optimal in its dependence on the support size n, while the non-adaptive one is tight within a log n factor.
Cite as

Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Erasmo Tani, and Andrew Tomkins. Learning Multinomial Logits in O(n log n) Time. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chierichetti_et_al:LIPIcs.ICALP.2026.63,
  author =	{Chierichetti, Flavio and Giacchini, Mirko and Kumar, Ravi and Lattanzi, Silvio and Panconesi, Alessandro and Tani, Erasmo and Tomkins, Andrew},
  title =	{{Learning Multinomial Logits in O(n log n) Time}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.63},
  URN =		{urn:nbn:de:0030-drops-264526},
  doi =		{10.4230/LIPIcs.ICALP.2026.63},
  annote =	{Keywords: Multinomial Logits, Conditional Samples, Discrete Choice Models, Recommender Systems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.134
Sampling Colorings with Fixed Color Class Sizes

Authors: Aiya Kuchukova, Will Perkins, and Xavier Povill

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
In 1970, Hajnal and Szemerédi proved a conjecture of Erdős stating that any graph with maximum degree Δ admits an equitable (Δ+1)-coloring, that is, a coloring where color class sizes differ by at most 1. In 2007 Kierstead and Kostochka reproved their result and provided a polynomial-time algorithm which produces such a coloring. In this paper we study the problem of approximately sampling uniformly random equitable colorings. A series of works gives polynomial-time sampling algorithms for colorings without the color class constraint, the latest improvement being by Carlson and Vigoda for q ≥ 1.809 Δ. In this paper we give a polynomial-time sampling algorithm for equitable colorings when q > 2Δ. Moreover, our results extend to colorings with small deviations from equitable (and as a corollary, establishing their existence). The proof uses the framework of the geometry of polynomials for multivariate polynomials, and as a consequence establishes a multivariate local Central Limit Theorem for color class sizes of uniform random colorings.
Cite as

Aiya Kuchukova, Will Perkins, and Xavier Povill. Sampling Colorings with Fixed Color Class Sizes. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 134:1-134:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kuchukova_et_al:LIPIcs.ICALP.2026.134,
  author =	{Kuchukova, Aiya and Perkins, Will and Povill, Xavier},
  title =	{{Sampling Colorings with Fixed Color Class Sizes}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{134:1--134:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.134},
  URN =		{urn:nbn:de:0030-drops-265231},
  doi =		{10.4230/LIPIcs.ICALP.2026.134},
  annote =	{Keywords: sampling, approximate counting, graph coloring, zero-freeness, Potts model, LCLT}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.5
BuffCut: Prioritized Buffered Streaming Graph Partitioning

Authors: Linus Baumgärtner, Adil Chhabra, Marcelo Fonseca Faraj, and Christian Schulz

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

Abstract
Streaming graph partitioners enable resource-efficient and massively scalable partitioning, but one-pass assignment heuristics are highly sensitive to stream order and often yield substantially higher edge cuts than in-memory methods. We present BuffCut, a buffered streaming partitioner that narrows this quality gap, particularly when stream ordering is adversarial, by combining prioritized buffering with batch-wise multilevel assignment. BuffCut maintains a bounded priority buffer to delay poorly informed decisions and regulate the order in which nodes are considered for assignment. It incrementally constructs high-locality batches of configurable size by iteratively inserting the highest-priority nodes from the buffer into the batch, effectively recovering locality structure from the stream. Each batch is then assigned via a multilevel partitioning algorithm. Experiments on diverse real-world and synthetic graphs show that BuffCut consistently outperforms state-of-the-art buffered streaming methods. Compared to the strongest prioritized buffering baseline, BuffCut achieves 20.8% fewer edge cuts while running 2.9× faster and using 11.3× less memory. Against the next-best batched method, it reduces edge cut by 15.8% with only modest overheads of 1.8× runtime and 1.09× memory.
Cite as

Linus Baumgärtner, Adil Chhabra, Marcelo Fonseca Faraj, and Christian Schulz. BuffCut: Prioritized Buffered Streaming Graph Partitioning. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baumgartner_et_al:LIPIcs.SEA.2026.5,
  author =	{Baumg\"{a}rtner, Linus and Chhabra, Adil and Faraj, Marcelo Fonseca and Schulz, Christian},
  title =	{{BuffCut: Prioritized Buffered Streaming Graph Partitioning}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{5:1--5:20},
  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.5},
  URN =		{urn:nbn:de:0030-drops-260097},
  doi =		{10.4230/LIPIcs.SEA.2026.5},
  annote =	{Keywords: graph partitioning, streaming, online, buffered, prioritized partitioning}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.10
Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries

Authors: Gabriel Carmona and Filippo Lari

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

Abstract
Tree compression is a well-studied area that aims at reducing the size of tree representations by exploiting different forms of repetition. While the underlying theory is well understood, there is still significant room for experimental investigation, particularly in the design of compressed representations that efficiently support navigational queries. In this work, we address the problem of designing, engineering, and experimentally evaluating a compression technique for unlabeled binary trees based on repeated subtrees, yielding the minimal Directed Acyclic Graph (DAG) of the input tree. We show how this representation can be computed in linear time and space directly from a succinct encoding of the tree, and how it can be augmented with compact auxiliary data structures to support Lowest Common Ancestor (LCA) queries. When the input tree is the Cartesian tree of an array, LCA queries can be used to answer Range Minimum Queries (RMQs) on the underlying array. This is particularly relevant in the encoding model, where the array is not accessible at query time, and a space lower bound of 2n-O(log n) bits is known. Given the numerous applications of RMQs, we use this problem as a case study for our experimental evaluation, testing our implementation on 11 real-world datasets. Our experiments show that, on almost every dataset, our implementation is the most space-efficient, using as few as 0.11n bits, while still delivering practical query times.
Cite as

Gabriel Carmona and Filippo Lari. Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{carmona_et_al:LIPIcs.SEA.2026.10,
  author =	{Carmona, Gabriel and Lari, Filippo},
  title =	{{Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{10:1--10:20},
  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.10},
  URN =		{urn:nbn:de:0030-drops-260140},
  doi =		{10.4230/LIPIcs.SEA.2026.10},
  annote =	{Keywords: tree compression, range minimum query, compact data structures, algorithm engineering, experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.14
K-Hole Separation in PEO‑Based ILP Treewidth Formulation

Authors: Andrea D'Ascenzo

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

Abstract
In this paper, we introduce a family of valid inequalities for the strongest currently known integer programming formulation of treewidth based on perfect elimination orderings. These inequalities arise from the structure of induced chordless cycles (holes) and strengthen the canonical linear relaxation by enforcing constraints that every feasible chordal completion must satisfy. To handle the exponentially many such inequalities, we develop a dedicated separation routine capable of detecting violated k-hole constraints within a cutting-plane framework. Our computational results show that incorporating these inequalities substantially improves the quality of the lower bounds across a broad range of graph classes, in some cases nearly closing the integrality gap.
Cite as

Andrea D'Ascenzo. K-Hole Separation in PEO‑Based ILP Treewidth Formulation. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dascenzo:LIPIcs.SEA.2026.14,
  author =	{D'Ascenzo, Andrea},
  title =	{{K-Hole Separation in PEO‑Based ILP Treewidth Formulation}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{14:1--14:14},
  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.14},
  URN =		{urn:nbn:de:0030-drops-260186},
  doi =		{10.4230/LIPIcs.SEA.2026.14},
  annote =	{Keywords: Treewidth, Integer Linear Programming, Polyhedral Combinatorics, Chordal Completion, Induced Cycles}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.23
Exploiting Multi-Core Parallelism in Blockchain Validation and Construction

Authors: Arivarasan Karmegam, Lucianna Kiffer, and Antonio Fernández Anta

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

Abstract
Blockchain validators can reduce block processing time by exploiting multi-core CPUs, but deterministic execution must preserve a given total order while respecting transaction conflicts and per-block runtime limits. This paper systematically examines how validators can exploit multi-core parallelism during both block construction and execution without violating blockchain semantics. We formalize two validator-side optimization problems: (i) executing an already ordered block on p cores to minimize makespan while ensuring equivalence to sequential execution; and (ii) selecting and scheduling a subset of mempool transactions under a runtime limit B to maximize validator reward. For both, we develop exact Mixed-Integer Linear Programming (MILP) formulations that capture conflict, order, and capacity constraints, and propose fast deterministic heuristics that scale to realistic workloads. Using Ethereum mainnet traces and including a Solana-inspired declared-access baseline (Sol) for ordered-block scheduling and a simple reward-greedy baseline (RG) for block construction, we empirically quantify the trade-offs between optimality and runtime. MILPs quickly become intractable as heterogeneity or core count increases, whereas our heuristics run in milliseconds and achieve near-optimal quality. For ordered-block execution, heuristic makespans are typically within a few percent of the MILP solutions (and can even surpass the MILP incumbent when the solver times out), yielding up to 1.5 speedup with p = 2 and 2.3 speedup with p = 8 over sequential execution, despite tight ordering constraints. For block construction, the heuristic achieves 99-100% of the MILP optimum reward on homogeneous workloads, and 74-100% of an LP-relaxation upper bound on heterogeneous workloads, where exact optimization often times out. The resulting block-construction throughput scales close to linearly with p, reaching up to 7.9 speedup with p = 8 in our experiments. These results demonstrate that lightweight, conflict-aware scheduling and selection can unlock substantial parallelism in blockchain validation, bridging the gap between sequential execution and the true potential of multi-core hardware.
Cite as

Arivarasan Karmegam, Lucianna Kiffer, and Antonio Fernández Anta. Exploiting Multi-Core Parallelism in Blockchain Validation and Construction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karmegam_et_al:LIPIcs.SEA.2026.23,
  author =	{Karmegam, Arivarasan and Kiffer, Lucianna and Fern\'{a}ndez Anta, Antonio},
  title =	{{Exploiting Multi-Core Parallelism in Blockchain Validation and Construction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{23:1--23:21},
  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.23},
  URN =		{urn:nbn:de:0030-drops-260271},
  doi =		{10.4230/LIPIcs.SEA.2026.23},
  annote =	{Keywords: Block construction, Block execution, Deterministic parallelism, Conflict-aware scheduling}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.27
Exploring the Gap Between LCS and LCStr

Authors: Shay Golan, Matan Kraus, Ely Porat, and B. Riva Shalom

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
The Longest Common Subsequence (LCS) problem and the Longest Common Substring (LCStr) problem are classical string problems with broad theoretical and practical significance. The former has a quadratic conditional lower bound [FOCS, 2015], while the latter admits a linear-time solution. In this paper, we study a natural variation of these problems, the Longest Common Subsequence-Substring (LCSS) problem. The LCSS problem seeks the longest string that is simultaneously a subsequence of one input string and a substring of the other. This variant bridges LCS and LCStr, raising intriguing algorithmic questions: Does the complexity of computing LCSS interpolate between the linear time of LCStr and the quadratic time of LCS? What about approximability? We also examine a natural extension of LCSS to multiple strings, parameterizing the balance between subsequence and substring requirements. Our results reveal several insights. First, under the SETH conjecture, the inherent complexity of LCSS is quadratic, similar to LCS. In contrast, we provide a linear-time approximation for LCSS. Finally, for the multi-string variant, unlike both problems, we design a quadratic-time algorithm, uncovering deeper structural properties of the problem. By studying the complexity of the LCSS problem, we aim to gain some understanding of what influences whether a variant of the LCS problem behaves more like the standard LCS or like LCStr. Our findings suggest that hybrid constraints can create computational "sweet spots," where problems become more tractable than their pure counterparts. This opens a broader research direction in constraint-mediated algorithm design. Beyond LCSS itself, our work highlights unexpected connections between subsequence and substring constraints, advancing the theoretical understanding of string problems and laying the foundation for new algorithmic techniques and complexity-theoretic insights in the rich space between classical string comparison paradigms.
Cite as

Shay Golan, Matan Kraus, Ely Porat, and B. Riva Shalom. Exploring the Gap Between LCS and LCStr. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{golan_et_al:LIPIcs.CPM.2026.27,
  author =	{Golan, Shay and Kraus, Matan and Porat, Ely and Shalom, B. Riva},
  title =	{{Exploring the Gap Between LCS and LCStr}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.27},
  URN =		{urn:nbn:de:0030-drops-259535},
  doi =		{10.4230/LIPIcs.CPM.2026.27},
  annote =	{Keywords: Longest Common Subsequence, Longest Common Substring, Conditional Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.31
Improved and Parameterized Algorithms for Online Multi-Level Aggregation

Authors: Young-San Lin and Alex Turoczy

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

Abstract
We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski, Böhm, Byrka, Chrobak, Dürr, Folwarczný, Jeż, Sgall, Thang, and Veselý (ESA 2016, OR 2020). In this problem, requests arrive over time at the vertices of a given vertex-weighted tree, and each request has a deadline that it must be served by. The cost of serving a request equals the cost of a path from the root to the vertex where the request resides. Instead of serving each request individually, requests can be aggregated and served by transmitting a subtree from the root that spans the vertices on which the requests reside, to potentially be more cost-effective. The aggregated cost is the weight of the transmission subtree. The goal of MLAP-D is to find an aggregation solution that minimizes the total cost while serving all requests. MLAP-D generalizes some well-studied problems including the TCP acknowledgment problem and the joint replenishment problem, and arises in natural scenarios such as multi-casting, sensor networks, and supply chain management. We present improved and parameterized algorithms for MLAP-D. Our result is twofold. First, we present an e(D+1)-competitive algorithm where D is the depth of the tree. Second, we present an e(4H+2)-competitive algorithm where H is the caterpillar dimension of the tree. Here, H ≤ D and H ≤ log₂ |V| where |V| is the number of vertices in the given tree. The caterpillar dimension remains constant for rich but simple classes of trees, such as line graphs (H = 1), caterpillar graphs (H = 2), and lobster graphs (H = 3). To the best of our knowledge, this is the first online algorithm parameterized on a measure better than depth. The state-of-the-art online algorithms are 6(D+1)-competitive by Buchbinder, Feldman, Naor, and Talmon (SODA 2017) and O(log |V|)-competitive by Azar and Touitou (FOCS 2020). Our framework outperforms the state-of-the-art ratios when H = o(min{D,log₂ |V|}). Our memory-based algorithms extend transmission subtrees with a cost comparable to transmission subtrees used to serve previous requests. Our simple framework directly applies to trees with any structure and differs from the previous frameworks that reduce the problem to trees with specific structures.
Cite as

Young-San Lin and Alex Turoczy. Improved and Parameterized Algorithms for Online Multi-Level Aggregation. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.SWAT.2026.31,
  author =	{Lin, Young-San and Turoczy, Alex},
  title =	{{Improved and Parameterized Algorithms for Online Multi-Level Aggregation}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{31:1--31:17},
  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.31},
  URN =		{urn:nbn:de:0030-drops-260673},
  doi =		{10.4230/LIPIcs.SWAT.2026.31},
  annote =	{Keywords: Online Algorithms, Approximation Algorithms, Graph Problems}
}
Document
DOI: 10.4230/OASIcs.AEiC.2026.5
A Rust Framework for Real-Time Parallel Programming

Authors: Hugo Silva, Tiago Carvalho, and Luis Miguel Pinho

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

Abstract
Real-time systems increasingly rely on parallel execution to meet performance and timing requirements. While several programming languages provide mechanisms for combining real-time and parallel programming, Rust currently lacks dedicated frameworks that address both aspects in an integrated way. In previous work, we proposed a high-level design of a framework for real-time parallel programming in Rust. In this paper, we describe the design of a prototype implementation of this framework as a Rust library. The prototype provides abstractions for creating and managing real-time threads with priorities, as well as thread pools that enable structured parallel execution while respecting priority-based scheduling. We describe the architecture of the prototype, its implementation and illustrate its use through examples. This implementation demonstrates the feasibility of supporting real-time parallel programming patterns in Rust and serves as a foundation for future extensions of the framework.
Cite as

Hugo Silva, Tiago Carvalho, and Luis Miguel Pinho. A Rust Framework for Real-Time Parallel Programming. In 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026). Open Access Series in Informatics (OASIcs), Volume 143, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{silva_et_al:OASIcs.AEiC.2026.5,
  author =	{Silva, Hugo and Carvalho, Tiago and Pinho, Luis Miguel},
  title =	{{A Rust Framework for Real-Time Parallel Programming}},
  booktitle =	{30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)},
  pages =	{5:1--5:17},
  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.5},
  URN =		{urn:nbn:de:0030-drops-259231},
  doi =		{10.4230/OASIcs.AEiC.2026.5},
  annote =	{Keywords: Real-time systems, Parallel programming, Rust}
}
Document
DOI: 10.4230/OASIcs.AEiC.2026.7
A Flexible Ada Framework for Jitter-Sensitive Mixed-Criticality Real-Time Systems

Authors: Sergio Sáez Barona and Jorge Real Sáez

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

Abstract
Real-time systems often require combining time-triggered (TT) and event-triggered (ET) execution models to balance predictability and flexibility. Previous work proposed a unified framework supporting both paradigms, enabling the integration of jitter-sensitive activities within a static TT schedule while preserving the responsiveness of ET execution. However, that framework did not address the requirements of mixed-criticality systems (MCS), where tasks may exhibit different execution-time assumptions depending on the system criticality level. This paper extends the original framework, designed for Ada under the Ravenscar profile, to support mixed-criticality workloads. First, the task model is enhanced to incorporate multiple execution-time estimates per job, allowing tasks to adapt their behaviour across criticality levels, including the possibility of selectively disabling jobs. Second, the TT scheduling model is extended to support criticality-aware execution, introducing adaptive slot durations, application-level overrun handling, and mechanisms to control the system criticality level at run time. Third, the framework preserves the semantic consistency of multi-frame tasks under criticality-level changes by defining a clear separation between system-wide and task-local criticality. Additionally, the mode-change mechanism is extended to support timed mode changes, enabling precise control over plan transitions and facilitating synchronisation across distributed schedules. The proposed approach maintains the predictability of TT execution while providing the flexibility required to support mixed-criticality behaviour. An execution example illustrates the applicability of the framework and the interaction between its main components.
Cite as

Sergio Sáez Barona and Jorge Real Sáez. A Flexible Ada Framework for Jitter-Sensitive Mixed-Criticality Real-Time Systems. In 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026). Open Access Series in Informatics (OASIcs), Volume 143, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{saezbarona_et_al:OASIcs.AEiC.2026.7,
  author =	{S\'{a}ez Barona, Sergio and Real S\'{a}ez, Jorge},
  title =	{{A Flexible Ada Framework for Jitter-Sensitive Mixed-Criticality Real-Time Systems}},
  booktitle =	{30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)},
  pages =	{7:1--7:21},
  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.7},
  URN =		{urn:nbn:de:0030-drops-259253},
  doi =		{10.4230/OASIcs.AEiC.2026.7},
  annote =	{Keywords: Real-time systems, Time-triggered scheduling, Mixed-criticality systems, Ravenscar tasking profile, High-integrity systems, Embedded systems}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.15
Incentivizing High-Quality Content in Online Recommender Systems

Authors: Xinyan Hu, Meena Jagadeesan, Michael I. Jordan, and Jacob Steinhardt

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

Abstract
In content recommender systems such as TikTok and YouTube, the platform’s recommendation algorithm shapes content producer incentives. Many platforms employ online learning, which generates intertemporal incentives, since content produced today affects recommendations of future content. We study the game between producers and analyze the content created at equilibrium. We prove that standard online learning algorithms, such as Hedge and EXP3, unfortunately incentivize producers to create low-quality content, where producers' effort approaches zero in the long run for typical learning rate schedules. Motivated by this negative result, we design learning algorithms that incentivize producers to invest high effort and achieve high user welfare. At a conceptual level, our work illustrates the unintended impact that a platform’s learning algorithm can have on content quality and introduces algorithmic approaches to mitigating these effects.
Cite as

Xinyan Hu, Meena Jagadeesan, Michael I. Jordan, and Jacob Steinhardt. Incentivizing High-Quality Content in Online Recommender Systems. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.FORC.2026.15,
  author =	{Hu, Xinyan and Jagadeesan, Meena and Jordan, Michael I. and Steinhardt, Jacob},
  title =	{{Incentivizing High-Quality Content in Online Recommender Systems}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{15:1--15:18},
  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.15},
  URN =		{urn:nbn:de:0030-drops-259887},
  doi =		{10.4230/LIPIcs.FORC.2026.15},
  annote =	{Keywords: recommender systems, content quality, producer incentives, online learning, algorithmic game theory, Stackelberg games}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.18
A Differentially Private Approximation of the Width Problem

Authors: Mor Hale and Or Sheffet

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

Abstract
The width of a point set - the minimum distance between two parallel hyperplanes enclosing the data - is a fundamental geometric measure that captures how "flat" or "fat" a dataset is. As such, it serves as a basic shape descriptor used in visualization, convex hull approximation, and geometric data analysis. Despite its importance, width is highly sensitive to single-point changes, and no differentially private algorithm for approximating it was previously known. We present the first pure ε-differentially private algorithm that approximates the width of a dataset. Our algorithm is a private adaptation of Chan’s approximation scheme [Chan, 2000] and operates by privately approximating the solution to a collection of suitably formulated linear programs. In addition to estimating the width, our method privately identifies a corresponding direction, enabling a private "fattening" transformation of the dataset - a basic structural preprocessing step for many geometric algorithms. This work advances the understanding of how geometric shape descriptors can admit good approximations even under the constraints of differential privacy.
Cite as

Mor Hale and Or Sheffet. A Differentially Private Approximation of the Width Problem. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hale_et_al:LIPIcs.FORC.2026.18,
  author =	{Hale, Mor and Sheffet, Or},
  title =	{{A Differentially Private Approximation of the Width Problem}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{18:1--18:18},
  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.18},
  URN =		{urn:nbn:de:0030-drops-259914},
  doi =		{10.4230/LIPIcs.FORC.2026.18},
  annote =	{Keywords: Differential privacy, computational geometry, width approximation, private algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.25
The Typical Algebraic Shifting of Graphs and Surfaces

Authors: Denys Bulavka, Eran Nevo, and Yuval Peled

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

Abstract
We initiate a statistical study of Kalai’s exterior algebraic shifting, focusing on concentration phenomena for random triangulations of a fixed space. First, for a uniform n-vertex refinement of any given graph G, we show that asymptotically almost-surely (a.a.s.) its exterior algebraic shifting is an explicit shifted graph depending only on n and the Betti numbers of G. Next, for any given compact connected Riemannian surface S, sample n points independently at random according to the volume measure, and consider the resulted a.a.s. unique Delaunay triangulation. We prove that a.a.s. its exterior algebraic shifting is an explicit shifted complex depending only on n and the Euler genus of S, and in particular is area-rigid. In both results the expected shifted complex is a homology lex-segment complex, a notion we define combinatorially and characterize numerically à la Björner-Kalai. As a tool to prove the result on surfaces, we prove a universality result on edge contractions: for every fixed surface triangulation K, every dense enough point set in the surface yields a Delaunay triangulation that edge contracts to K.
Cite as

Denys Bulavka, Eran Nevo, and Yuval Peled. The Typical Algebraic Shifting of Graphs and Surfaces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bulavka_et_al:LIPIcs.SoCG.2026.25,
  author =	{Bulavka, Denys and Nevo, Eran and Peled, Yuval},
  title =	{{The Typical Algebraic Shifting of Graphs and Surfaces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{25:1--25: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.25},
  URN =		{urn:nbn:de:0030-drops-258312},
  doi =		{10.4230/LIPIcs.SoCG.2026.25},
  annote =	{Keywords: Algebraic shifting, Delaunay triangulation, surfaces, random triangulation, area rigidity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.31
Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems

Authors: Chaeyoon Chung, Anil Maheshwari, and Michiel Smid

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

Abstract
Given a set S of n points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in S to its closest line. We present a (1+ε)-approximation algorithm for the two-line-center problem that runs in O((n/ε) log (1/ε)) time, which improves the previously best O(nlog n + (n/ε²) log (1/ε) + (1/ε³)log (1/ε))-time algorithm. We also consider three variants of this problem, in which the orientations of the two lines are restricted: (1) the orientation of one of the two lines is fixed, (2) the orientations of both lines are fixed, and (3) the two lines are required to be parallel. For each of these three variants, we give the first (1+ε)-approximation algorithm that runs in linear time. In particular, for the variant where the orientation of one of the two lines is fixed, we also give an improved exact algorithm that runs in O(n log n) time and show that it is optimal.
Cite as

Chaeyoon Chung, Anil Maheshwari, and Michiel Smid. Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.SoCG.2026.31,
  author =	{Chung, Chaeyoon and Maheshwari, Anil and Smid, Michiel},
  title =	{{Linear-Time (1+\epsilon)-Approximation Algorithms for Two-Line-Center Problems}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{31:1--31: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.31},
  URN =		{urn:nbn:de:0030-drops-258374},
  doi =		{10.4230/LIPIcs.SoCG.2026.31},
  annote =	{Keywords: Approximation algorithm, two-line-center problem, k-line-center problem, projective clustering, \epsilon-certificate, \epsilon-coreset, width of a point set}
}
  • Refine by Type
  • 176 Document/PDF
  • 144 Document/HTML

  • Refine by Publication Year
  • 38 2026
  • 102 2025
  • 8 2024
  • 11 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 3 Albouy, Timothé
  • 3 Altmeyer, Sebastian
  • 3 Fernández Anta, Antonio
  • 3 Harbour, Michael González
  • 3 Lattanzi, Silvio
  • Show More...

  • Refine by Series/Journal
  • 127 LIPIcs
  • 20 OASIcs
  • 1 DARTS
  • 11 LITES
  • 17 TGDK

  • Refine by Classification
  • 13 Theory of computation → Distributed algorithms
  • 10 Theory of computation → Computational geometry
  • 9 Theory of computation → Design and analysis of algorithms
  • 8 Computing methodologies → Knowledge representation and reasoning
  • 8 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 5 Real-time systems
  • 3 Knowledge Graphs
  • 3 Knowledge graphs
  • 3 Large Language Models
  • 3 computational geometry
  • 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