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

• Advanced Algorithms (COMS31900). Guest lecturing this year.

2011/12

2010/11

• Computational Complexity Theory (COMS30126).

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

#### Some example slides

• Dynamic Programming – 20 minute long introduction to dynamic programming that I gave to undergraduates in January 2013.
• Suffix Arrays – 50 minute long lecture on how to construct suffix arrays (including the DC3 method) and how to use suffix arrays for searching.
• Approximate Pattern Matching – 50 minute long lecture on how to compute the Hamming distance and solve the k-mismatch problem using a combination of fast Fourier transforms and counting.
• Computability – 50 minute long introduction to computational complexity, covering Turing machines, languages, computability and the Halting Problem.

### 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):1461–1477, 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.