* Dr. Soren Riis
Department of Computer Science
Queen Mary, University of London
London E1 4NS
UK
*

*Phone: +44 020-7882 7611
Fax: +44 020-7882 3159
Email:smriis@dcs.qmul.ac.uk*

** PhD and Advanced MSc projects **

Algebraic Proof Complexity, Network Coding, Phase Transitions in Randomized Algorithms, Symmetry and Complexity gaps.

Below I include some of my own papers that can serve as an introduction to network coding. This is a new research area that contains many interesting open questions. See also the links to network coding on Ralf Koetter's homepages.

Riis, S., Ahlswede, U. "Problems in Network coding and error correcting codes" , to appear in NetCod the first Workshop on Network Coding, Theory, and Applications , April 2005, Trento, Italy.

Riis, S. "Linear versus non-linear Boolean functions in Network Flow" , appears in the Proceedings of CISS 2004

Riis, S. "Reversible and Irreversible information networks" (submitted)

Riis, S. "Utilising public information in Network Coding" (submitted)

** BSc and MSc projects **

I have desinged a list of ** ODL335 project titles **,
around two themes.

** Theme 1: Routing Strategies in information Networks.**

** (a) Repeated Prisoners dilemma in conflict resolution in Network
communication.**
Consider a communication channel that can only transmit one
message (at a time). Two processors A and B are independent of each other
and have to decide whether to send or delay sending their message. From
the individual processor's perspective there is never any point in
delaying sending its message. However, the system as a whole might very
well benefit from a delay. This type of situation is a typical example of
a "prisoner's dilemma". The task of the project is to analyse the
performance of different strategies for encouraging co-operation among
processors in a network. The project is very open-ended and the student is
expected to work independently. Original ways of stating and analysing the
problem is considered a part of this project. ** Requirements: **
Ability to work independently, flair for research, Good mathematical skills and
ingenuity, willingness to learn and understand issues related to von
Neumann's theory of games.

** (b) Algorithm that calculates network performance.**
In the paper "Network Routing Capacity", IEEE/ACM TRANSACTIONS ON NETWORKING by
J. Cannons, R. Dougherty, C. Freiling, and K. Zeger,
(2004) it has been shown that each flow problem in a
graph has a uniquely determined capacity. It has been shown that the number
is a rational number in the interval (0,1]. The task of this project is to
design an algorithm that
computes the capacity of any a given flow problem. Such an algorithm has
recently been constructed, but it is important that the correctness of
this algorithm is independently verified. Efficiency and the ability to manage
larger graphs is an important feature of the algorithm. A successful algorithm
will bennefit the network research community.
** Requirements:** Ability to work independently, flair for research, Good
mathematical skills, and ingenuity.

** (c) Routing within the wave paradigm (linear Network coding).**
This is a
research project related to a new and very active research area. The task
is to design an Algorithm that for a given network - specified by the user
- finds a linear solution (if such exists). One module of the algorithm
should be able to convert the input - a flow graph - to a system of linear
equations. Another module of the algorithm solves the equations using
linear algebra (Gauss elimination). Finally, the algorithm displays the
appropriate linear functions on the edges contained in the flow graph.
** Requirements: ** Willingness to read and understand the basic ideas in
Network Coding, flair for research, good mathematical skills, and
ingenuity.

** (d) Algorithm for solving multicast problems - Routing within the
paradigm of Network Coding.**
This is a research project related to a new and very
active research area. The task is to design an Algorithm that for a given
network - specified by the user - finds a solution (if such exists). The
algorithm might be based on linear algebra even though there are
alternative designs. Like in project (c), a module of the algorithm
converts the input - a flow graph for a multicast problem - to a system of
linear equations. Another module of the algorithm then solves the
equations using linear algebra (Gauss elimination). Finally, the algorithm
displays the appropriate linear functions on the edges contained in the
flow graph. ** Requirements: ** Willingness to read and understand the
basic ideas in Network coding, flair for research, good mathematical skills,
and ingenuity.

** (e) Algorithm for calculating the monochromatic polynomial in graph
theory.**
The task is to develop an algorithm that for a given graph (the
input), computes the monochromatic polynomial P. In general this task
requires exponential time. However, for smaller graphs that algorithm
should be able to produce the polynomial efficiently. ** Requirements: **
Willingness to read and understand the basic ideas relating to the
monochromatic polynomial, good mathematical skills, and ingenuity.

** (f) Educational tool that demonstrates the basic ideas of Network
Coding. **
The task of this project is to design an educational tool that
illustrates the basic ideas in Network Coding: a new and very active
research area. Emphasis is on the GUI side. ** Requirements: **
Willingness to
read and understand the basic ideas in Network Coding, reasonable
mathematical skills, good ability to communicate ideas in a clearly. Good
programming skills is an advantage.

** (g) Interactive, educational tool that demonstrates the basic ideas of
Network Coding. **
The task of this project is to design an educational tool
that illustrates the basic ideas in Network Coding: a new and very
active research area. Emphasis is on the GUI side. In this project the
tool is expected to include an interactive part that allows the user to
experiment with simple Networks. ** Requirements: ** Willingness to
read and understand the basic ideas in Network Coding, reasonable mathematical
skills, good programming skills.

** Theme 2: High quality play in Games of skill and strategy**

** (a) Bridge program for double dummy play in no trump contracts **
The aim is to design an algorithm that help expert bridge players analyse the
optimal play of the cards (double dummy). The ideal algorithm will be able
to identify and execute squeezes and end-plays. ** Requirements: ** Good
programming skills, good analytic abilities, good problem solving skills,
ability to work independently. Experience in bridge or other competitive
games is an advantage.

** (b) When to double in backgammon. **
Backgammon is one of the few games of
skill where methods of AI have been very successful in achieving a very
good evaluation function. The task is it to take this achievement one step
further. An AI module evaluates for a given position the probability of a
win (or the expected score). The search module builds up a search tree and
look a few moves ahead by analysing different outcomes of the combination
of dice rolls. In a given position, the algorithm should be able to list
its evaluation of the expected outcomes for each possible decision.
** Requirements: ** Good programming skills, good analytic abilities,
ability to work independently, good problem solving skills, creativity.
A good understanding of the basic strategies in backgammon is an advantage

** (c) Trading in Monopoly.**
The strategy in the famous game of Monopoly
depends crucially on the number of players. Decisions depend on the players
subgoals. Players might have very different "personalities". Some of the most
complex decisions involve "side trading" when two players negotiate
"swapping ownership of deeds". This project is to design a program that
plays monopoly. The program should be able to play for 1,2,3,4 or 5
players against 0,1,2 etc. human players. The artificial players should be
able to play with various playing styles (safe, risky, principled,
analytic, etc). The most important challenge is that a player (in his/her
turn) might offer other players certain "side deals" that will benefit the
involved player. ** Requirements: ** Good programming skills,
creativity, good
analytic abilities, ability to deal with complex issues, good problem
solving skills.

** (d) Perfect Mill - retrograde analysis.**
This project is an advanced
database project. The idea is to build a database using a technique called
"retrograde analysis" a kind of dynamic programming. The task is to build
a static database that contains an entry for each legitimate position
(possibly by merging symmetric positions into one entry). The database
should contain all positions with, for example, at most 8 pieces (4 of
each colour). The database will contain one entry for each legitimate
position, and the entry will specify exactly what is the outcome (e.g.
white wins in 23 moves) if both players play optimally. In the final
interface it should be possible to play the program. In each position it
should provide a list of all legitimate moves together with an evaluation
of the moves. ** Requirements:** Good programming skills,
good understanding of (static) databases, good analytic abilities,
good problem solving skills.

** (e) Yatzy. **
One or more persons play one or more artificial opponents. The
aim of the project is to build a program that can make a rough estimate of
the prospects of a given Yatzy position. Given a position (specific
values, possible, certain entries cancelled) the program should contain
a valuation module that is able to give a rough estimate of the
probability of a final score of p or more points to be achieved. Based on
the evaluation module the programme should be able to estimate the
expected outcome of different decisions. ** Requirements: **
Good programming
skills, good analytic abilities, good problem solving skills, creativity,
good understanding of probability theory.

** (f) Othello. **
The task is to produce an algorithm that plays high quality
Othello. Most naive programs for this game tend to play very poorly
because they - mistakenly - try to be at the lead early in game. Against a
good opponent this greedy strategy usually backfires, and the situation,
literally speaking, gets turned around during the last 10-15 moves of the
game. The task of this project is to develop an algorithm that uses a good
evaluation function, combined with a good search algorithm.
** Requirements: **
Good programming skills, good analytic abilities, good engineering skills,
creativity, good problem solving skills, good experience, and skill in
games of strategy is an advantage.

** (g) Master mind as von Neuman game. ** This project contains an
element that is somewhat more theoretical than some of the other
"games projects". The
program should be able to play the game. In a deep sense this game
should be analysed as a von Neuman game where the players optimal
strategies are mixed strategies. It is not feasible to analyse the game
completely since the number of pure strategies is far too high to be
handled in practice. The task is to make certain slight simplifications,
and analyse the game as a von Neuman game. ** Requirements: ** Good
mathematical skills, familiarity with linear algebra, willingness to learn
and understand von Neumann's theory of games.

Other games that contains important challenges include: "Poker (7 card stud)", "Tool for analysis for a bidding system in bridge", and "Go on a 13 x 13 board".