Romeo wants to send a message to Juliet—a sequence of digits, for example—but the communication channel introduces noise into the signal that alters some of the digits. To ensure that Juliet can understand the information she receives, Romeo must encode his message by adding redundant information. This redundancy allows for the recovery of the original message, so that, if some errors occur due to noise, there is still enough useful information left for Juliet to decode it without losing the original meaning. What is the minimum amount of redundancy that needs to be added? Which technique is most effective (reducing the computation time required) and cost-efficient?
João Ribeiro, professor at Instituto Superior Técnico (Department of Mathematics) and researcher at Instituto de Telecomunicações (IT), received a Starting Grant from the European Research Council (ERC) worth approximately €1.5 million to develop new techniques for studying channels that experience synchronization loss—a specific type of communication error where, for example, some digits may be dropped from the final message, making it difficult to compare it with the initial message. Synchronization loss errors can be found in cutting-edge data storage systems, particularly in DNA data storage systems, a promising solution due to their high density and durability.
“This grant enables me to establish a robust research group in coding and information theory, comprising several PhD students and postdocs, while fostering connections with other leading research groups in this field both within and outside Europe”, says the researcher, who is also a Técnico alumnus (Undergraduate Programme in Applied Mathematics and Computation). His project “focuses on fundamental problems in coding and information theory”, which lie “at the intersection of mathematics, computer science, and electrical engineering”, he notes.
Using the example of communication between Romeo and Juliet, one of the simplest types of errors is known as ‘erasures.’ In an erasure channel, each symbol of the message can be deleted (with a certain probability) and replaced with a ‘?’ symbol. For example, when Romeo sends the message 10101010, Juliet might receive 10?01??0. However, in a deletion channel (in contrast to the erasure channel) the digit is completely removed-instead of being substituted with a ‘?’. Thus, instead of receiving 10?01??0, Juliet would get only 10010.
“This modification, although seemingly innocuous, changes everything – we know very little about the redundancy required to correct deletions, and our methods for protecting information against deletions are still quite primitive compared to what we have developed for erasure channels”, explains João Ribeiro. The main reason for this is that deletions, unlike erasures, result in a loss of synchronization between the sender and the recipient – when Juliet sees the sequence 10010, she has no way of knowing where the first symbol in the original message was positioned.
“Almost all techniques developed over the past 75 years do not work in this scenario”, says the professor, referring to advancements in information theory since its origins in 1948, with the work of Claude Shannon. “The goal of my project is to develop new techniques to study channels with synchronization loss [such as the example mentioned above] and related problems”, incorporating “ideas from algebra, combinatorics, and geometry”, he concludes.
In 2024, Marco Piccardo also received an ERC Starting Grant for research in the field of high-power laser-plasma interactions. In the field of artificial intelligence, André Martins received an ERC Consolidator Grant in 2023. In 2022, Vítor Cardoso won his third ERC grant to study black holes, and Frederico Fiúza returned to Técnico to develop XPACE, with funding from the European Research Council. In 2016, Patrícia Gonçalves received an ERC Starting Grant for her work on hydrodynamic limits and equilibrium fluctuations, and Luís Oliveira e Silva was awarded his second ERC Advanced Grant, becoming the first Portuguese researcher to achieve this feat. In the field of cloud computing, Rodrigo Rodrigues set out in 2012 to address problems that had not yet been systematically considered, which earned him an ERC Starting Grant.