I am an EPSRC Postdoctoral Research Fellow in the Department of Computer Science at the University of Warwick. I am also affiliated with the DIMAP group. Before this I completed my PhD at the University of Bristol where I am now also a visiting research fellow. My PhD was completed in the Algorithms group under the supervision of Raphaël Clifford.

Research interests

I am currently actively researching problems in Combinatorial pattern matching. Particularly, I am interested in both deterministic and randomised pattern matching algorithms in the streaming model as well as lower bound techinques. I am also interested in Combinatorial games, Computational Geometry, Communication Complexity, External memory algorithms and Mathematical puzzles.

Teaching

• (First Term, 2011-2012) Instructor (15 lectures) for Complexity of Algorithms (CS301)
• (Second Term, 2010-2011) Guest Instructor (two lectures) for Advanced Topics in Algorithms (CS341)
• (University of Bristol, 2009-2011) Teaching Assistant for Data Structures and Algorithms (COMS21103)
• (University of Bristol, 2007-2008) Teaching Assistant for Software Engineering (COMS21102)
• (University of Bristol, 2007-2008) Teaching Assistant for Advanced Algorithms (COMSM1402)
• (University of Bristol, 2006-2008) Lab Demonstrator for Introduction to Computer Architecture (COMS12200)

Departmental Involvement

• Organising Commitee for ICALP 2012
• Organiser of DIMAP junior seminar series

Visits and Ongoing Collaboration

• Visiting research fellow at the University of Bristol, UK for ongoing collaboration with Raphaël Clifford and Markus Jalsenius
• (Autumn 2010) Invited visit to the Danish Technical University, hosted by Philip Bille. Resulting ongoing collaboration with Philip Bille, Inge Li Gørtz and Hjalte Wedel Vildhøj.

Publications

Preprints

• Raphaël Clifford, Markus Jalsenius, and Benjamin Sach. Finding Matches in Unlabelled Streams. In: ArXiv and under conference submission
• Ayelet Butman, Peter Clifford, Raphaël Clifford, Markus Jalsenius, Noa Lewenstein, Benny Porat, Ely Porat and Benjamin Sach. Pattern Matching under Polynomial Transformation. In: ArXiv and under journal submission

2012

• Raphaël Clifford, Markus Jalsenius, Ely Porat, and Benjamin Sach. Pattern Matching in Multiple Streams. In CPM 2012, to appear
• Philip Bille, Inge Li Gørtz, Benjamin Sach, and Hjalte Wedel Vildhøj. Time-Space Trade-Offs for Longest Common Extensions. In CPM 2012, to appear
• Raphaël Clifford, Markus Jalsenius, Ashley Montanaro and Benjamin Sach. The Complexity of Flood Filling Games. In: Theory Comput. Syst. 50(1): 72-92 (2012)

2011

• Raphaël Clifford, Markus Jalsenius, Ely Porat, and Benjamin Sach. Space Lower Bounds for Online Pattern Matching. In CPM 2011, June 2011
• Raphaël Clifford and Benjamin Sach. Pattern matching in pseudo real-time. In: CPM'09 special issue of J. Discrete Algorithms 9(1): 67-81 (2011)

2010

• Raphaël Clifford and Benjamin Sach. Permuted Function Matching. In Information Processing Letters 110(22): 1012-1015 (2010)
• Raphaël Clifford and Benjamin Sach. Pseudo-realtime Pattern Matching: Closing the Gap. In: CPM 2010, June 2010
• Dave Arthur, Raphaël Clifford, Markus Jalsenius, Ashley Montanaro and Benjamin Sach. The Complexity of Flood Filling Games. In: FUN 2010, June 2010

2009

• Raphaël Clifford, Aram Harrow, Alexandru Popa and Benjamin Sach. Generalised matching. In: SPIRE 2009, August 2009
• Raphaël Clifford and Benjamin Sach. Online approximate matching with non-local distances. In: CPM 2009, June 2009

2008

• Benjamin Sach and Raphaël Clifford. An Empirical Study of Cache-Oblivious Priority Queues and their Application to the Shortest Path Problem. In: arXiv, arXiv:0802.1026v1, February 2008

2007

• Raphaël Clifford and Benjamin Sach. Fast Approximate Point Set Matching for Information Retrieval. In: SOFSEM 2007, January 2007.