The IDEA Project is organizing a Workshop on Identifying Codes and related concepts in Bordeaux, France from November 21st - 25th 2011.

More information can be found on http://bwic2011.labri.fr.


What is IDEA ?

Combinatorics has studied a number of reconstruction problems. A famous problem is that of determining, among a set of binary vectors, a minimal subset whose sum (exclusive ``or'') equals a given vector. This problem is equivalent to the decoding problem in the theory of error-correcting codes. Consider the analogous problem of reconstructing a set of vectors whose inclusive ``or'' equals a given vector. In set-theoretic terms, we have a family of subsets of an underlying set and we want to reconstruct a collection of subsets from their union. This problem has a number of applications, it is the relevant problem for some watermarking or fingerprinting issues, and also for group testing where individual samples are pooled together and tested for a property and one wishes to recover the samples with the given property. Families of subsets with good reconstruction capabilities are also known as superimposed codes and have been studied by different communities, often independently.

We are interested in the case when the underlying set has an additional structure: it is the vertex set of a given graph. We then have a privileged set of vertices called a code and we consider the subsets of code vertices that are neighbours of some vertex. Again, we want to reconstruct the individual subsets from their union and also to recover the neighbourhood centers.

The code is called an identifying code when it has this reconstruction capability. This problem was introduced by Karpovsky, Chakrabarty and Levitin in 1998 to establish a model for a fault detection problem in multiprocessor systems. One has to exhibit a privileged subset of processors (the identifying code), each privileged processor tests whether there is any faulty processor within its neighbours; depending on the answers of these processors, one must be able to identify the set of faulty processors.

Since 1998, this subject has been actively studied (more than 150 publications). The relationship with the theory of superimposed codes has only recently become apparent, and gives this emerging theory extra perspective and potential for applications. The problem is graph-theoretic in nature, and graph theory is clearly an appropriate tool to tackle it. However, like superimposed coding its likeness to coding problems makes it amenable to coding techniques.

Our aims will include the investigation of dynamic versions of identifying codes. Two directions are considered. First, the input (the graph) is given dynamically and we want to build an efficient identifying code step by step. This approach has not been thoroughly studied before, moreover it is relevant in the context of large scale graphs. Besides, removing or adding vertices or edges also leads to the study of robustness of identifying codes.

The other approach is called adaptive. One can test vertices one after the other, and build the sequence according to the previous answers.

We will be interested in algorithmic, structure and complexity issues. In order to develop some helpful tools for these questions, we will look at static variants and generalized versions of identifying codes.

For example, when the graph is given dynamically, a simple greedy algorithm for building an identifying code may be very inefficient. Therefore, we will propose distributed versions of such algorithms.

Now, only partial results concerning the cardinality of an optimal identifying code in classical structures (grids, hypercubes) are known, we will give the first results on these structures for the adaptive version of identifying codes.



The project?

Meetings

Notices

edit SideBar