[Research] | [Teaching] | [Other] | [Biography] | [Publications] |
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.
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.
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):1461–1477, 2008. |
2006 |
Improved mixing bounds for the anti-ferromagnetic Potts model on
Z^{2} [ arXiv |
slides ]
L. A. Goldberg, M. Jalsenius, R. Martin, and M. Paterson LMS Journal of Computation and Mathematics, 9:1–20, 2006. |