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.