[DMANET] PhD position at ETH, Theory of Combinatorial Algorithms group

The research group "Theory of Combinatorial Algorithms"
<http://www.ti.inf.ethz.ch/ew/index.html> (Komei Fukuda, Bernd Gaertner,
Michael Hoffmann, Jiri Matousek, Emo Welzl) of the Institute of
Theoretical Computer Science at ETH Zurich offers a PhD position. Three
possible topics of study are Satisfiability - Combinatorics and
Algorithms, Unique Sink Orientations (USO) of Cubes, and Crossing-Free
Configurations on Planar Point Sets (see short descriptions below).

Candidates are expected to have a degree in Mathematics or Computer
Science, with emphasis on at least some of algorithms, theoretical
computer science in general, geometry, discrete mathematics and
probability theory.

Applications with CV, names of references, a short letter about
scientific background and interests, and when the candidate wishes to
start the project, should be sent to Emo Welzl <emo@inf.ethz.ch>.
Submission of applications as early as possible is encouraged (before
February 15, 2013). The starting date is flexible.

--------

Satisfiability - Combinatorics and Algorithms: There are a number of
exciting questions about the satisfiability of boolean formulas, even
before touching the issue of exponential versus polynomial complexity.
The working group has achieved a number of contributions on the topic
and wishes to continue this line of research.

Unique Sink Orientations (USO) of Cubes: The object under study here are
USOs, i.e. orientations of the edges of a d-dimensional hypercube where
every face has a unique sink. Such orientations have a surprisingly
strong structure and algorithms for finding the sink (when the cube is
implicitly given by an oracle) have many implications for optimization
algorithms (linear programming, convex programming, linear
complementarity problems, etc.).

Crossing-Free Configurations on Planar Point Sets: The (extremal
combinatorics) question of how many plane spanning cycles (embeddable
with straight edges without crossings) are possible on a planar set of n
points has intrigued researchers for over thirty years now, similarly
for triangulations, plane perfect matchings and spanning trees, etc. On
the algorithmic side, enumerating all such objects or counting them is a
challenging problem, that connects to the convergence of the random flip
process on triangulations. All these questions, despite of recent
progress, are still wide open.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************