Multi-user settings present new challenges to the problems of characterizing the fundamental limits and design of explicit schemes for a network. In the first direction of the dissertation we consider the problem of explicit scheme design for digital fingerprinting, which is a multi-user extension of watermarking. First, minimum distance decoding is studied and an explicit scheme based on graph codes under Belief Propagation decoding is proposed which achieves vanishing misidentification probability for rates as high as 0.11. This is a marked improvement over the best available designs in the literature. A specific coalition attack nicknamed “zero capacity attack” is also identified for which the minimum distance decoder fails to extend to larger coalition sizes than 2.
Next, we study the application of tree codes and sequential decoding to the problem and establish the existence of a good code which can achieve vanishing error probability with finite average complexity for rates below a cut-off rate. Using random Convolutional codes we provide numerical results indicating vanishing error probability for rates as high as 0.16. Our numerical results are extended to coalition size of 3 under the zero capacity collusion attack using a novel family of non-linear tree codes based on concatenation of random Convolutional codes and tree codes under bidirectional sequential decoding. We achieve vanishing error probability for rates as high as 0.05.
In the second direction of the thesis, we study the fundamental limits of multi-user communications. We begin by considering the X channel which contains most of the well studied multi-terminal networks (e.g., multiple-access, broadcast and interference channels). We propose a signaling scheme and derive the achievable rate region. The achievable region includes the best known rate regions for the special cases and outperforms the best available one in the literature. We conclude this direction of the thesis by studying cognitive cooperation in downlink communication for cellular systems. A singling scheme based on joint interference alignment and dirty paper coding is proposed and the achievable sum degrees of freedom region is characterized. Moreover, an outer bound on this region is derived and it is established that our proposed scheme is optimal for some special cases.