Markus Jalsenius
Department of Computer Science
Room 3.37, Merchant Venturers Building
University of Bristol, Bristol, BS8 1UB

I am a Research Associate in the Algorithms Team in the Department of Computer Science at the University of Bristol. I am also lecturing several courses (see below).

Research

I have a wide range of research interests where over the past years focus has shifted from complexity to algorithms, and is now somwhere that could be described as "in between" the two, namely lower bounds.

I am currently researching pattern matching problems and string algorithms, both in an offline and streaming setting. For streaming, we are given a fixed pattern and a text of which characters arrive one at a time. The task is to report the distance between the pattern and the last symbols of the text as quickly as possible before the next symbol arrives. The difficulty of this task depends greatly on how we define the distance between two strings. In addition to finding fast unamortised solutions, I am particularly interested in establishing bounds on how efficiently these problems can be solved, that is finding provable time and space lower bound. An example can be found in a paper from 2011 (arXiv) where we show a logarithmic time lower bound for two fundamental problems: computing the inner product between a fixed vector and a stream, and online multiplication (digits arrive in pairs and the corresponding digit in the product is to be outputted). Another more recent example is that of computing the Hamming distance between a fixed string and the last symbols of a stream. Here we also provide a logarithmic time lower bound (arXiv).

During my PhD, which I obtained from the University of Liverpool in 2008 under the supervision of 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 had a postdoc position in Liverpool 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. Main collaborators include Leslie Ann Goldberg, Martin Dyer and Mark Jerrum.

Other

On the Programme Committee for

Teaching

I lecture the following courses.

2013/14

2012/13

2011/12

2010/11

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

Some example slides

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 probability theory and stochastic processes at Stockholm University. In 2004 I started my PhD at the University of Warwick in the UK. After slightly less than two years I moved with my supervisor Leslie Ann Goldberg to the University of Liverpool, where I finished my PhD in 2008. After my PhD I held a postdoc position at Liverpool. Since 2009 I am a memeber of the Algorithms Team at Bristol.

Publications

For some of the papers that I have presented, there is a link to my slides.
2013
Pattern matching under polynomial transformation [ arXiv ]
A. Butman, P. Clifford, R. Clifford, M. Jalsenius, N. Lewenstein, B. Porat, E. Porat, and B. Sach
SIAM Journal on Computing, 42(2):611–633, 2013.
Space lower bounds for online pattern matching [ arXiv ]
R. Clifford, M. Jalsenius, E. Porat, and B. Sach
Theoretical Computer Science, 483:58–74, 2013.
Parameterized matching in the streaming model [ arXiv ]
Markus Jalsenius, Benny Porat, and Benjamin Sach
In STACS '13: Proc. 30th Annual Symp. on Theoretical Aspects of Computer Science, pages 400–411, 2013.
Tight cell-probe bounds for online hamming distance computation [ arXiv | slides ]
R. Clifford, M. Jalsenius, and B. Sach
In SODA '13: Proc. 24th ACM-SIAM Symp. on Discrete Algorithms, 2013.
2012
The complexity of approximating bounded-degree Boolean #CSP [ arXiv ]
M. Dyer, L. A. Goldberg, M. Jalsenius, and D. Richerby
Information and Computation, 220:1–14, 2012.
Sampling colourings of the triangular lattice [ arXiv ]
M. Jalsenius
Random Structures & Algorithms, 40(4):501–533, 2012.
Pattern matching in multiple streams [ arXiv | slides ]
R. Clifford, M. Jalsenius, E. Porat, and B. Sach
In CPM '12: Proc. 23nd Annual Symp. on Combinatorial Pattern Matching, pages 97–109, 2012.
The complexity of weighted and unweighted #CSP [ arXiv ]
A. Bulatov, M. Dyer, L. A. Goldberg, M. Jalsenius, M. Jerrum, and D. Richerby
Journal of Computer and System Sciences, 78(2):681–688, 2012.
The complexity of flood filling games [ arXiv | slides ]
R. Clifford, M. Jalsenius, A. Montanaro, and B. Sach
Theory of Computing Systems, 50(1):79–92, 2012.
2011
Lower bounds for online integer multiplication and convolution in the cell-probe model [ arXiv | slides ]
R. Clifford and M. Jalsenius
In ICALP '11: Proc. 28th International Colloquium on Automata, Languages and Programming, pages 593–604, 2011.
Space lower bounds for online pattern matching [ arXiv ]
R. Clifford, M. Jalsenius, E. Porat, and B. Sach
In CPM '11: Proc. 22nd Annual Symp. on Combinatorial Pattern Matching, pages 184–196, 2011.
2010
The complexity of approximating bounded-degree Boolean #CSP [ arXiv ]
M. Dyer, L. A. Goldberg, M. Jalsenius, and D. Richerby
In STACS '10: Proc. 27th Annual Symp. on Theoretical Aspects of Computer Science, pages 323–334, 2010.
The complexity of flood filling games [ arXiv | slides ]
D. Arthur, R. Clifford, M. Jalsenius, A. Montanaro, and B. Sach
In FUN '10: Proc. 5th International Conference on Fun with Algorithms, pages 307–318, 2010.
2009
The complexity of weighted Boolean #CSP with mixed signs [ arXiv | slides ]
A. Bulatov, M. Dyer, L. A. Goldberg, M. Jalsenius, and D. Richerby
Theoretical Computer Science, 410(38):3949–3961, 2009.
Strong spatial mixing and rapid mixing with five colours for the Kagome lattice [ arXiv ]
M. Jalsenius
LMS Journal of Computation and Mathematics, 12:195–227, 2009.
2008
A systematic scan for 7-colourings of the grid [ arXiv | slides ]
M. Jalsenius and K. Pedersen
International Journal of Foundations of Computer Science, 19(6):14611477, 2008.
2006
Improved mixing bounds for the anti-ferromagnetic Potts model on Z2 [ arXiv | slides ]
L. A. Goldberg, M. Jalsenius, R. Martin, and M. Paterson
LMS Journal of Computation and Mathematics, 9:1–20, 2006.