DS0704 - Fondements du numérique

Complexity and bidirectional information-theory: complexity-feedback-performance limits and a new class of ecological information networks – ECOLOGICAL-BITS-AND-FLOPS

Complexity And Bidirectional Information-Theory: Complexity-Feedback-Performance Limits And A New Class Of Ecological Information Networks

Current efforts in telecommunications research have encountered two seemingly insurmountable bottlenecks; the bottleneck of computational complexity corresponding to the need for algorithms that require extreme computing resources, and the bottleneck of feedback corresponding to the need for equally idealistic feedback mechanisms that must disseminate massive amounts of overhead information about the fluctuating states of each link in the network.

We will provide a never-before-attempted exploration of the crucial interdependencies between computational complexity, feedback and performance in wireless communications.

They also drive our technological vision: We will develop algorithms for a new class of mobile-user devices that can participate in properly gathering/disseminating feedback (at the right place and time) as well as in computing solutions to outsourced algorithmic tasks across the network, in an effort which we term as “outsourcing the surgical insertion of bidirectional bits and flops across the network” and which aims to reduce computational complexity and improve performance.<br />We will take a novel approach, which drives our vision. A recent result of ours has revealed the surprising fact that – for a simple point-to-point setting – a single bit of feedback from the receiver back to the transmitter (properly placed in time, and properly representing the predicted flop count), managed to massively reduce the computational complexity of transceiver algorithms. This reduction was a surprising finding, and it was traced back to the newly-found ability of feedback to `skew’ the statistics of the accumulation of computational load, without negatively skewing the statistics defining performance.

We will expand this idea to networks with more than one pair of nodes, with different topologies and different users that assist in the computations of the network. In the process we will explore uncharted territory by addressing questions such as: How should this feedback (timing, location, message) change in interference channels with interesting topologies, or even larger (or massive) MIMO broadcast channels? What happens if feedback is abstracted to involve an interactive back-and-forth between `transmitters’ and `receivers’? What would be the best way to surgically distribute feedback bits across the network users, in order to reduce computational cost, while maintaining or even improving performance?

Naturally these key ideas – just like computational complexity, feedback and performance – are intertwined, and will be explored jointly. Finding the crucial and largely-unexplored complexity-feedback-performance interdependencies, will offer guiding principles for merging fog (decentralized) and cloud (centralized) ideas, towards hybrid solutions that better traverse the complexity-feedback-performance triangle by surgically inserting bidirectional bits and flops across the network nodes.

1.3.1 Foundational nature
Our proposal is of a foundational nature, as it seeks to explore the elusive complexity-feedback-performance triangle. This effort is supported by our recent breakthroughs, and is motivated by the urgent need to handle the complexity and feedback bottlenecks. Our approach is foundational also because it attacks this problem at its roots, by employing fundamental measures, and by exploring the very core stochastic properties and links between these three parameters. Finally our approach is foundational is it seeks universal solutions; after all, information theory and (computational) complexity theory do exactly that – they offer bounds that go beyond the different specific algorithms, and rather describe the (performance and complexity) limits of the problem itself.
1.3.2 Theoretical novelties
In terms of theory, our research is novel as it seeks to promote a long overdue marriage between information theory and complexity theory of computation. This marriage finds its roots in the common stochastic nature of performance (information theory) and of the nature of accumulation of computational cost. To address this effort, we will draw from our expertise in large deviations, which has allowed us to asymptotically combine different aspects, such as in [Elia-KEJ09] where high-rate finite-duration information theory met finite-duration high-flow queueing theory. This asymptotic approach can also facilitate another novelty; that of comparing, contrasting and partly fusing different promising new visions of network architectures.
1.3.3 Practical novelties
The project offers several practical novelties that include:
• The idea to use feedback to reduce complexity in multi-node networks, rather than improve performance.
• The idea of extending ARQ to be a function of the flop count, rather than of projected performance.
• The idea of using back-and-forth type feedback, in multi-node networks.

Means for dissemination and valorization
Valorization will be academic, regulatory and industrial.
? Academic direction for valorization: Emphasis will be given on strengthening the PI’s and the students’ competences, increasing their international reputation and networks, amelioration of master and PhD programs, jointly solving long-standing open problems, and publications in prestigious journals, conferences, and Ph.D. theses, over a broad range of topics.
? Regulatory direction for valorization and exploitation: Impact will be further maximized by capitalizing on the fact that EURECOM is a member of ETSI. We will seek to promote, in standardization authorities, innovative concepts on novel communication network concepts. The partners will constantly be on alert for patentable outcomes.
? Industrial direction for valorization, and potential technological fallout: Special attention will be given in transforming the project into a breeding ground for setting up further projects, as well as to potentially enable the applicability in commercial equipment. We will also seek for exploitation of the project results and IP it develops via industrial partners in European projects, and in private partnerships.

Wireless communications are currently exhibiting a giant leap in volume and societal impact, but are also facing a massive environmental challenge in the form of a carbon footprint that matches that of global aviation, and which will triple by 2020. This challenge has spurred worldwide research to produce radically new power-efficient high-performance environmentally-friendly communication technologies. However, the efforts have encountered two seemingly insurmountable bottlenecks; the bottleneck of computational complexity corresponding to the need for algorithms that require extreme computing resources, and the bottleneck of feedback corresponding to the need for equally idealistic feedback mechanisms that must disseminate massive amounts of overhead information about the fluctuating states of each link in the network.

These bottlenecks drive our theoretical vision: We will provide a never-before-attempted exploration of the crucial interdependencies between computational complexity, feedback and performance in wireless communications. They also drive our technological vision: We will develop algorithms for a new class of mobile-user devices that can participate in properly gathering/disseminating feedback (at the right place and time) as well as in computing solutions to outsourced algorithmic tasks across the network, in an effort which we term as “outsourcing the surgical insertion of bidirectional bits and flops across the network” and which aims to reduce computational complexity and improve performance.

We will take a novel approach, which drives our vision. A recent result of ours has revealed the surprising fact that – for a simple point-to-point setting – a single bit of feedback from the receiver back to the transmitter (properly placed in time, and properly representing the predicted flop count), managed to massively reduce the computational complexity of transceiver algorithms. This reduction was a surprising finding, and it was traced back to the newly-found ability of feedback to `skew’ the statistics of the accumulation of computational load, without negatively skewing the statistics defining performance.

We will expand this idea to networks with more than one pair of nodes, with different topologies and different users that assist in the computations of the network. In the process we will explore uncharted territory by addressing questions such as: How should this feedback (timing, location, message) change in interference channels with interesting topologies, or even larger (or massive) MIMO broadcast channels? What happens if feedback is abstracted to involve an interactive back-and-forth between `transmitters’ and `receivers’? What would be the best way to surgically distribute feedback bits across the network users, in order to reduce computational cost, while maintaining or even improving performance?
What if then we took this same idea, and turned it around so that the roles of feedback and complexity are reversed, and now instead of surgically inserting feedback bits to reduce complexity, we carefully inserted flops (computational capabilities across the users) to reduce the need for feedback?

Naturally these key ideas – just like computational complexity, feedback and performance – are intertwined, and will be explored jointly. Finding the crucial and largely-unexplored complexity-feedback-performance interdependencies, will offer guiding principles for merging fog (decentralized) and cloud (centralized) ideas, towards hybrid solutions that better traverse the complexity-feedback-performance triangle by surgically inserting bidirectional bits and flops across the network nodes.

Project coordination

Petros Elia (EURECOM)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

EURECOM

Help of the ANR 306,652 euros
Beginning and duration of the scientific project: September 2015 - 42 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter