Capacity of Non-Separable Networks with Restricted Adversaries

Christopher Hojny, Altan B. Kılıç, Sascha Kurz, Alberto Ravagnani

In the world of network coding, we usually assume the worst: an "omniscient" adversary who can corrupt any $t$ edges in a network. Under this assumption, the math is relatively clean. You can design an "inner" network code to handle the routing and an "outer" error-correcting code to handle the noise separately. But what happens if the adversary is restricted? What if they can only attack specific, vulnerable links (like a wireless hop in an otherwise wired network)?

This paper, recently published by researchers from the Eindhoven University of Technology and the University of Bayreuth, dives into this "restricted adversary" model. They show that when an attacker's reach is limited, the traditional rules of the game break down, requiring a radical rethink of how we design secure communication.

TL;DR

The authors prove that networks with restricted adversaries are "non-separable," meaning you must design the network's internal logic and the external error-correction code jointly to reach maximum capacity. They provide the first exact capacity results for several fundamental network families and use computational solvers to find record-breaking new codes for small communication alphabets.

What Problem Does This Paper Address?

In classical network coding, the cut-set bound is the gold standard for determining capacity. It essentially says your throughput is limited by the "thinnest" part of the network. If an adversary can hit any $t$ edges, we use rank-metric codes (like Gabidulin codes) to fix the errors. This approach is separable: the network nodes don't need to know what the error-correction code is, and vice versa.

However, if the adversary is restricted to a specific subset of edges, the cut-set bound is no longer "tight"—it overestimates how much data we can send. To hit the true capacity, intermediate nodes must perform network decoding, locally processing and "cleaning" data before forwarding it. The core challenge is that we don't have a general formula for the capacity of these networks, and finding the best codes is computationally grueling.

Methods

The authors employ a mix of heavy-duty combinatorics and modern optimization:

  1. Network Decoding Framework: Instead of simple linear forwarding, intermediate nodes use specific functions to map incoming packets to outgoing ones, effectively acting as local decoders.
  2. MINLP and SAT Solvers: To find the best possible codes for small alphabets (where the math is most difficult), the authors modeled the code search as a Mixed-Integer Nonlinear Program (MINLP). They used the Gurobi solver and SAT solvers (like Glucose4 via the pysat library) to exhaustively search for "unambiguous" codes.
  3. Structural Generalization: They introduced a new family of "2-level" networks ($\mathfrak{S}_{a,b,s}$) that generalizes previous benchmarks, allowing them to study how different network topologies affect capacity in a unified way.

Datasets

While this isn't a machine learning paper, the authors evaluate their methods on established "benchmark" network topologies used in information theory:

  • Family B and Family E: Two fundamental 2-level network structures introduced in prior literature.
  • The Diamond Network: The simplest known example where traditional cut-set bounds fail.
  • New Generalized Family: A newly introduced benchmark ($\mathfrak{S}_{a,b,s}$) used to test the limits of their capacity theorems.

Key Insights and Ideas

  • The Death of Separability: The most significant insight is that restricted adversaries destroy the "separability" property. You cannot simply pick a great error-correcting code and expect it to work on any network. The code must be "aware" of the specific network topology and the specific edges the adversary can touch.
  • Metric Matters: The authors show that while the rank metric is great for unrestricted adversaries, it fails to provide separability in the restricted case. Furthermore, they prove that the standard Hamming metric (counting bit-flips) is almost never separable, even in simple networks.
  • Local Logic is Key: In Family E networks, they found that capacity is achieved when intermediate nodes act as "majority-rule" decoders, injecting a specific "!" symbol when they detect an unrecoverable conflict.

Key Results

  • Exact Capacity for Family E: The authors derived a closed-form expression for the capacity of Family E networks for any adversarial power $t$. For example, if $t=2m$, the capacity is $\log_{|\mathcal{A}|} \lfloor |\mathcal{A}| / (m+1) \rfloor$.
  • Breaking Records in Family B: Using their SAT-based search, they improved the lower bounds for small alphabets. For an alphabet of size 4 on a specific Family B network, they found a code of size 10, surpassing the previous best of 9.
  • Generalized Capacity: They provided tight upper and lower bounds for their new $\mathfrak{S}_{a,b,s}$ family, showing exactly how the number of incoming and outgoing edges at intermediate nodes dictates the maximum flow of information.

Limitations and Future Work

The primary limitation is computational complexity. Finding these optimal codes is an NP-hard problem. While the authors' MINLP approach is powerful, it hit a wall after about 7.6 hours of computation for even relatively small networks.

Future Directions: 1. Scaling up: Developing more efficient algorithms to find codes for larger networks and larger alphabets. 2. Separability Criteria: The authors want to find a formal mathematical criterion that can tell an engineer, "Yes, this specific network is separable under the Hamming metric," without needing to run a massive simulation. 3. Multi-shot Capacity: This paper focuses on "one-shot" capacity (sending data once). Extending this to "multi-shot" scenarios (streaming data over time) remains a major open question.

Summary updated

Abstract

This paper investigates the problem of single-source multicasting over a communication network in the presence of restricted adversaries. When the adversary is constrained to operate only on a prescribed subset of edges, classical cut-set bounds are no longer tight, and achieving capacity typically requires a joint design of the outer code and the inner (network) code. This stands in sharp contrast with the case of unrestricted adversaries, where capacity can be achieved by combining linear network coding with appropriate rank-metric outer codes. Building on the framework of network decoding, we determine the exact one-shot capacity of one of the fundamental families of 2-level networks introduced in [4], and we improve the best currently known lower bounds for another such family. In addition, we introduce a new family of networks that generalizes several known examples, and derive partial capacity results that illustrate a variety of phenomena that arise specifically in the restricted-adversary setting. Finally, we investigate the concept of separability of networks with respect to both the rank metric and the Hamming metric.
BibTeX
@misc{hojny2026capacity,
  author = {Christopher Hojny and Altan B. Kılıç and Sascha Kurz and Alberto Ravagnani},
  title = {{Capacity of Non-Separable Networks with Restricted Adversaries}},
  year = {2026},
  eprint = {2603.08246},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.08246},
}

Loading related content...

Figure