Shannon theory aims for solutions/characterizations to infinite-dimensional design problems and a “single-letter” characterization is one where the solution is reducable to a finite dimensional optimization problem. While such characterizations are powerful and yield significant insight, it is unclear whether many problems in network information theory admit such a solution. In fact, after almost 40 years of effort, few problems in network information theory have been resolved with such a characterization. We argue that much broader progress can be made when instead one seeks approximate solutions with a guarantee on the gap to optimality. Focusing on the practically important models of linear Gaussian channels and Gaussian sources, our approach consists of three steps: 1) simplify the model 2) obtain optimal solution for the simplified model; 3) translate the optimal scheme and outer bounds back to the original model.

For communicating messages over a noisy network, we develop a deterministic model that focusses on the “interaction” rather than the noise. This simplification allows us to pursue the steps of the program, by simplifying the model, solving it and then translating it to an approximate characterization. This “deterministic approximation” approach has been successfully applied to make progress on many long-standing open problems in network information theory problems. The deterministic model and its application to the approximation of capacity of wireless relay networks have been developed in the paper: Wireless network information flow: a deterministic approach

For network data compression problems, we simplify by replacing the lossy distortion criterion to lossless one. This allows us to gain insight into the network data compression problem and obtain an approximation to the original problem. This was first developed for the multiple description data compression problem in the paper Approximating the Gaussian Multiple Description Rate Region Under Symmetric Distortion.

Using this approach, progress has already been made on several other long-standing open problems. A partial list of our work on these topics is given below. Also look at David Tse's page for more results on this topic.

Papers

  1. Abstract:
    In this paper we study two-stage Gaussian relay-interference networks where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. Our main result is an approximate characterization of the capacity region for such networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals.
  2. Abstract:
    This paper approximately resolves the information flow over wireless (Gaussian) relay networks to within a constant number of bits. It introduced the linear deterministic model and established a max-flow min-cut result for linear deterministic networks. The insights from the deterministic approach led to the approximate max-flow min-cut characterization for noisy Gaussian networks, through the introduction of a new relaying strategy called quantize-map-forward (QMF).
  3. Abstract:
    We show that source-channel separation is approximately optimal for transmitting a Gaussian source over a bandwidth mismatched Gaussian channel, for quadratic distortion measures. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.
  4. Download: asymmd.pdf on Arxiv 
    Abstract:
    This paper introduces the asymmetric multi-level lossless data compression problem and gives a complete characterization for the three-description version. It then uses insights from this characterization to provide an approximate characterization for the 3-description asymmetric multiple description problem.
  5. Abstract:
    Approximately solves symmetric Gaussian multiple description problem to within a bit, by sandwiching the MD rate region between two polytopes separated by at most a fraction of a bit.
  6. Download: tcdsspcom10.pdf 
    Abstract:
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, and the channels in this network are synchronized, orthogonal and memoryless (i.e., noisy graphs).
  7. Download: od_isit10.pdf on Arxiv 
    Abstract:
    An approximate max-flow min-cut result for arbitrary wireless relay network was recently established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays. This also extended the original scalar quantizer analysis to vector quantizers and obtained a slightly better approximation constant.
  8. C. Tian, J. Chen, S. N. Diggavi, and S. Shamai, "Optimality and approximate optimality of source-channel separation in networks," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 495-499.
  9. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  10. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Capacity of Deterministic Z-Chain Relay-Interference Network," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 331-335.
  11. C. Tian, S. N. Diggavi, and S. Shamai, "An Approximate Characterization For the Gaussian Broadcasting Distortion Region," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 2477-2481.
  12. S. Mohajer, S. N. Diggavi, and D. Tse, "Approximate Capacity of a Class of Gaussian Relay-Interference Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 31-35.
  13. Download: pdt_icc09.pdf 
    Abstract:
    We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.
  14. Download: pdtita09final.pdf 
    Abstract:
    This paper studies the idea of noise insertion by authenticated relays through friendly jamming. We develop the secrecy rate achievable in arbitrary (deterministic) networks when there are relays actively helping secrecy.
  15. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Transmission techniques for relay-interference networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2008, pp. 464-474.
  16. S. Avestimehr, S. N. Diggavi, and D N C. Tse, "Approximate characterization of capacity in Gaussian relay networks," in Proc. IEEE International Wireless Communications and Mobile Computing Conference (IWCMC), Crete, Greece, 2008, pp. 56-61.
  17. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Approximate Capacity of Gaussian Relay Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 474-478.
  18. C. Tian, S. Mohajer, and S N. Diggavi, "Approximating the Gaussian multiple description rate region under symmetric distortion constraints," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1413-1417.
  19. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1992-1996.
  20. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Information flow over compound wireless relay networks," in Proc. IEEE Zurich Seminar on Communications (IZS), Zurich, Switzerland, 2008, p. 92.
  21. C. Tian, S. Mohajer, and S. N. Diggavi, "On the symmetric Gaussian multiple description rate-distortion function," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 412-421.
  22. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Multilevel Diversity Coding," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 402-411.
  23. C. Tian, S. Mohajer, and S. N. Diggavi, "On the Gaussian $K$-description problem under symmetric distortion constraints," in Proc. Information Theory and Applications Workshop, UCSD, San Diego, California, 2008, pp. 401-406.
  24. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Wireless network information flow," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  25. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A Deterministic Approach to Wireless Relay Networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  26. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A deterministic model for wireless relay networks and its capacity," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 6-11.