On Explicit Families of Outer Bounds for Broadcast Networks

Karakurt, Altug; Varanasi, Mahesh K.

Permalink

https://hdl.handle.net/2142/130318 Copy

Description

Title

On Explicit Families of Outer Bounds for Broadcast Networks

Author(s)

• Karakurt, Altug
• Varanasi, Mahesh K.

Issue Date

2025-09-17

Keyword(s)

• Broadcast networks
• Combination network
• Broadcast channel
• Groupcast
• Capacity region

Abstract

The cut-set bounds arise from the graph-theoretic notion of a cut and are used as outer bounds for broadcast networks. Although these bounds are tight for broadcasting a single message, they are loose when multiple messages are broadcasted. The generalized cut-set bounds (GCBs) were proposed in [1] in implicit form as a broader class of outer bounds. In this work, we build on the GCB framework and present two families of explicit outer bounds with associated structure. We also present two techniques to modify GCBs that we call GCB-mappings. These are mappings that the class of GCBs are closed under. They enable customizing known outer bounds to generate novel bounds with similar structure. We present a systematic approach for proving outer bounds for broadcast networks using these results. In addition to the concise proofs it yields, this approach also reveals common structure shared across the inequalities within a capacity region. We focus on the combination network (CN) as a special case to demonstrate our approach. First, we revisit the well-known capacity region for the 3-user complete message set and present an alternative converse proof using a single explicit family and a GCB-mapping. Next, we turn to a 4-user generalization of this problem that we call the cubic message set, which includes an additional receiver that decodes all seven original messages, as well as an additional unicast message. We show that our outer bounds are tight when specialized to this setting and prove the converse of the capacity region. Finally, we present an explicit outer bound for the 5-user extension of the cubic message set.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130318&&

Copyright and License Information

Copyright 2025 is held by Altug Karakurt and Mahesh K. Varanasi.

Owning Collections