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.
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.
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.
|Cell-probe bounds for online edit distance and other pattern matching problems [ arXiv ] R. Clifford, M. Jalsenius, and B. Sach To appear in SODA '15: Proc. 26th ACM-SIAM Symp. on Discrete Algorithms.|
|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.|
|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.|
|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.|
|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.|
|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.|
|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.|
|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.|