PhD scholarships on Constraints @ LSIS (marseille)

PhD scholarships on Constraints

Title: Tractable classes for extending constraint satisfaction solvers

Laboratory: Laboratoire des Sciences de l’Information et des Systèmes (LSIS) – UMR CNRS 6168

Advisors: Philippe Jégou, Cyril Terrioux

Abstract:

The implementation of constraint satisfaction solvers, including SAT solvers for propositional logic (the NP-complete problem of reference), has lead to spectacular results in the last years, proved by their ability to treat industrial instances of huge size. However, the community seems to have reached a plateau that is now difficult to cross.

A significant jump with respect to the current state of the art would likely require the study of two complementary issues:
• The first one is the study of existing solvers, including CDCL-based systems or systems making use of filtering techniques by propagation and exploiting the topological structure of instances, such as bounded tree-width. A theoretical explanation of their practical efficiency is currently lacking. The point here is to develop a theoretical analysis - based on complexity theory (the parameterized complexity seems to be a relevant notion) in order to provide an explanation of their behavior.
• The second issue focuses on integrating tractable fragments handled by the current systems, to the aim of discovering new tractable fragments. These new fragments are intended to cover large classes of benchmarks, and at the same time being suitable for efficient implementation (recognizing and solving algorithms must have an almost linear time complexity).

The thesis will deal with the above issues and will comprise both a theoretical investigation and an experimental analysis.

This research will be undertaken within the TUPLES programme, which is funded by the French National Research Agency (ANR) and it associates four laboratories: namely the IRIT (Toulouse with Martin Cooper and Pierre Régnier), the CRIL (Lens with Pierre Marquis, Lakhdar Saïs, Daniel Le Berre and Bertrand Mazure), the GREYC (Caen with Bruno Zanuttini) and the LSIS (Marseille). TUPLES is the acronym for Tractability for Understanding and Pushing forward the Limits of Efficient Solvers. The applicant will integrate INCA team at LSIS. The INCA team has been ranked A+ (the best possible ranking) by the French National Agency for Evaluation of Research (AERES).

Keyword: CSP, SAT, complexity, algorithmic, tractable classes, solving systems (solvers).

Location: Paul Cézanne University (Aix-Marseille III), Faculty of Sciences and Techniques, Marseille, France

Funding: the Ph.D. fellowship is funded for 3 years and is monthly funded about 1632,22 € before taxes (or 1998,61 € before taxes if included missions other than research activities as teaching) under Decree No. 2009-464 of April 23rd 2009 on doctoral contract of public higher education or research.

Candidate Profile: Applicants should have (or in the process of getting) a M.Sc. in Computer Science, Computer Engineering or a closely-related discipline (such as Discrete Mathematics). Strong algorithmic and mathematical skills are required. C++ or C development skills are desirable. Note that the knowledge of French is not required.

Start date: the position starts preferably in September / October 2011.

Application and contacts: Candidates must send their application before July 1st 2011 midnight, including:
- CV (at most 3 pages)
- Results and ranking for the M.Sc. (join a copy of marks)
- a motivation letter,
- reference letters.
Send your applications by email with attached pdf files to: philippe.jegou@univ-cezanne.fr and cyril.terrioux@univ-cezanne.fr