Markus Jalsenius
Department of Computer Science
Room 3.36, 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 have also been teaching several courses.

Research

I am currently researching fundamental problems in combinatorial pattern matching, particularly for streaming data. I am interested in both deterministic and randomised solutions, as well as upper and lower bounds.

I have also been researching the complexity of counting in constraint satisfaction problems (CSPs). Constraint Satisfaction provides a general framework for modelling decision problems, such as SAT.

During my PhD studies I was researching the efficiency of Markov chain Monte Carlo methods for sampling combinatorial structures, in particular graph colourings and configurations in spin systems.

Teaching

I have lectured the following courses at the University of Bristol. Before 2010 I was tutoring courses at both the University of Liverpool and the University of Warwick.

Some example slides from my lectures

Other

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. After my MSc I worked for Cap Gemini Ernst & Young and studied bioinformatics at McGill University in Montreal, Canada. In 2004 I started my PhD at the University of Warwick in the UK under the supervision of Leslie Ann Goldberg. When Leslie moved to the University of Liverpool in 2006, I came along. In 2008 I finished my PhD, after which I held a postdoc position at Liverpool. Since 2009 I am a member of the Algorithms Team at Bristol.

Publications

There are links to the slides for some of the papers that I have presented.
Preprints
Cell-probe bounds for online edit distance and other pattern matching problems [ arXiv ]
R. Clifford, M. Jalsenius, and B. Sach
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.