Postdoctoral position at LaBRI & Institut Fourier IDEA ANR PROJECT Identifying Codes for Evolving Graphs

### Post-doc vacancy

A 12-months to 18-months postdoctoral position is available at the LaBRI (Bordeaux, France) and at the Institut Fourier (Grenoble, France).

We are seeking candidates (post-doc) to work on the IDEA ANR project (http://idea.labri.fr/).

### Scientific context

The notion of identifying codes 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).

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.

### Important dates

July 26: application deadline. July 31: notification. September 1st: suggested starting date.

### Salary and benefits

The monthly salary will be around 2000 EUR. This is then subject to income tax.

The post-doc researcher will be affiliated to the French social security system, and will be entitled to unemployment benefit at the end of the contract.

### Requirements

The applicants should hold a Ph.D. or be about to defend their Ph.D. thesis by December 2009.

We are especially interested in candidates with background in one or several of the following fields:

- graph theory - coding theory - algorithms and complexity

Ideally, the post-doc will spend part of his/her time at the LaBRI and part at the Institut Fourier.

Applications should be sent before July 26th, 2009, EXCLUSIVELY by email, to the address

klasing@labri.fr

preferably with the subject containing the words "IDEA Application".

The application must include:

- a detailed resume; - a short research project (1 page), - contact information of two possible references.

Notifications will be sent by email, on July 31st, 2009. The suggested starting date is September 1st, 2009, but later dates may be considered.

For any further information, please refer to the IDEA project homepage: http://idea.labri.fr/

More information:

klasing@labri.fr, raspaud@labri.fr, sylvain.gravier@ujf-grenoble.fr