I am a postdoc in the Algorithms group in the Department of Computer Science at the University of Bristol. I am also the instructor of several courses (see below).


Research

I am researching pattern matching problems and string algorithms, both in an offline and streaming setting. For streaming, we are given a pattern and a streaming text that arrives one character at a time. The task is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. The complexity of this task depends greatly on how we define the distance between two strings. I am interested in finding fast unamortised solutions as well as proving time and space lower bounds for such problems.

During my PhD, which I obtained from the University of Liverpool in 2008 under the supervision of Prof. Leslie Ann Goldberg, I was researching the efficiency of Markov chain simulations for sampling combinatorial structures, in particular graph colourings and so called spin configurations. For example, consider a Markov chain whose state space is the set of proper q-colourings of a graph, and whose stationary distribution is uniform. The goal is to determine how long to simulate the Markov chain in order to be near the stationary distribution. Related to sampling is counting; an efficient method for sampling can be used for efficient counting (the number of proper colourings, for example).

After my PhD, I stayed in Liverpool for a postdoc position on the complexity of counting in constraint satisfaction problems (CSPs). Constraint Satisfaction provides a general framework for modelling decision problems, where 3-SAT is one classic example. I was researching the complexity of counting the number of satisfying solutions for CSPs, where the overall goal was to classify CSPs according to complexity, giving a characterisation for which CSPs are tractable.


Teaching

I lecture the following courses.

2011/12:

2010/11:

Previously, I have been tutoring courses in algorithms at both the University of Liverpool and the University of Warwick.


Biography

I grew up in Stockholm, Sweden, and have a MSc in Computer Science and Engineering from the Royal Institute of Technology (KTH) in Stockholm. During my studies, I spent one year at the University of California, Irvine. In between my MSc and PhD, I worked for Cap Gemini Ernst & Young, and studied bioinformatics at McGill University in Montreal, Canada, as well as a few courses on probability theory, stochastic processes and statistics at Stockholm University. I started my PhD at the University of Warwick in the UK, but after slightly less than two years, I moved with my supervisor Prof. Leslie Ann Goldberg to the University of Liverpool.


Publications


Last modified: 26 April 2012