100 Search Results for "Chen, Xi"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.61
Sublinear-Query Relative-Error Testing of Halfspaces

Authors: Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, and Tianqi Yang

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

Abstract
The relative-error property testing model was introduced in [Chen et al., 2024] to facilitate the study of property testing for "sparse" Boolean-valued functions, i.e. ones for which only a small fraction of all input assignments satisfy the function. In this framework, the distance from the unknown target function f that is being tested to a function g is defined as Vol(f△g)/Vol(f), where the numerator is the fraction of inputs on which f and g disagree and the denominator is the fraction of inputs that satisfy f. Recent work [Chen et al., 2026] has shown that over the Boolean domain {0,1}ⁿ, any relative-error testing algorithm for the fundamental class of {halfspaces} (i.e. linear threshold functions) must make Ω(log n) oracle calls. In this paper we complement the [Chen et al., 2026] lower bound by showing that halfspaces can be relative-error tested over ℝⁿ under the standard N(0,I_n) Gaussian distribution using a sublinear number of oracle calls - in particular, substantially fewer than would be required for learning. Our results use a wide range of tools including Hermite analysis, Gaussian isoperimetric inequalities, and geometric results on noise sensitivity and surface area.
Cite as

Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, and Tianqi Yang. Sublinear-Query Relative-Error Testing of Halfspaces. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 61:1-61:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.61,
  author =	{Chen, Xi and De, Anindya and Huang, Yizhi and Nadimpalli, Shivam and Servedio, Rocco A. and Yang, Tianqi},
  title =	{{Sublinear-Query Relative-Error Testing of Halfspaces}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{61:1--61: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.61},
  URN =		{urn:nbn:de:0030-drops-264508},
  doi =		{10.4230/LIPIcs.ICALP.2026.61},
  annote =	{Keywords: Property testing, relative-error testing, halfspaces, Gaussian space}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.62
Relative-Error Unateness Testing

Authors: Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, and Yiding Zhang

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

Abstract
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [X. Chen et al., 2025; Chen et al., 2025; Chen et al., 2025]. In this paper we consider the problem of relative-error testing an unknown and arbitrary f: {0,1}ⁿ → {0,1} for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the n input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes Õ(log(N)/ε) samples and queries, where N = |f^{-1}(1)| is the number of satisfying assignments of the function that is being tested and the value of N is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of N and with high probability makes Õ(log(N)/ε) samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of N up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.
Cite as

Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, and Yiding Zhang. Relative-Error Unateness Testing. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.62,
  author =	{Chen, Xi and Palit, Diptaksho and Peshawaria, Kabir and Pires, William and Servedio, Rocco A. and Zhang, Yiding},
  title =	{{Relative-Error Unateness Testing}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{62:1--62:14},
  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.62},
  URN =		{urn:nbn:de:0030-drops-264511},
  doi =		{10.4230/LIPIcs.ICALP.2026.62},
  annote =	{Keywords: Property Testing, Relative Error}
}
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/LIPIcs.SoCG.2026.76
A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids

Authors: Clément Maria and Hoel Queffelec

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

Abstract
Knot theory is an active field of mathematics, in which combinatorial and computational methods play an important role. One side of computational knot theory, that has gained interest in recent years, both for complexity analysis and practical algorithms, is quantum topology and the computation of topological invariants issued from the theory. In this article, we leverage the rigidity brought by the representation-theoretic origins of the quantum invariants for algorithmic purposes. We do so by exploiting braids and the algebraic properties of the braid group to describe, analyze, and implement a fast algorithm to compute the Hecke representation of the braid group. We apply this construction to design a parameterized algorithm to compute the HOMFLY-PT polynomial of knots, and demonstrate its interest experimentally. Finally, we combine our fast Hecke representation algorithm with Garside theory, to implement a reservoir sampling search and find non-trivial braids with trivial Hecke representations with coefficients in ℤ/pℤ. We find explicitly several such braids, for the 4-strand and 5-strand braid groups.
Cite as

Clément Maria and Hoel Queffelec. A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 76:1-76:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.SoCG.2026.76,
  author =	{Maria, Cl\'{e}ment and Queffelec, Hoel},
  title =	{{A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{76:1--76:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.76},
  URN =		{urn:nbn:de:0030-drops-258838},
  doi =		{10.4230/LIPIcs.SoCG.2026.76},
  annote =	{Keywords: Hecke representation of the braid group, parameterized algorithm, HOMFLY-PT polynomial of knots, reservoir sampling, faithfulness of Hecke representation}
}
Document
DOI: 10.4230/OASIcs.PARMA-DITAM.2026.7
Linking High-Level Synthesis with FPGA Runtime Orchestration

Authors: Despoina Tomkou, Aggelos Ferikoglou, Dimosthenis Masouros, Sotirios Xydis, and Dimitrios Soudris

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

Abstract
FPGAs are increasingly being adopted across the edge-to-cloud continuum due to their ability to provide both high performance and energy efficiency. However, the complexity of programming FPGAs often leads to deployed designs that underutilize available resources. FPGA multi-tenancy has been proposed to enhance resource utilization, yet monolithic designs and dynamic workload demands continue to challenge efficient FPGA usage and compliance with Quality of Service requirements. To address these issues, we propose a novel framework for the optimal orchestration of FPGAs across the edge-to-cloud continuum while meeting user demands. The framework generates approximations of Pareto-optimal designs for each application, capturing trade-offs between performance and resource usage with minimal bitstream generation. This information allows the runtime orchestrator to select the most suitable design based on available PR regions and the QoS requirements of each user. Experimental results demonstrate that the proposed approach achieves an average reduction of QoS violations by a factor of 8.1× across diverse workloads and baseline configurations. Overall, the framework offers a practical and effective solution for realizing FPGA-as-a-Service across the edge-to-cloud continuum.
Cite as

Despoina Tomkou, Aggelos Ferikoglou, Dimosthenis Masouros, Sotirios Xydis, and Dimitrios Soudris. Linking High-Level Synthesis with FPGA Runtime Orchestration. In 17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026). Open Access Series in Informatics (OASIcs), Volume 141, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tomkou_et_al:OASIcs.PARMA-DITAM.2026.7,
  author =	{Tomkou, Despoina and Ferikoglou, Aggelos and Masouros, Dimosthenis and Xydis, Sotirios and Soudris, Dimitrios},
  title =	{{Linking High-Level Synthesis with FPGA Runtime Orchestration}},
  booktitle =	{17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026)},
  pages =	{7:1--7:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-416-1},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{141},
  editor =	{Baroffio, Davide and Busia, Paola and Denisov, Lev and Shukla, Nitin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.PARMA-DITAM.2026.7},
  URN =		{urn:nbn:de:0030-drops-256746},
  doi =		{10.4230/OASIcs.PARMA-DITAM.2026.7},
  annote =	{Keywords: FPGA, Orchestration, Partial Reconfiguration, FPGAaaS}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.6
EcoCell: Energy Conservation Through Traffic Shaping in Cellular Radio Access Networks

Authors: Zikun Liu, Seoyul Oh, Bill Tao, Yaxiong Xie, Anuj Kalia, and Deepak Vasisht

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

Abstract
Cellular networks contribute significantly to global energy demands and carbon emissions due to the millions of base stations deployed worldwide. We characterize the energy consumption of production base stations by performing fine-grained power and network telemetry measurements using off-the-shelf base stations. Our measurements reveal unique insights about how variations in temporal-usage patterns affect base station energy consumption. Based on these insights, we design EcoCell, a software-only solution that introduces energy-efficient traffic patterns in network flows. EcoCell can be implemented either as a traffic scheduler in the radio access network or as an independent middlebox. We evaluate EcoCell with five popular networked applications on a production basestation. We demonstrate savings up to 32% in dynamic energy consumption of a base station, without drops in application-level quality of experience.
Cite as

Zikun Liu, Seoyul Oh, Bill Tao, Yaxiong Xie, Anuj Kalia, and Deepak Vasisht. EcoCell: Energy Conservation Through Traffic Shaping in Cellular Radio Access Networks. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:OASIcs.NINeS.2026.6,
  author =	{Liu, Zikun and Oh, Seoyul and Tao, Bill and Xie, Yaxiong and Kalia, Anuj and Vasisht, Deepak},
  title =	{{EcoCell: Energy Conservation Through Traffic Shaping in Cellular Radio Access Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{6:1--6:25},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.6},
  URN =		{urn:nbn:de:0030-drops-255911},
  doi =		{10.4230/OASIcs.NINeS.2026.6},
  annote =	{Keywords: energy efficiency, traffic shaping, cellular networks, radio access networks}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.15
BISCAY: Practical Radio KPI Driven Congestion Control for Mobile Networks

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

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

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

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

Copy BibTex To Clipboard

@InProceedings{larrea_et_al:OASIcs.NINeS.2026.15,
  author =	{Larrea, Jon and Shreedhar, Tanya and Niemi, Atte and Sefiane, Adel and Marina, Mahesh K.},
  title =	{{BISCAY: Practical Radio KPI Driven Congestion Control for Mobile Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{15:1--15:32},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.15},
  URN =		{urn:nbn:de:0030-drops-256002},
  doi =		{10.4230/OASIcs.NINeS.2026.15},
  annote =	{Keywords: Cellular Networks, Congestion Control, LTE/5G}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.18
TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control

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

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

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

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

Copy BibTex To Clipboard

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

Authors: Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss

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

Abstract
Existing transport protocols in commodity datacenter networks struggle to provide low collective completion times (CCTs) to AI training collectives, as packet losses and retransmissions significantly degrade performance. We propose dcSim, an efficient transport that achieves low CCTs and practically lossless performance with commodity switches. In dcSim, each packet first employs a small simulation probe to traverse the network and explore congestion along a candidate path. Only packets whose simulation probes succeed are then transmitted, expecting to succeed as well. Evaluations confirm that dcSim achieves faster CCTs than existing schemes, with small queues and virtually zero packet loss. Finally, dcSim also excels in adverse conditions, including oversubscribed topologies.
Cite as

Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss. Simulate Before Sending: Rethinking Transport in Datacenter Networks. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{straussman_et_al:OASIcs.NINeS.2026.19,
  author =	{Straussman, Dan and Keslassy, Isaac and Shpiner, Alexander and Liss, Liran},
  title =	{{Simulate Before Sending: Rethinking Transport in Datacenter Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{19:1--19:22},
  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.19},
  URN =		{urn:nbn:de:0030-drops-256044},
  doi =		{10.4230/OASIcs.NINeS.2026.19},
  annote =	{Keywords: Datacenter networks, transport protocols, AI training, lossless networks}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.24
SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing

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

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

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

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

Copy BibTex To Clipboard

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

Authors: Amirmohammad Nazari, Rajit Manohar, and Robert Soulé

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

Abstract
In this paper, we propose a novel software/hardware design to improve I/O performance while maintaining existing POSIX-standard APIs. Our approach stands in contrast to existing kernel-bypass strategies that improve performance at the expense of abandoning familiar programming abstractions. Our key insight is that navigating the performance-functionality trade-off requires changes to the processor; it cannot be done without support of the CPU micro-architecture. Our design, called Accio, includes: dedicated hardware for interrupt management, a hardware assist for thread scheduling, tables in hardware that manage I/O state, and modifications to the operating system to support the new hardware. Our evaluation demonstrates that Accio saturates the bus bandwidth, reduces CPU usage by up to 66% compared to state-of-the-art kernel-bypass systems, and reduces latency to 1/12th of that of the Linux kernel, matching that of kernel-bypass systems.
Cite as

Amirmohammad Nazari, Rajit Manohar, and Robert Soulé. Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nazari_et_al:OASIcs.NINeS.2026.21,
  author =	{Nazari, Amirmohammad and Manohar, Rajit and Soul\'{e}, Robert},
  title =	{{Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{21:1--21:24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.21},
  URN =		{urn:nbn:de:0030-drops-256063},
  doi =		{10.4230/OASIcs.NINeS.2026.21},
  annote =	{Keywords: Networks, Operating Systems, I/O Optimization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.22
Modular Counting over 3-Element and Conservative Domains

Authors: Andrei A. Bulatov and Amirhossein Kazeminia

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

Abstract
In the Constraint Satisfaction Problem (CSP for short) the goal is to decide the existence of a homomorphism from a given relational structure {G} to a given relational structure {H}. If the structure {H} is fixed and {G} is the only input, the problem is denoted CSP({H}). In its counting version, #CSP({H}), the task is to find the number of such homomorphisms. The CSP and #CSP have been used to model a wide variety of combinatorial problems and have received a tremendous amount of attention from researchers from multiple disciplines. In this paper we consider the modular version of the counting CSPs, that is, problems of the form #_pCSP({H}) of counting the number of homomorphisms to {H} modulo a fixed prime number p. Modular counting has been intensively studied during the last decade, although mainly in the case of graph homomorphisms. Here we continue the program of systematic research of modular counting of homomorphisms to general relational structures. The main results of the paper include a new way of reducing modular counting problems to smaller domains and a study of the complexity of such problems over 3-element domains and over conservative domains, that is, relational structures that allow to express (in a certain exact way) every possible unary predicate.
Cite as

Andrei A. Bulatov and Amirhossein Kazeminia. Modular Counting over 3-Element and Conservative Domains. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2026.22,
  author =	{Bulatov, Andrei A. and Kazeminia, Amirhossein},
  title =	{{Modular Counting over 3-Element and Conservative Domains}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{22:1--22:20},
  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.22},
  URN =		{urn:nbn:de:0030-drops-255114},
  doi =		{10.4230/LIPIcs.STACS.2026.22},
  annote =	{Keywords: Constraint Satisfaction Problem, Modular Counting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.57
Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach

Authors: Antoine Joux and Karol Węgrzycki

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

Abstract
Lagarias and Odlyzko (J.ACM 1985) proposed a polynomial-time algorithm for solving "almost all" instances of the Subset Sum problem with n integers of size Ω(Γ_LO), where log₂(Γ_LO) > n² log₂(γ) and γ is a parameter of the lattice basis reduction (γ > √{4/3} for LLL). The algorithm of Lagarias and Odlyzko is a cornerstone of cryptography. However, the theoretical guarantee on the density of feasible instances has remained unimproved for almost 40 years. In this paper, we propose an algorithm that solves "almost all" instances of Subset Sum with integers of size Ω(√{Γ_LO}) after a single call to lattice reduction. Additionally, our approach allows solving the Subset Sum problem for multiple targets, whereas the previous method could handle only one target per call to lattice basis reduction. We introduce a modular arithmetic approach to the Subset Sum problem, leveraging lattice reduction to solve a linear system modulo a suitably large prime. By analyzing the lengths of the LLL-reduced basis vectors of both the primal and dual lattices simultaneously, we show that density guarantees can be improved.
Cite as

Antoine Joux and Karol Węgrzycki. Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{joux_et_al:LIPIcs.STACS.2026.57,
  author =	{Joux, Antoine and W\k{e}grzycki, Karol},
  title =	{{Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{57:1--57:19},
  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.57},
  URN =		{urn:nbn:de:0030-drops-255462},
  doi =		{10.4230/LIPIcs.STACS.2026.57},
  annote =	{Keywords: Average-Case Analysis, Subset Sum, Lattice Reduction, LLL}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.14
Computing Tarski Fixed Points in Financial Networks

Authors: Leander Besting, Martin Hoefer, and Lars Huth

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

Abstract
Modern financial networks are highly connected and result in complex interdependencies of the involved institutions. In the prominent Eisenberg-Noe model [Eisenberg and Noe, 2001], a fundamental aspect is clearing - to determine the amount of assets available to each financial institution in the presence of potential defaults and bankruptcy. A clearing state represents a fixed point that satisfies a set of natural axioms. Existence can be established (even in broad generalizations of the model) using Tarski’s theorem. While a maximal fixed point can be computed in polynomial time, the complexity of computing other fixed points is open. In this paper, we provide an efficient algorithm to compute a minimal fixed point. Our algorithm applies in a broad generalization of the Eisenberg-Noe model with any monotone, piecewise-linear payment functions and default costs. We also study claims trading, a local network adjustment to improve clearing, when networks are evaluated with minimal clearing. We provide an efficient algorithm to decide existence of Pareto-improving trades and compute optimal ones if they exist.
Cite as

Leander Besting, Martin Hoefer, and Lars Huth. Computing Tarski Fixed Points in Financial Networks. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{besting_et_al:LIPIcs.STACS.2026.14,
  author =	{Besting, Leander and Hoefer, Martin and Huth, Lars},
  title =	{{Computing Tarski Fixed Points in Financial Networks}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{14:1--14:18},
  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.14},
  URN =		{urn:nbn:de:0030-drops-255038},
  doi =		{10.4230/LIPIcs.STACS.2026.14},
  annote =	{Keywords: Tarski Fixed Points, Financial Networks, Minimal Clearing, Claims Trade}
}
  • Refine by Type
  • 100 Document/PDF
  • 76 Document/HTML

  • Refine by Publication Year
  • 27 2026
  • 47 2025
  • 5 2024
  • 7 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 16 Chen, Xi
  • 13 Servedio, Rocco A.
  • 5 De, Anindya
  • 3 Meng, Boning
  • 3 Nadimpalli, Shivam
  • Show More...

  • Refine by Series/Journal
  • 79 LIPIcs
  • 11 OASIcs
  • 2 LITES
  • 7 TGDK
  • 1 DagMan

  • Refine by Classification
  • 9 Theory of computation → Problems, reductions and completeness
  • 8 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 5 Computer systems organization → Real-time systems
  • 5 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Algorithmic mechanism design
  • Show More...

  • Refine by Keyword
  • 5 Large Language Models
  • 4 property testing
  • 3 Holant
  • 3 Property Testing
  • 3 communication complexity
  • 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