It has been known that the insufficiency of linear coding in achieving the optimal rate of the general index coding problem is rooted in its rate’s dependency on the field size. However, this dependency has been described only through the two well-known matroid instances, namely the Fano and non- Fano matroids, which, in turn, limits its scope only to the fields with characteristic two. In this paper, we extend this scope to demonstrate the reliance of linear coding rate on fields with characteristic three. By constructing two index coding instances of size 29, we prove that for the first instance, linear coding is optimal only over the fields with characteristic three, and for the second instance, linear coding over any field with characteristic three can never be optimal. Another main contribution of this paper is to reduce the key constraints on the space of the linear coding for each index coding instance of size 29 into a matroid instance with the ground set of size 9, whose linear representability is dependent on the fields with characteristic three. The proofs and discussions provided in this paper through using these two relatively small matroid instances will shed light on the underlying reason causing the linear coding to become insufficient for the general index coding problem.

In this paper, we propose a new scalar linear coding scheme for the index coding problem called update-based maximum column distance (UM CD) coding scheme. The central idea in each transmission is to code messages such that one of the receivers with the minimum size of side information is instantaneously eliminated from unsatisfied receivers. One main contribution of the paper is to prove that the other satisfied receivers can be identified after each transmission, using a polynomial-time algorithm solving the well-known maximum cardinality matching problem in graph theory. This leads to determining the total number of transmissions without knowing the coding coefficients. Once this number and what messages to transmit in each round is found, we then propose a method to determine all coding coefficients from a sufficiently large finite field. We provide concrete instances where the proposed UM CD scheme has a better broadcast performance compared to the most efficient existing linear coding schemes, including the recursive scheme (Arbabjolfaei and Kim, 2014) and the interlinked-cycle cover scheme (Thapa et al., 2017).

Insufficiency of linear coding for the network coding problem was first proved by providing an instance which is solvable only by nonlinear network coding (Dougherty et al., 2005). Based on the work of Effros et al., 2015, this specific network coding instance can be modeled as a groupcast index coding (GIC) instance with 74 messages and 80 users (where a message can be requested by multiple users). This proves the insufficiency of linear coding for the GIC problem. Using the systematic approach proposed by Maleki$et$al., 2014, the aforementioned GIC instance can be cast into a unicast index coding (UIC) instance with more than 200 users, each wanting a unique message. This confirms the necessity of nonlinear coding for the UIC problem, but only for achieving the entire capacity region. Nevertheless, the question of whether nonlinear coding is required to achieve the symmetric capacity (broadcast rate) of the UIC problem remained open. In this paper, we settle this question and prove the insufficiency of linear coding, by directly building a UIC instance with only 36 users for which there exists a nonlinear index code outperforming the optimal linear code in terms of the broadcast rate.

In this work, we study the secure index coding problem where there are security constraints on both legitimate receivers and eavesdroppers. We develop two performance bounds (i.e., converse results) on the symmetric secure capacity. The first one is an extended version of the basic acyclic chain bound (Liu and Sadeghi, 2019) that takes security constraints into account. The second converse result is a novel information-theoretic lower bound on the symmetric secure capacity, which is interesting as all the existing converse results in the literature for secure index coding give upper bounds on the capacity.