Since their introduction a decade ago, identifying codes have developed a broad range of connections to both theoretical and applied problems. On the theoretical side, these codes are intimately and deeply linked to locating-dominating sets, super-imposed codes, covering codes, and tilings. On the applied side, researchers (including the PIs) have found fundamental links between identifying codes and important monitoring problems, such as the detection of faults and failures in computer and communication networks, indoor localization, and identification of contaminant sources in the environment. The goal of this research is to properly develop and cultivate the connections between the theory of identifying codes and monitoring applications, thus, contributing to the broader efforts by the research community to develop efficient tools for monitoring the nation's critical infrastructures.
The work entails developing approximation algorithms for identifying code problems, with proven guarantees for arbitrary graphs or graphs of particular relevance to monitoring problems (e.g., geometric and sector random graphs). This is achieved by exploiting connections, recently found by the PIs, between identifying code problems and the well-studied set, multi-set and test covering problems. An important part of the research is to explore sophisticated variants of classical identifying codes, such as source identifying codes, statistical identifying codes, and disjoint identifying codes, which are important for several practical monitoring applications, with an eye towards extending the set covering connections to these new problems. On the educational front, the project involves a unique program, called GreenHack, through which students from local high schools come together with undergraduates engineers at Boston University for a two day workshop and competition around the theme of environmental monitoring and management, in line with the broader goals of the proposed research.
