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".