Skip to main content

Research of Alexander Tiskin

My main research interests are in the following areas.

String algorithms

My research in the area of string algorithms is concerned with efficient methods of string comparison and approximate string matching, and their surprising connections with computational geometry and algebra. I have developed a novel approach to string comparison, based on a deep connection between the longest common subsequence problem and a certain algebraic structure known as the seaweed monoid. A flavour of this approach is given in this presentation and this book draft. I also collaborate on developing applications of this approach in computational molecular biology, such as the one described in this press release

Parallel computation

My research in the area of parallel computation is concerned with the design and analysis of efficient algorithms and programming techniques for parallel computers, which take account of communication and synchronisation time as scarce resources alongside computation time. For an introduction into the area, see my BSP computation web page, and the Advanced Topics in Algorithms teaching material.

Combinatorial optimisation and graph theory

My research in the areas of combinatorial optimisation and graph theory is concerned with efficient approximation techniques fot the travelling salesman problem, as well as certain combinatorial packing problems. This topic overlaps significantly with the previous topics, as there are some close relationships between string algorithms, parallel algorithms, and algorithms on combinatorial objects and graphs.

For more details on each of the above topics, see my publications.