This paper investigates the optimization of physical layer security (PLS) in intelligent reflecting surface (IRS)-assisted wireless networks under imperfect channel state information (CSI). Traditional PLS techniques often assume perfect CSI, which is difficult to obtain in IRS-assisted systems due to their passive nature and limited signal processing capabilities. To address this challenge, we derive, under the imperfect CSI condition, a novel expression for the secrecy outage probability (SOP) and propose an optimization framework to minimize the SOP by jointly designing the beamforming vector and the IRS phase-shift matrix. The proposed approach employs alternating optimization, utilizing the generalized Rayleigh quotient for beamforming and the generalized Dinkelbach algorithm for phase-shift adjustments. Furthermore, we derive a power scaling law that reveals significant energy efficiency gains with an increasing number of IRS elements. Simulation results validate the effectiveness of the proposed framework, demonstrating substantial improvements in secrecy performance over baseline schemes. This work underscores the potential of IRS-assisted systems in enhancing secure communications for future wireless networks.

The undirected multiple unicast network coding conjecture states that network coding is equivalent to routing in terms of rate benefit in undirected multiple unicast networks. So far, the conjecture is confirmed only for a handful of networks and network classes. Motivated by the quest for a possible counterexample and a tighter information-theoretic upper bound, this paper focuses on asymmetric demand vectors and examines the gap between the routing rates and known upper bounds for information flow. Specifically, a particular case of asymmetric demands called partition-symmetric demands for Type-I layered networks is introduced, and it is shown that for Type-I bipartite networks, the partition upper bound is achievable by a routing solution. A scheme called a parallel combination of solutions is introduced to obtain a solution from solutions for sub-networks. For Type-I 3-layer networks, a set of demand vectors is characterized such that the partition bound is achievable by a parallel combination. With a linear programming formulation, the gaps between the rates by proposed routing solutions and known upper bounds are analyzed.

Central to the field of information theory is the study of the entropy function and the possible values it can attain when applied to subsets of sets of arbitrarily correlated random variables. The set of attainable entropy vectors over three variables $\Gamma _3^{\ast}$ is not fully understood. A complete description of $\Gamma _3^{\ast}$ requires the analysis and characterization of the faces of the related polymatroid, Γ3. Thus far, only three faces of Γ3have been fully characterized. These faces are either one or two dimensional. Less concrete success has been attained for more complex faces. This paper focuses on a four-dimensional face $F_6^4$, and presents a novel approach to analyzing a complex face of Γ3by reducing the problem to a two-dimensional subset of the face. Through this approach, this paper attains novel insights and a tighter inner bound on $F_6^4$ than those that have been established thus far. This method demonstrates a possible way to fully characterize $F_6^4$ through the analysis of the simpler two dimensional subset.

Properties of the Shannon entropy vectors are instrumental for analyzing the limits of reliable communication for various communication models. However, the set of all Shannon entropy vectors is not yet known even for three random variables. Often, there are constraints on the entropy vectors of random variables due to the underlying communication model, e.g., functional dependence, independence, and Markov chain constraints. Moreover, the entropy vectors may be constrained to belong to a specific class for a given model, e.g., belonging to the class of quasi-uniform entropy vectors due to code design constraints. This paper presents distribution construction approaches and converse results for such constrained entropy vectors. We present three approaches for constructing distributions such that corresponding entropy vectors satisfy given constraints: (i) by exploiting functional dependence constraints, (ii) by quasiuniform constructions, and (iii) by using independent random vectors. In particular, these approaches are utilized to show the looseness of the known inner bounds for constrained entropy vectors for three random variables. We also present converse results for entropy vectors constrained by basic equalities and quasi-uniformity.

The convex closure of entropy vectors for quasi-uniform random vectors is the same as the closure of the entropy region. Thus, quasi-uniform random vectors constitute an important class of random vectors for characterizing the entropy region. Moreover, the one-to-one correspondence between quasi-uniform codes and quasi-uniform random vectors makes quasi-uniform random vectors of central importance for designing effective codes for communication systems. In this paper, we present a novel approach that utilizes quasi-uniform random vectors for characterizing the boundary of the almost entropic region. In particular, we use the notion of quasi-uniform random vectors to establish looseness of known inner bounds for the entropy vectors at the boundary of the almost entropic region for three random variables. For communication models such as network coding, our approach can be applied to design network codes from quasi-uniform entropy vectors.

One of the important unsolved problems in information theory is the conjecture that the undirected multiple-unicast network information capacity is the same as the routing capacity. This conjecture is verified only for a handful of networks and network classes. Moreover, only two explicit upper bounds on information capacity are known for general undirected networks: the sparsest cut bound and the linear programming bound. In this paper, we present an information-theoretic upper bound, called thepartition bound, on the capacity of general undirected multiple-unicast networks. We show that a decision version problem of computing the bound is NP-complete. We present two classes of undirected multiple-unicast networks such that the partition bound is achievable by routing. Thus, the conjecture is proved for these classes of networks. Recently, the conjecture was proved for a new class of networks defined by properties relating to cut-set and source-sink paths. We show the existence of a network outside of this new class of networks such that the partition bound is achievable by routing.

In the fields of information theory and network coding, a complete characterization of the almost entropic region is a fundamental but inherently difficult open problem. This paper focuses on the characterization of this region via explicit inner bounds, optimization of functions over this region, and network code construction. One approach to study the entropic region is to put a constraint on the alphabets for involved random variables, enabling us to focus on a specific set of joint distributions. We present the notion of alphabet constrained entropic set and describe its properties, namely, its a closed and path-connected set. Motivated by the properties, a random local search algorithm is designed to find an entropic vector and associated distribution near to a given target vector and extended to optimize functions of joint entropies. We present significantly improved inner bound compared to known inner bounds for the almost entropic region involving four random variables using a refinement of our algorithm. Finally, another application of the algorithm is shown to construct network codes and index codes for a given rate vector in the capacity region. This approach to constructing network codes is novel and has an entirely different flavor than classical coding theoretic construction.

It is of central interest in information theory to determine whether a given vector in the entropy space is an almost entropic vector. This problem can be answered if all the information inequalities are known, but this is an extremely challenging problem. On the other hand, we can establish that a given vector is an entropy vector if we can show the existence of distribution such that the corresponding entropy vector is the same as the given vector. However, there is no known algorithm to solve this problem. Only for the simplest case of binary entropy vectors, an algorithm is known to solve this problem. In this paper, we present a recursive algorithm to determine whether a given vector is a quasi-uniform entropy vector and, if it is, to return a consistent quasi-uniform distribution. We also present two applications of the recursive procedure: (i) to generate all quasi-uniform distributions motivated by the problem of finding the smallest quasi-uniform distribution such that its entropy vector violates the well known Ingleton inequality and (ii) to obtain an entropy vector (not necessarily quasi-uniform) near to a target vector in the entropy space for random variables with given alphabet size.

One of the important unsolved problems in information theory is the conjecture that network coding has no rate benefit over routing in undirected unicast networks. Three known bounds on the symmetric rate in undirected unicast information networks are the sparsest cut, the LP bound and the partition bound. In this paper, we present three results on the partition bound. We show that the decision version problem of computing the partition bound is NP-complete. We give complete proofs of optimal routing schemes for two classes of networks that attain the partition bound. Recently, the conjecture was proved for a new class of networks and it was shown that all the network instances for which the conjecture is proved previously are elements of this class. We show the existence of a network for which the partition bound is tight, achievable by routing and is not an element of this new class of networks.

In this paper, we present a new technique to obtain upper bounds on undirected unicast network information capacity. Using this technique, we characterize an upper bound, called partition bound, on the symmetric rate of information flow in undirected unicast networks and give an algorithm to compute it. Two classes of networks are presented for which the bound is tight and the capacity is achievable by routing thus confirming the undirected unicast conjecture for these classes of networks. We also show that the bound can be loose in general and present an approach to tighten it.

The entropy region is a fundamental object in information theory. An outer bound for the entropy region is defined by a minimal set of Shannon-type inequalities called elemental inequalities also referred to as the Shannon region. This paper focuses on characterization of the entropic points at the boundary of the Shannon region for three random variables. The proper faces of the Shannon region form its boundary. We give new outer bounds for the entropy region in certain faces and show by explicit construction of distributions that the existing inner bounds for the entropy region in certain faces are not tight.

The minimal set of Shannon-type inequalities (or elemental inequalities) plays a central role in efficiently determining whether a given inequality is in fact Shannon-type or not and in computing the linear programming bound for network coding capacity. In many cases, random variables under consideration are subject to additional constraints, such as functional dependence and conditional independence constraints. For example, functional dependence constraints are common in many communication problems due to deterministic encoding and decoding constraints. In other situations, the variables involved may form a Markov chain or in general a Markov random field, leading to conditional independence constraint. Subject to additional constraints, the challenge is how to identify the non-redundant inequalities. While one can always numerically determine the non-redundant inequalities (subject to additional linear equality constraints), it will be instrumental and also important if the non-redundant inequalities can be listed explicitly. In this paper, we show that this is achievable under the functional dependence and full conditional independence constraints.

The minimal set of Shannon-type inequalities, called elemental inequalities, plays a central role in efficiently determining whether a given inequality is in fact Shannon-type or not and in computing the linear programming bound for network coding capacity. In previous work we characterised a minimal set when functional dependence constraints are present. In this work we further generalize the characterisation to include Markov random field (MRF) structures which are defined by full conditional mutual independence constraints.

This paper focuses on the problem of finding a distribution for an associated entropic vector in the entropy space nearest to a given, possibly non-entropic, target vector for random variables with a constraint on alphabet size. We show the feasibility to find distribution for associated vector via a sequence of perturbations in the probability mass function. Then we present an algorithm for numerically solving the problem together with extensions, applications, and comparison with the known results.

The minimal set of Shannon-type inequalities (referred to as elemental inequalities), plays a central role in determining whether a given inequality is Shannon-type. Often, there arises a situation where one needs to check whether a given inequality is a constrained Shannon-type inequality. Another important application of elemental inequalities is to formulate and compute the Shannon outer bound for multi-source multi-sink network coding capacity. Under this formulation, it is the region of feasible source rates subject to the elemental inequalities and network coding constraints that is of interest. Hence it is of fundamental interest to identify the redundancies induced amongst elemental inequalities when given a set of functional dependence constraints. In this paper, we characterize a minimal set of Shannon-type inequalities when functional dependence constraints are present.

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the linear programming bound, which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of linear programming bounds to networks with correlated sources is largely open. Source dependence is usually specified through a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependences via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”. Using such auxiliary random variables, we also give implicit and explicit outer bounds on the capacity of networks with correlated sources. The characterisation of correlation or joint distribution via Shannon entropy functions is also applicable to other information measures, such as Rényi entropy and Tsallis entropy.

Explicit characterization of the capacity region of communication networks is a long-standing problem. While it is known that network coding can outperform routing and replication, the set of feasible rates is not known in general. Characterizing the network coding capacity region requires the determination of the set of all entropic vectors. Furthermore, computing the explicitly known linear programming bound is infeasible in practice due to an exponential growth in complexity as a function of network size. This paper focuses on the fundamental problems of characterization and computation of outer bounds for multi-source multi-sink networks. Starting from the known local functional dependence induced by the communication network, we introduce the notion of irreducible sets, which characterize implied functional dependence. We provide recursions for the computation of all maximal irreducible sets. These sets act as information-theoretic bottlenecks, and provide an easily computable outer bound for networks with correlated sources. We extend the notion of irreducible sets (and resulting outer bound) for networks with independent sources. We compare our bounds with existing bounds in the literature. We find that our new bounds are the best among the known graph theoretic bounds for networks with correlated sources and for networks with independent sources.

The max-flow outer bound is achievable by regenerating codes for functional repair distributed storage system. However, the capacity of exact repair distributed storage system is an open problem. In this paper, the linear programming bound for exact repair distributed storage systems is formulated. A notion of symmetrical sets for a set of random variables is given and equalities of joint entropies for certain subsets of random variables in a symmetrical set is established. Concatenation coding scheme for exact repair distributed storage systems is proposed and it is shown that concatenation coding scheme is sufficient to achieve any admissible rate for any exact repair distributed storage system. Equalities of certain joint entropies of random variables induced by concatenation scheme is shown. These equalities of joint entropies are new tools to simplify the linear programming bound and to obtain stronger converse results for exact repair distributed storage systems.

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the Linear Programming bound which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of Linear Programming bounds to networks with correlated sources is largely open. Source dependence is usually specified via a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependencies via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”.

This paper presents a lower bound on the mutual information between any two sets of source/edge random variables in a general multi-source multi-sink network. This bound is useful to derive a new class of better information-theoretic upper bounds on the network coding capacity given existing edge-cut based bounds. A refined functional dependence bound is characterized from the functional dependence bound using the lower bound. It is demonstrated that the refined versions of the existing edge-cut based outer bounds obtained using the mutual information lower bound are stronger.

The polymatroid axioms are dominantly used to study the capacity limits of various communication systems. In fact for most of the communication systems, for which the capacity is known, these axioms are solely required to obtain the characterization of capacity. Moreover, the polymatroid axioms are stronger tools to tackle the implication problem for conditional independencies compared to the axioms used in Bayesian networks. However, their use is prohibitively complex as the number of random variables increases since the number of inequalities to consider increases exponentially. In this paper we give a compact characterization of the minimal set of polymatroid axioms when arbitrary conditional independence and functional dependence constraints are given. In particular, we identify those elemental equalities which are implied by given constraints. We also identify those elemental inequalities which are redundant given the constraints.

Explicit characterization and computation of the multi-source network coding capacity region (or even bounds) is long standing open problem. In fact, finding the capacity region requires determination of the set of all entropic vectors Gamma*, which is known to be an extremely hard problem. On the other hand, calculating the explicitly known linear programming bound is very hard in practice due to an exponential growth in complexity as a function of network size. We give a new, easily computable outer bound, based on characterization of all functional dependencies in networks. We also show that the proposed bound is tighter than some known bounds.