Bits and flops in modern communications: Analyzing complexity as the missing piece of the wireless-communication puzzle

The tutorial offers an exposition of newly established rigorous relationships between telecommunications-performance and computational-complexity, with emphasis on outage limited high rate MIMO scenarios. We provide exciting new results, and place strong emphasis on future challenges. We argue that complexity is the missing piece of the communication puzzle, and make the point that these challenges strike at the core of the theory and practice of modern wireless communications. The basic premise of the tutorial is that there is an urgent need to develop a unified theory, techniques and algorithms, for analyzing and minimizing the overall implementation complexity of future communication networks, and to decipher and practically achieve the fundamental performance-complexity limits achievable by collectives of communicating nodes. This tutorial comes at a time where recent advances in telecommunications systems have provided powerful communications algorithms that allow for large reductions in transmission power, at the expense though of exponential increases in computational complexity, and consequently in prohibitive increases in algorithmic power consumption. In conjunction with a broad introduction of recent work, the tutorial will reveal future challenges and open problems relating to:

* What is the complexity price to pay for near-optimal implementation of MIMO, multiuser and cooperative communications?

* Why is complexity a bottleneck?

* What are meaningful complexity measures?

* What policies can regulate complexity at a limited performance loss? 

* How does complexity-constraints affect cooperative protocols, what is the best protocol, and how many relays does it involve? 

* How should multiple users behave in the presence of complexity constraints? 

* How big of a chip do you need to cancel interference? 

* How does feedback reduce complexity? 

* How can we convert the non-ergodic MIMO channel to an ergodic channel with one bit of feedback and a few flops? 

The tutorial is designed to attract audience from many branches of communications, while the presented framework can be general enough to attract researchers in areas where performance comes at the expense of non-negligible computational costs. The tutorial will conclude with an open ended exposition of what is involved in broadening the results to communications scenarios other than the outage limited MIMO setting.