510 Search Results for "Wang, Chen"

Document
DOI: 10.4230/LIPIcs.ITC.2026.4
Fiat-Shamir for Bounded-Depth Adversaries

Authors: Liyan Chen, Yilei Chen, Zikuan Huang, Nuozhou Sun, Tianqi Yang, and Yiding Zhang

Published in: LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026)

Abstract
We study how to construct hash functions that can securely instantiate the Fiat-Shamir transformation against bounded-depth adversaries. The motivation is twofold. First, given the recent fruitful line of research of constructing cryptographic primitives against bounded-depth adversaries under worst-case complexity assumptions, and the rich applications of Fiat-Shamir, instantiating Fiat-Shamir hash functions against bounded-depth adversaries under worst-case complexity assumptions might lead to further applications (such as SNARG for P, showing the cryptographic hardness of PPAD, etc.) against bounded-depth adversaries. Second, we wonder whether it is possible to overcome the impossibility results of constructing Fiat-Shamir for arguments [Goldwasser, Kalai, FOCS '03] in the setting where the depth of the adversary is bounded, given that the known impossibility results (against p.p.t. adversaries) are contrived. Our main results give new insights for Fiat-Shamir against bounded-depth adversaries in both the positive and negative directions. On the positive side, for Fiat-Shamir for proofs with certain properties, we show that weak worst-case assumptions are enough for constructing explicit hash functions that give AC⁰[2]-soundness. In particular, we construct an AC⁰[2]-computable correlation-intractable hash family for constant-degree polynomials against AC⁰[2] adversaries, assuming ⊕L/poly ⊈ Sum̃_{n^{-c}}∘AC⁰[2] for some c > 0. This is incomparable to all currently-known constructions, which are typically useful for larger classes and against stronger adversaries, but based on arguably stronger assumptions. Our construction is inspired by the Fiat-Shamir hash function by Peikert and Shiehian [CRYPTO '19] and the fully-homomorphic encryption scheme against bounded-depth adversaries by Wang and Pan [EUROCRYPT '22]. On the negative side, we show Fiat-Shamir for arguments is still impossible to achieve against bounded-depth adversaries. In particular, - Assuming the existence of AC⁰[2]-computable CRHF against p.p.t. adversaries, for every poly-size hash function, there is a (p.p.t.-sound) interactive argument that is not AC⁰[2]-sound after applying Fiat-Shamir with this hash function. - Assuming the existence of AC⁰[2]-computable CRHF against AC⁰[2] adversaries, there is an AC⁰[2]-sound interactive argument such that for every hash function computable by AC⁰[2] circuits, the argument does not preserve AC⁰[2]-soundness when applying Fiat-Shamir with this hash function. This is a low-depth variant of Goldwasser and Kalai.
Cite as

Liyan Chen, Yilei Chen, Zikuan Huang, Nuozhou Sun, Tianqi Yang, and Yiding Zhang. Fiat-Shamir for Bounded-Depth Adversaries. In 7th Conference on Information-Theoretic Cryptography (ITC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 385, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITC.2026.4,
  author =	{Chen, Liyan and Chen, Yilei and Huang, Zikuan and Sun, Nuozhou and Yang, Tianqi and Zhang, Yiding},
  title =	{{Fiat-Shamir for Bounded-Depth Adversaries}},
  booktitle =	{7th Conference on Information-Theoretic Cryptography (ITC 2026)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-426-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{385},
  editor =	{Dodis, Yevgeniy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.4},
  URN =		{urn:nbn:de:0030-drops-270978},
  doi =		{10.4230/LIPIcs.ITC.2026.4},
  annote =	{Keywords: Fiat-Shamir, Correlation Intractability}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.43
Unique Decoding of Reed–Solomon and Related Codes for Semi-Adversarial Errors

Authors: Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang

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

Abstract
Motivated by recent developments in coding theory, particular in list-decoding, we introduce a new error model which we call semi-adversarial errors. This error model bridges between fully random errors and fully adversarial errors by allowing some symbols of a message to be corrupted by an adversary while others are replaced with uniformly random symbols. As our main quest, we seek to understand optimal efficient unique decoding algorithms in the semi-adversarial model. For interleaved Reed-Solomon (IRS), folded Reed-Solomon (FRS) and univariate multiplicity codes, we design decoding algorithms running in near-linear time for most mixtures of random and adversarial errors. Our analysis matches the information-theoretic optimum for semi-adversarial errors. Our algorithm for interleaved Reed-Solomon codes is an improved implementation of the decoding algorithm by Bleichenbacher-Kiayias-Yung (BKY) for fully random errors. We use a novel monomial-tracking technique to analyze its performance in this new semi-adversarial errors. Inspired by the BKY algorithm, we use novel interpolations to extend our approach to the settings of folded Reed-Solomon and multiplicity codes, resulting in fast algorithms for unique decoding against semi-adversarial errors. Our new decoders for FRS and multiplicity codes replace the sophisticated root-finding step in traditional algorithms, such as the Guruswami-Wang algorithm, with a straightforward polynomial long division. Analysis of these algorithms requires more robust monomial-tracking arguments than IRS codes.
Cite as

Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. Unique Decoding of Reed–Solomon and Related Codes for Semi-Adversarial Errors. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2026.43,
  author =	{Brakensiek, Joshua and Chen, Yeyuan and Dhar, Manik and Zhang, Zihan},
  title =	{{Unique Decoding of Reed–Solomon and Related Codes for Semi-Adversarial Errors}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{43:1--43:19},
  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.43},
  URN =		{urn:nbn:de:0030-drops-264326},
  doi =		{10.4230/LIPIcs.ICALP.2026.43},
  annote =	{Keywords: coding theory, interleaved codes, Reed-Solomon codes, semi-random models, unique decoding}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.58
Quantum Multi-Level Estimation of Functionals of Discrete Distributions

Authors: Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, and Xinzhao Wang

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

Abstract
We propose a quantum multi-level estimation framework for a functional ∑_{i=1}^n f(p_i) of a discrete distribution (p_i)_{i=1}^n. We partition the values p_i into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant p_i, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the q-Tsallis entropy of discrete distributions. Specifically, - For q > 1, we obtain a near-optimal quantum algorithm with query complexity Θ̃(1/ε^{max{1/(2(q-1)), 1}}), improving the prior best O(1/ε^{1+1/(q-1)}) due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). - For 0 < q < 1, we obtain a quantum algorithm with query complexity Õ(n^{1/q-1/2}/ε^{1/q}), exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized q-entropy for non-integer q.
Cite as

Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, and Xinzhao Wang. Quantum Multi-Level Estimation of Functionals of Discrete Distributions. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.58,
  author =	{Chen, Kean and Gao, Minbo and Li, Tongyang and Wang, Qisheng and Wang, Xinzhao},
  title =	{{Quantum Multi-Level Estimation of Functionals of Discrete Distributions}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{58:1--58:23},
  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.58},
  URN =		{urn:nbn:de:0030-drops-264473},
  doi =		{10.4230/LIPIcs.ICALP.2026.58},
  annote =	{Keywords: Quantum algorithms, functional estimation, entropy estimation, query complexity, Tsallis entropy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.59
Strict Hierarchy for Quantum Channel Certification to Unitary

Authors: Kean Chen, Qisheng Wang, and Zhicheng Zhang

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

Abstract
We consider the problem of quantum channel certification to unitary, where one is given access to an unknown d-dimensional channel ℰ, and wants to test whether ℰ is equal to a target unitary channel or is ε-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: 1) Θ(d/ε²) queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). 2) Θ(d/ε) queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). 3) Θ(√d/ε) queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.
Cite as

Kean Chen, Qisheng Wang, and Zhicheng Zhang. Strict Hierarchy for Quantum Channel Certification to Unitary. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.59,
  author =	{Chen, Kean and Wang, Qisheng and Zhang, Zhicheng},
  title =	{{Strict Hierarchy for Quantum Channel Certification to Unitary}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{59:1--59:12},
  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.59},
  URN =		{urn:nbn:de:0030-drops-264480},
  doi =		{10.4230/LIPIcs.ICALP.2026.59},
  annote =	{Keywords: Quantum algorithms, quantum channels, quantum certification, query complexity, entanglement fidelity}
}
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.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.SEA.2026.3
Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization

Authors: Dildar Ali, Ansh Jasrotia, Abishek Salaria, and Suman Banerjee

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

Abstract
How to utilize an allocated budget effectively for branding and promotion of a commercial house is an important problem, particularly when multiple advertising media are available. There exist multiple such media, and among them, two popular ones are billboards and social media advertisements. In this context, the question naturally arises: how should a budget be allocated to maximize total influence? Although there is significant literature on the effective use of budgets in individual advertising media, there are hardly any studies examining budget allocation across multiple advertising media. To bridge this gap, this paper introduces the Budget Splitting Problem in Billboard and Social Network Advertisement. We introduce the notion of interaction effect to capture the additional influence due to triggers from multiple media of advertising. Using this notion, we propose a noble influence function Φ(,) that captures the total influence and shows that this function is non-negative, monotone, and non-bisubmodular. We introduce bi-submodularity ratio (γ) and generalized curvature (α) to measure how close a function is to being bi-submodular and how far a function is from being modular, respectively. We propose the Randomized Greedy and Two-Phase Adaptive Greedy approach, where the influence function is non-bisubmodular and achieves an approximation guarantee of (1/α)(1-e^(-γα)). We conducted several experiments using real-world datasets and observed that the proposed solution approach’s budget splitting leads to a greater influence than existing approaches.
Cite as

Dildar Ali, Ansh Jasrotia, Abishek Salaria, and Suman Banerjee. Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ali_et_al:LIPIcs.SEA.2026.3,
  author =	{Ali, Dildar and Jasrotia, Ansh and Salaria, Abishek and Banerjee, Suman},
  title =	{{Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-260070},
  doi =		{10.4230/LIPIcs.SEA.2026.3},
  annote =	{Keywords: Advertisement, Billboard, Social Network, Bi-submodularity, Influence Maximization}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.4
Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance

Authors: Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti

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

Abstract
The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.
Cite as

Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti. Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arbib_et_al:LIPIcs.SEA.2026.4,
  author =	{Arbib, Claudio and D'Ascenzo, Andrea and Kara\c{s}an, Oya E. and Pizzuti, Andrea},
  title =	{{Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{4:1--4: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.4},
  URN =		{urn:nbn:de:0030-drops-260081},
  doi =		{10.4230/LIPIcs.SEA.2026.4},
  annote =	{Keywords: Levenshtein Distance, Median String Problem, Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.22
Engineering Fully Dynamic Convex Hulls

Authors: Ivor van der Hoog, Henrik Reinstädtler, and Eva Rotenberg

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

Abstract
We present a new fully dynamic algorithm for maintaining convex hulls under insertions and deletions while supporting geometric queries. Our approach combines the logarithmic method with a deletion-only convex hull data structure, achieving amortised update times of O(log n log log n) and query times of O(log² n). We provide a robust and non-trivial implementation that supports point-location queries, a challenging and non-decomposable class of convex hull queries. We evaluate our implementation against the state of the art, including a new naive baseline that rebuilds the convex hull whenever an update affects it. On hulls that include polynomially many data points (e.g. Θ(n^ε) for some ε), such as the ones that often occur in practice, our method outperforms all other techniques. Update-heavy workloads strongly favour our approach, which is in line with our theoretical guarantees. Yet, our method remains competitive all the way down to when the update to query ratio is 1 to 10. Experiments on real-world data sets furthermore reveal that existing fully dynamic techniques suffer from significant robustness issues. In contrast, our implementation remains stable across all tested inputs.
Cite as

Ivor van der Hoog, Henrik Reinstädtler, and Eva Rotenberg. Engineering Fully Dynamic Convex Hulls. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.SEA.2026.22,
  author =	{van der Hoog, Ivor and Reinst\"{a}dtler, Henrik and Rotenberg, Eva},
  title =	{{Engineering Fully Dynamic Convex Hulls}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{22:1--22: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.22},
  URN =		{urn:nbn:de:0030-drops-260264},
  doi =		{10.4230/LIPIcs.SEA.2026.22},
  annote =	{Keywords: Convex hulls, fully-dynamic data structures, robustness}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.25
Engineering Learned Heuristics to Improve Clustering for Multilevel Graph Partitioning

Authors: Simeon Schrape, Nikolai Maas, Kenneth Langedal, and Daniel Seemaier

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

Abstract
Balanced Graph Partitioning is a classical optimization problem where quality guarantees are computationally infeasible, and practical solvers therefore rely on manually engineered heuristics. Yet, the problem has also proven difficult for approaches that rely heavily on machine learning - especially since applications often need to partition graphs of huge scale in a short amount of time. Instead, we demonstrate how to achieve practical improvements with a more careful approach that uses machine learning to improve heuristic decisions within the state-of-the-art solver Mt-KaHyPar. We use a pre-trained neural network to predict a score for each edge, which then guides clustering decisions in the first phase of the partitioning (the coarsening). Combined with corresponding adjustments to the clustering algorithm and an efficient implementation of the neural network logic, we improve the overall solution quality while preserving the efficiency and scalability of the original algorithm. Our detailed evaluation on more than 180 graphs shows an average quality improvement of 2% on a class of graphs with beneficial properties, and unchanged quality on all remaining graphs. Moreover, our improvements generalize to a set of instances from the literature that are much larger than the graphs used during training.
Cite as

Simeon Schrape, Nikolai Maas, Kenneth Langedal, and Daniel Seemaier. Engineering Learned Heuristics to Improve Clustering for Multilevel Graph Partitioning. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 25:1-25:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schrape_et_al:LIPIcs.SEA.2026.25,
  author =	{Schrape, Simeon and Maas, Nikolai and Langedal, Kenneth and Seemaier, Daniel},
  title =	{{Engineering Learned Heuristics to Improve Clustering for Multilevel Graph Partitioning}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{25:1--25: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.25},
  URN =		{urn:nbn:de:0030-drops-260295},
  doi =		{10.4230/LIPIcs.SEA.2026.25},
  annote =	{Keywords: Graph Partitioning, Graph Algorithms, Machine Learning, Neural Networks}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.17
Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems

Authors: Tim Donkiewicz

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

Abstract
Scenario-based optimization problems can be solved via Benders decomposition, which separates first-stage (master problem) decisions from second-stage (subproblem) recourse actions and iteratively refines the master problem with Benders cuts. In conventional Benders decomposition, all subproblems are solved at each iteration. For problems with many scenarios, solving only a selected subset can reduce computation. We quantify the potential in selecting only those subproblems that yield cuts, and develop subproblem scoring and selection strategies. The proposed multi-criteria scoring methods combine historical subproblem performance metrics with problem-specific features, trained online via logistic regression to adapt to the changing likelihood of subproblem usefulness. Multiple stopping criteria balance exploration and exploitation: cut limits, proportional solve limits, and score thresholds. We evaluate our approach on a variant of the survivable network design problem, which serves as a testbed due to its natural decomposition into many subproblems of varying importance. Computational experiments on 135 test instances demonstrate the potential and practical performance of subproblem selection. Analysis reveals that 52.1% of all subproblems solved are unnecessary (they contribute no cuts and occur outside cut-free rounds). An oracle with perfect foresight reduces total solve times by 34.4%. Random selection performs significantly worse than full enumeration, showing that naive strategies can degrade performance. Our best-scoring and selection method achieves statistically significant improvements in both runtime and primal-dual integrals. These results provide empirical evidence that informed subproblem selection can improve Benders decomposition in this setting, while highlighting challenges in developing reliable prediction models. Whether these findings extend to other problem classes remains an open question for future work.
Cite as

Tim Donkiewicz. Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{donkiewicz:LIPIcs.SEA.2026.17,
  author =	{Donkiewicz, Tim},
  title =	{{Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{17:1--17: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.17},
  URN =		{urn:nbn:de:0030-drops-260219},
  doi =		{10.4230/LIPIcs.SEA.2026.17},
  annote =	{Keywords: Integer programming, Benders decomposition, subproblem selection, survivable network design, machine learning, operations research}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.16
Online Hitting Set for Axis-Aligned Squares

Authors: Minati De, Satyam Singh, and Csaba D. Tóth

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

Abstract
Given a set P of n points in the plane and a sequence of axis-aligned squares that arrive in an online fashion, the online hitting set problem consists of maintaining, by adding new points from P if necessary, a hitting set H ⊆ P, which contains at least one point in every input square that has already arrived. We present an O(log n)-competitive deterministic algorithm for this problem. The competitive ratio is the best possible, apart from constant factors. In fact, this is the first O(log n)-competitive algorithm for the online hitting set problem that works for geometric objects of arbitrary sizes (i.e., unbounded scaling factors) in the plane. We further generalize this result to positive homothets of a polygon with k ≥ 3 vertices in the plane and provide an O(k²log n)-competitive algorithm.
Cite as

Minati De, Satyam Singh, and Csaba D. Tóth. Online Hitting Set for Axis-Aligned Squares. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.SWAT.2026.16,
  author =	{De, Minati and Singh, Satyam and T\'{o}th, Csaba D.},
  title =	{{Online Hitting Set for Axis-Aligned Squares}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-260528},
  doi =		{10.4230/LIPIcs.SWAT.2026.16},
  annote =	{Keywords: axis-aligned squares, hitting set, homothets of a polygon, online algorithm}
}
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.20
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Authors: Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi

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

Abstract
A disk graph is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs, the complexity of this problem is still open, but for unit disk graphs, it is well known to be in P. The currently fastest algorithm runs in time O(n^{7/3+ o(1)}), where n denotes the number of disks [Jared Espenant et al., 2023; J. Mark Keil and Debajyoti Mondal, 2025]. Moreover, for the case of disk graphs with t distinct radii, the problem has also recently been shown to be in XP. More specifically, it is solvable in time O^*(n^{2t}) [J. Mark Keil and Debajyoti Mondal, 2025]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization: [(i)] 1) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(n/ε²); and 2) for disk graphs with t distinct radii, we give a parameterized approximation scheme that, with a constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(f(t)⋅ (1/ε)^{O(t)} ⋅ n), for some (exponential) function f(t).
Cite as

Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi. Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.SWAT.2026.20,
  author =	{Gao, Jie and Gawrychowski, Pawe{\l} and Giannopoulos, Panos and Mulzer, Wolfgang and Singh, Satyam and Staals, Frank and Zehavi, Meirav},
  title =	{{Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{20:1--20: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.20},
  URN =		{urn:nbn:de:0030-drops-260563},
  doi =		{10.4230/LIPIcs.SWAT.2026.20},
  annote =	{Keywords: Maximum Clique, Disk Graphs, Unit Disk Graphs, FPT Approximation}
}
  • Refine by Type
  • 510 Document/PDF
  • 443 Document/HTML

  • Refine by Publication Year
  • 111 2026
  • 324 2025
  • 21 2024
  • 12 2023
  • 11 2022
  • Show More...

  • Refine by Author
  • 5 Wang, Qisheng
  • 4 Blanca, Antonio
  • 4 Gao, Jie
  • 4 Schmid, Stefan
  • 4 Wang, Chen
  • Show More...

  • Refine by Series/Journal
  • 397 LIPIcs
  • 67 OASIcs
  • 1 DARTS
  • 14 LITES
  • 30 TGDK
  • Show More...

  • Refine by Classification
  • 53 Theory of computation → Computational geometry
  • 34 Theory of computation → Design and analysis of algorithms
  • 21 Theory of computation → Graph algorithms analysis
  • 19 Theory of computation → Problems, reductions and completeness
  • 13 Computing methodologies → Knowledge representation and reasoning
  • Show More...

  • Refine by Keyword
  • 10 Large Language Models
  • 8 Clustering
  • 7 Knowledge Graphs
  • 7 approximation algorithms
  • 6 Blockchain
  • 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