55 Search Results for "Chen, Ken"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.34
Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs

Authors: Kengo Nakamura and Masaaki Nishino

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

Abstract
Given a network and a set of vertices called seeds to initially inject information, influence spread is the expected number of vertices that eventually receive the information under a certain stochastic model of information propagation. Under the commonly used independent cascade model, influence spread is equivalent to the expected number of vertices reachable from the seeds on a directed uncertain graph, and the exact evaluation of influence spread offers many applications, e.g., influence maximization. Although its evaluation is a #P-hard task, there is an algorithm that can precisely compute the influence spread in O(mnω_p²⋅ 2^{ω_p²}) time, where ω_p is the pathwidth of the graph. We improve this by developing an algorithm that computes the influence spread in O((m+n)ω_p²⋅ 2^{ω_p²}) time. This is achieved by identifying the similarities in the repetitive computations in the existing algorithm and sharing them to reduce computation. Although similar refinements have been considered for the probability computation on undirected uncertain graphs, a greater number of similarities must be leveraged for directed graphs to achieve linear time complexity.
Cite as

Kengo Nakamura and Masaaki Nishino. Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nakamura_et_al:LIPIcs.SWAT.2026.34,
  author =	{Nakamura, Kengo and Nishino, Masaaki},
  title =	{{Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{34:1--34: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.34},
  URN =		{urn:nbn:de:0030-drops-260704},
  doi =		{10.4230/LIPIcs.SWAT.2026.34},
  annote =	{Keywords: Influence spread, bounded pathwidth, network reliability, linear time algorithm}
}
Document
DOI: 10.4230/OASIcs.AEiC.2026.4
HASCO: A Hybrid AI Simulation Compiler for Semantic Accident Reconstruction

Authors: Edin Jelačić, Rong Gu, Cristina Seceleanu, Ning Xiong, Peter Backeman, Tiberiu Seceleanu, Zhennan Fei, and Ali Nouri

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

Abstract
The validation of Automated Driving Systems (ADSs) has shifted from distance-based metrics to Scenario-Based Testing (SBT). Large Language Models (LLMs) have emerged as powerful tools with potential for generating vehicular scenarios at scale. However, generative models, used for direct simulation synthesis, produce inadequate output, therefore necessitating a more structured compilation approach. In this regard, we present HASCO (Hybrid AI Simulation COmpiler), a system that translates natural-language driving scene specifications into executable simulation artifacts (XOSC/XODR files) for the esmini/OpenSCENARIO ecosystem. While LLMs excel at narrative parsing, we demonstrate that direct synthesis of simulation artifacts fails in the vast majority of cases due to hallucinated physics or schema violations. To resolve this, HASCO treats scenario creation as a compilation task rather than a generative one. The pipeline supports three compilation paths: direct synthesis, a Python intermediate (via scenariogeneration), and an ontology-guided path that grounds intent into an intermediate representation (IR) before compilation. We further evaluate a self-judging mechanism for automated repair. Across six operating modes evaluated on 40 real-world accident reports, the ontology-guided compiler and Python-based compiler achieve 95% and 90% executability rates, respectively (compared to 5% for direct synthesis). Additionally, we evaluate outputs on semantic fidelity, positioning HASCO as a robust tool for forensic scene reconstruction.
Cite as

Edin Jelačić, Rong Gu, Cristina Seceleanu, Ning Xiong, Peter Backeman, Tiberiu Seceleanu, Zhennan Fei, and Ali Nouri. HASCO: A Hybrid AI Simulation Compiler for Semantic Accident Reconstruction. In 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026). Open Access Series in Informatics (OASIcs), Volume 143, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jelacic_et_al:OASIcs.AEiC.2026.4,
  author =	{Jela\v{c}i\'{c}, Edin and Gu, Rong and Seceleanu, Cristina and Xiong, Ning and Backeman, Peter and Seceleanu, Tiberiu and Fei, Zhennan and Nouri, Ali},
  title =	{{HASCO: A Hybrid AI Simulation Compiler for Semantic Accident Reconstruction}},
  booktitle =	{30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)},
  pages =	{4:1--4:22},
  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.4},
  URN =		{urn:nbn:de:0030-drops-259220},
  doi =		{10.4230/OASIcs.AEiC.2026.4},
  annote =	{Keywords: Autonomous Driving, OpenSCENARIO, Large Language Models, Scenario Generation, Semantic Reconstruction}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.10
Packing Compact Subgraphs with Applications to Districting

Authors: Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu

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

Abstract
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs [Prathamesh Dharangutte et al., 2025]. In particular, we improve the approximation factor from O(log n) to O(1) for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an O(1) approximation for packing radius-k districts (with a constant k) in planar and apex-minor-free graphs. In order to get a (1+ε) approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to 1), for bounded radius-k districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types.
Cite as

Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu. Packing Compact Subgraphs with Applications to Districting. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.FORC.2026.10,
  author =	{Chen, Ho-Lin and Chou, Po-Yu and Dharangutte, Prathamesh and Gao, Jie and Huang, Shang-En and Yu, Fang-Yi},
  title =	{{Packing Compact Subgraphs with Applications to Districting}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{10:1--10:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.10},
  URN =		{urn:nbn:de:0030-drops-259820},
  doi =		{10.4230/LIPIcs.FORC.2026.10},
  annote =	{Keywords: Approximation algorithms, algorithmic fairness}
}
Document
DOI: 10.4230/LITES.11.1.1
A Survey of Real-Time Support, Analysis, and Advancements in ROS 2

Authors: Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper

Published in: LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1

Abstract
The Robot Operating System 2 (ROS 2) has emerged as a relevant middleware framework for robotic applications, offering modularity, distributed execution, and communication. In the last six years, ROS 2 has drawn increasing attention from the real-time systems community and industry. This survey presents a comprehensive overview of research efforts that analyze, enhance, and extend ROS 2 to support real-time execution. We first provide a detailed description of the internal scheduling mechanisms of ROS 2 and its layered architecture, including the interaction with DDS-based communication and other communication middleware. We then review key contributions from the literature, covering timing analysis for both single- and multi-threaded executors, metrics such as response time, reaction time, and data age, and different communication modes. The survey also discusses community-driven enhancements to the ROS 2 runtime, including new executor algorithm designs, real-time GPU management, and microcontroller support via micro-ROS. Furthermore, we summarize techniques for bounding DDS communication delays, message filters, and profiling tools that have been developed to support analysis and experimentation. To help systematize this growing body of work, we introduce taxonomies that classify the surveyed contributions based on different criteria. This survey aims to guide both researchers and practitioners in understanding and improving the real-time capabilities of ROS 2.
Cite as

Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper. A Survey of Real-Time Support, Analysis, and Advancements in ROS 2. In LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1, pp. 1:1-1:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{casini_et_al:LITES.11.1.1,
  author =	{Casini, Daniel and Chen, Jian-Jia and Li, Jing and Reghenzani, Federico and Teper, Harun},
  title =	{{A Survey of Real-Time Support, Analysis, and Advancements in ROS 2}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:37},
  ISSN =	{2199-2002},
  year =	{2026},
  volume =	{11},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.11.1.1},
  URN =		{urn:nbn:de:0030-drops-257914},
  doi =		{10.4230/LITES.11.1.1},
  annote =	{Keywords: ROS 2, middleware, real-time, timing predictability, publish-subscribe}
}
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.18
TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control

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

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

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

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

Copy BibTex To Clipboard

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

Authors: Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, and Yisu Remy Wang

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
Most research on query optimization has centered on binary join algorithms like hash join and sort-merge join. However, recent years have seen growing interest in theoretically optimal algorithms, notably Yannakakis' algorithm. These algorithms rely on join trees, which differ from the operator trees for binary joins and require new optimization techniques. We propose three approaches to constructing join trees for acyclic queries. First, we give an algorithm to enumerate all join trees of an α-acyclic query by edits in linear time with amortized constant delay, which forms the basis of a cost-based optimizer for acyclic joins. Second, we show the Maximum Cardinality Search algorithm by Tarjan and Yannakakis constructs the unique shallowest join tree for any Berge-acyclic query, thus enabling parallel execution of large join queries. Finally, we prove that a simple algorithm by Hu et al. converts any connected left-deep linear plan of a γ-acyclic query into a join tree, allowing reuse of optimizers developed for binary joins.
Cite as

Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, and Yisu Remy Wang. Algorithms for Optimizing Acyclic Queries. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.ICDT.2026.17,
  author =	{Luo, Zheng and Van den Broeck, Wim and Van den Broeck, Guy and Wang, Yisu Remy},
  title =	{{Algorithms for Optimizing Acyclic Queries}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.17},
  URN =		{urn:nbn:de:0030-drops-256319},
  doi =		{10.4230/LIPIcs.ICDT.2026.17},
  annote =	{Keywords: Query Optimization, Join Trees, Enumeration}
}
Document
DOI: 10.4230/OASIcs.NG-RES.2026.2
Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping

Authors: Mohammad Samadi, Tiago Carvalho, Luís Miguel Pinho, and Sara Royuela

Published in: OASIcs, Volume 140, 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)

Abstract
Task-to-thread mapping is a key process in parallel applications to achieve the best possible performance. This process is even more challenging when it is required to meet the schedulability and timing requirements of critical systems. In these systems, mapping tasks to threads is usually carried out using static scheduling (i.e., offline mapping) to improve system schedulability, with several approaches being presented in the literature. Nevertheless, there has been little analysis on the impact that these static mapping approaches have on the schedulability of applications exploiting OpenMP, a model increasingly seen as a suitable mechanism to leverage the potential of parallel and heterogeneous processor architectures. This paper, therefore, performs a throughout evaluation of the recently presented heuristic task-to-thread mapping working with different heuristics through allocation and dispatching phases, compared with state-of-the-art, in terms of schedulability. This process is performed using a state-of-the-art schedulability analysis methodology through an integration of our simulator and an existing schedulability toolset. This evaluation allows for identifying the static heuristic mapping approaches that achieve tighter schedulability analysis than other methods in the literature.
Cite as

Mohammad Samadi, Tiago Carvalho, Luís Miguel Pinho, and Sara Royuela. Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping. In 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026). Open Access Series in Informatics (OASIcs), Volume 140, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{samadi_et_al:OASIcs.NG-RES.2026.2,
  author =	{Samadi, Mohammad and Carvalho, Tiago and Pinho, Lu{\'\i}s Miguel and Royuela, Sara},
  title =	{{Schedulability Analysis of OpenMP Applications Under Heuristic Task-To-Thread Mapping}},
  booktitle =	{7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)},
  pages =	{2:1--2:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-415-4},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{140},
  editor =	{Ali, Hazem Ismail and Kurunathan, Harrison},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2026.2},
  URN =		{urn:nbn:de:0030-drops-254204},
  doi =		{10.4230/OASIcs.NG-RES.2026.2},
  annote =	{Keywords: OpenMP, task-to-thread mapping, heuristics, response time, schedulability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.66
Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

Authors: Yupan Liu

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We investigate the computational hardness of estimating the quantum α-Rényi entropy S^𝚁_α(ρ) = (ln Tr(ρ^α))/(1-α) and the quantum q-Tsallis entropy S^𝚃_q(ρ) = (1-Tr(ρ^q))/(q-1), both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEA_q) ask whether S^𝚁_α(ρ) or S^𝚃_q(ρ), respectively, is at least τ_Y or at most τ_N, where τ_Y - τ_N is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-2 variants Rank2RényiQEA_α and Rank2TsallisQEA_q are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real order α > 0 and 0 < q ≤ 1, LowRankRényiQEA_α and LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ of polynomial rank. - For all real order q > 1, TsallisQEA_q is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
Cite as

Yupan Liu. Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 66:1-66:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.STACS.2026.66,
  author =	{Liu, Yupan},
  title =	{{Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{66:1--66:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.66},
  URN =		{urn:nbn:de:0030-drops-255550},
  doi =		{10.4230/LIPIcs.STACS.2026.66},
  annote =	{Keywords: computational hardness, quantum state testing, quantum R\'{e}nyi entropy, quantum Tsallis entropy, von Neumann entropy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.61
Random Unitaries in Constant (Quantum) Time

Authors: Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.
Cite as

Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. Random Unitaries in Constant (Quantum) Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 61:1-61:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{foxman_et_al:LIPIcs.ITCS.2026.61,
  author =	{Foxman, Ben and Parham, Natalie and Vasconcelos, Francisca and Yuen, Henry},
  title =	{{Random Unitaries in Constant (Quantum) Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{61:1--61:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.61},
  URN =		{urn:nbn:de:0030-drops-253481},
  doi =		{10.4230/LIPIcs.ITCS.2026.61},
  annote =	{Keywords: Quantum Information, Pseudorandomness, Circuit Complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.27
Where to Place Your TEE? In Search of a Censorship-Resilient Design for Rollup Sequencers

Authors: Andrei Arusoaie, Claudiu-Nicu Bărbieru, Oana-Otilia Captarencu, Pascal Felber, Corentin Libert, Emanuel Onica, Etienne Rivière, Valerio Schiavoni, and Peterson Yuhala

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Ethereum is the dominant blockchain ecosystem capable of executing Turing-complete smart contracts. Rollups gained significant traction as the primary layer 2 (L2) solution meant to bring horizontal scalability to the main Ethereum network (L1). A core component of any rollup is the sequencer, which creates new L2 blocks to be submitted in rollup batches to L1. In most of the current rollup architectures, this component is centralised. As a result, these designs are prone to inconspicuous censorship practices by the sequencer. Trusted execution environments (TEEs) can guarantee the integrity of various sequencer components, which is instrumental in addressing censorship. However, the reaction of the system design to censorship attempts depends on where a TEE is integrated and which components it protects. In particular, this reaction is limited in the case of a monolithic TEE-protected sequencer design. Proposer-Builder Separation (PBS) is a non-monolithic paradigm adopted on L1, which separates the production of blocks from proposing them for inclusion in the blockchain. Recently, PBS has been considered for integration with L2 sequencers, with an impact on alleviating censorship. In this paper, we explore the design space of TEE-integrating PBS and non-PBS sequencer variants. First, we introduce a formal framework for the censorship actions that captures the specificity of the L2 sequencer. Then, we analyse to what extent the different designs address these censorship actions. Our main contribution is a novel design variation that allows for a precise observation of censored transactions. In the presence of TEEs, in a PBS setting, we demonstrate this precise observability, which is necessary to enable resilience to censorship.
Cite as

Andrei Arusoaie, Claudiu-Nicu Bărbieru, Oana-Otilia Captarencu, Pascal Felber, Corentin Libert, Emanuel Onica, Etienne Rivière, Valerio Schiavoni, and Peterson Yuhala. Where to Place Your TEE? In Search of a Censorship-Resilient Design for Rollup Sequencers. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arusoaie_et_al:LIPIcs.OPODIS.2025.27,
  author =	{Arusoaie, Andrei and B\u{a}rbieru, Claudiu-Nicu and Captarencu, Oana-Otilia and Felber, Pascal and Libert, Corentin and Onica, Emanuel and Rivi\`{e}re, Etienne and Schiavoni, Valerio and Yuhala, Peterson},
  title =	{{Where to Place Your TEE? In Search of a Censorship-Resilient Design for Rollup Sequencers}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.27},
  URN =		{urn:nbn:de:0030-drops-252000},
  doi =		{10.4230/LIPIcs.OPODIS.2025.27},
  annote =	{Keywords: Rollups, Trusted Execution Environments, Censorship}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.9
An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Authors: Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh

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

Abstract
We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph G and integers d and k, the standard problem asks whether G contains a packing of vertex-disjoint cycles, each of length ≤ d, covering at least k vertices in total. In the multi-agent setting we consider, the vertex set is partitioned over several agents who reject a cycle packing as solution if it can be modified into an alternative packing that covers more of their own vertices. A cycle packing is called rejection-proof if no agent rejects it and the problem asks whether such a packing exists that covers at least k vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this Σ₂^P-complete problem that is polynomial in k for all constant values of d. We also provide a 2^𝒪(k log k) + n^𝒪(1) algorithm based on it and show that this FPT algorithm is asymptotically optimal under the ETH. Further, we generalize the problem by including an additional positive integer c in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant c, the resulting problem simplifies from being Σ₂^P-complete to NP-complete. The super-exponential lower bound already holds for c = 2, though. We present an ad-hoc single-exponential algorithm for c = 1. These results reveal an interesting discrepancy between the classical and parameterized complexity of the problem and give a good view of what makes it hard.
Cite as

Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh. An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2025.9,
  author =	{Jansen, Bart M. P. and Lamme, Jeroen S. K. and Verhaegh, Ruben F. A.},
  title =	{{An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.9},
  URN =		{urn:nbn:de:0030-drops-251414},
  doi =		{10.4230/LIPIcs.IPEC.2025.9},
  annote =	{Keywords: Parameterized complexity, Multi-agent kidney exchange, Kernelization, Set packing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.23
Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes

Authors: Archit Chauhan, Samir Datta, and M. Praveen

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Constructing a Depth First Search (DFS) tree is a fundamental graph problem, whose parallel complexity is still not settled. Reif showed parallel intractability of lex-first DFS. In contrast, randomized parallel algorithms (and more recently, deterministic quasipolynomial parallel algorithms) are known for constructing a DFS tree in general (di)graphs. However a deterministic parallel algorithm for DFS in general graphs remains an elusive goal. Working towards this, a series of works gave deterministic NC algorithms for DFS in planar graphs and digraphs. We further extend these results to more general graph classes, by providing NC algorithms for (di)graphs of bounded genus, and for undirected H-minor-free graphs where H is a fixed graph with at most one crossing. For the case of (di)graphs of bounded treewidth, we further improve the complexity to a Logspace bound. Constructing a maximal path is a simpler problem (that reduces to DFS) for which no deterministic parallel bounds are known for general graphs. For planar graphs a bound of O(log n) parallel time on a CRCW PRAM (thus in NC²) is known. We improve this bound to Logspace.
Cite as

Archit Chauhan, Samir Datta, and M. Praveen. Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.FSTTCS.2025.23,
  author =	{Chauhan, Archit and Datta, Samir and Praveen, M.},
  title =	{{Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.23},
  URN =		{urn:nbn:de:0030-drops-251041},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.23},
  annote =	{Keywords: Parallel Complexity, Graph Algorithms, Depth First Search, Maximal Path, Planar Graphs, Minor-Free, Treewidth, Logspace}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.47
Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems

Authors: Yusuke Kobayashi and Bingkai Lin

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

Abstract
In the Pinwheel Packing problem, we are given a set of recurring tasks, each associated with a positive integer a_i for task i. The objective is to select one task to perform each day such that every task i is performed at least once within every a_i consecutive days. The exact computational complexity of this problem, where ∑ 1/a_i = 1, has remained an open question for more than 30 years; in particular, it is still unknown whether the problem is NP-hard. The first contribution of this paper is to show that Pinwheel Packing cannot be solved in polynomial time under a standard complexity assumption, improving upon the hardness result shown by Jacobs and Longo. Additionally, we present fixed-parameter algorithms for variants of Pinwheel Packing, parameterized by the number of tasks.
Cite as

Yusuke Kobayashi and Bingkai Lin. Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2025.47,
  author =	{Kobayashi, Yusuke and Lin, Bingkai},
  title =	{{Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.47},
  URN =		{urn:nbn:de:0030-drops-249558},
  doi =		{10.4230/LIPIcs.ISAAC.2025.47},
  annote =	{Keywords: Pinwheel Scheduling, Polynomial-time Solvability, Packing and Covering, Fixed Parameter Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.53
A Parameterized Study of Secluded Structures in Directed Graphs

Authors: Jonas Schmidt, Shaily Verma, and Nadym Mallek

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

Abstract
Given an undirected graph G and an integer k, the Secluded Π-Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property Π and has at most k neighbors in the rest of the graph. This problem has been extensively studied; however, there is no prior study of the problem in directed graphs. This question has been mentioned by Jansen et al. [ISAAC'23]. In this paper, we initiate the study of Secluded Subgraph problems in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems {In, Out, Total}-Secluded Π-Subgraph, where given a directed graph G and an integer k, we want to find an induced subgraph satisfying Π of maximum size that has at most k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties Π. In particular, we prove the following parameterized results: - We design an FPT algorithm for the Total-Secluded Strongly Connected Subgraph problem when parameterized by k. - We show that the Out-Secluded ℱ-Free Subgraph problem with parameter k is W[1]-hard, where ℱ is a family of directed graphs except any subgraph of a star graph whose edges are directed towards the center. This result also implies that In/Out-Secluded DAG is W[1]-hard, unlike the undirected variants of the two problems, which are FPT. - We design an FPT-algorithm for In/Out/Total-Secluded α-Bounded Subgraph when parameterized by k, where α-bounded graphs are a superclass of tournaments. - For undirected graphs, we improve the best-known FPT algorithm for Secluded Clique by providing a faster FPT algorithm that runs in time 1.6181^k n^𝒪(1).
Cite as

Jonas Schmidt, Shaily Verma, and Nadym Mallek. A Parameterized Study of Secluded Structures in Directed Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:LIPIcs.ISAAC.2025.53,
  author =	{Schmidt, Jonas and Verma, Shaily and Mallek, Nadym},
  title =	{{A Parameterized Study of Secluded Structures in Directed Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.53},
  URN =		{urn:nbn:de:0030-drops-249616},
  doi =		{10.4230/LIPIcs.ISAAC.2025.53},
  annote =	{Keywords: Secluded Subgraph, Parametrized Complexity, Directed Graphs, Strong Connectivity}
}
  • Refine by Type
  • 55 Document/PDF
  • 49 Document/HTML

  • Refine by Publication Year
  • 11 2026
  • 35 2025
  • 1 2024
  • 3 2023
  • 1 2018
  • Show More...

  • Refine by Author
  • 3 Chen, Jian-Jia
  • 2 Italiano, Giuseppe F.
  • 1 Alahmad, Bader Naim
  • 1 Alves, Jorge Manuel Afonso
  • 1 Arusoaie, Andrei
  • Show More...

  • Refine by Series/Journal
  • 36 LIPIcs
  • 9 OASIcs
  • 5 LITES
  • 4 TGDK
  • 1 DagSemProc

  • Refine by Classification
  • 6 Theory of computation → Graph algorithms analysis
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 4 Mathematics of computing → Graph theory
  • 3 Computer systems organization → Real-time systems
  • 3 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 3 Parameterized complexity
  • 2 Connectivity
  • 2 Kernelization
  • 2 Large Language Models
  • 1 (m
  • 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