Monday, March 7, 2011

PhD Position - University of Twente - Analysis of Algorithms

PhD Position at the University of Twente
========================================

A full-time PhD position is available within the project

Smoothed Analysis of Belief Propagation

in the group Discrete Mathematics and Mathematical Programming (DMMP) at the
Department of Applied Mathematics. The project is funded by Netherlands
Organization for Scientific Research (NWO) and is embedded in the University
of Twente's Centre for Telematics and Information Technology (CTIT), the
largest academic ICT research institute in the Netherlands.

REQUIREMENTS

The successful candidate should have a Master's degree in Mathematics,
Computer Science, Econometrics, or a related field. A solid background in
Discrete Optimization, Theoretical Computer Science, or the Analysis of
Algorithms is highly appreciated but not a must as the candidate will be
given the opportunity to follow courses in the LNMB PhD program during
her/his first year (see www.lnmb.nl).

WHAT WE OFFER

We offer a 4-year research position in a dynamic and international
environment. The salary increases from 2042 Euro in the first year to 2612
in the fourth, plus holiday allowance and end-year bonus. The DMMP group
consists currently consists of 10 faculty members and 13 PhD students and is
headed by Prof. Marc Uetz. Please see www.utwente.nl/ewi/dmmp/ for more
details. The University of Twente provides excellent campus facilities, and
actively supports professional and personal development.

PROJECT DESCRIPTION

Belief propagation is a heuristic approach for solving large-scale
statistical inference problems. It is an easy-to-implement heuristic has
become very popular in a wide range of applications.

Its success in practice, however, is at sharp contrast to the lack of
theoretical understanding of its performance. To provide a more realistic
analysis of algorithms, the concept of smoothed analysis has been developed.
In smoothed analysis, performance is not measured in terms of worst-case
instances. Instead, an adversary specifies an instance, and then the
expected performance is measured when this instance is slightly randomly
perturbed. Smoothed analysis takes into account that practical data is often
noisy, e.g., due to measurement errors.

The aim of this project is smoothed analysis of belief propagation. The goal
is to get a deeper understanding of its performance and to bridge the gap
between theoretical and practical performance of belief propagation.

INFORMATION AND APPLICATION

You are invited to send your application (including curriculum vitae, copies
of certificates, and a letter of motivation) to as well as two letters of
recommendation to the address below. Electronic submissions are highly
encouraged (please attach relevant documents as PDF).

Deadline for applications is March 31, 2011. The letters of recommendation
can be sent after the application, but not later than April 15, 2011. The
intended starting date is late summer 2011.

Please do not hesitate to send any questions to the email given above.

Bodo Manthey
University of Twente
Department of Applied Mathematics
P.O. Box 217
7500 AE Enschede
The Netherlands
Email: b.manthey@utwente.nl
Phone: +31 53 4893385
http://www.math.utwente.nl/~mantheyb/