Bits and flops: performance and complexity tradeoffs in wireless communications
Computational complexity is generally accepted to be a major limiting bottleneck in wireless communications. On the one hand, optimal solutions often incur prohibitive complexity, and on the other hand, computationally efficient methods often offer abysmal reliability and quality of service.
Understanding this intertwined relationship between communication-performance and computational complexity, entails substantial practical ramifications. One such practical ramification was recently brought to light by one of our latest results. These results show that, in the setting of non-ergodic (outage-limited) MIMO, a single bit of properly placed feedback can, in the presence of a very reasonable number of flops, endow the non-ergodic MIMO setting with near-ergodic reliability and an overall near-ergodic behavior. At the same time though, practical limitations of other forms, may render such solutions inapplicable - hence a long list of open problems that ask how one can utilize a modest amount of flops, to substitute difficult to gather CSIT, in achieving time-limited near-ergodic reliability in non-ergodic communications.
Such open problems relate to finding concise and insightful answers to questions such as:
- What is the complexity price to pay for near-optimal implementation of MIMO, multiuser and cooperative communications?
- How does feedback reduce complexity?
- What policies can regulate complexity at a limited performance loss?
- How do complexity-constraints affect reliability in different MIMO settings?
- How big of a MIMO system (how many transmit antennas or tones or relays or mac users) can your DSP chip sustain?
- How should multiple users behave in the presence of complexity constraints?
- What is the role of antenna selection in reducing complexity?
- What are the cooperative protocols that perform best in the presence of computational constraints?