Department of Computer Science
»
Intelligent Systems Laboratory
»
Algorithms
Algorithms
Team
| [About] | [Latest news] | [Events] | [Members] | [Projects] | [Publications] | [Contact us] |
About
We look at various aspects of the theory and practice of algorithms, in partucular in the context of pattern matching. The goal of our research is both to provide scalable solutions to existing problems and to understand the limits of what is possible. The quantity of data available in digital form continues to increase at an exponential rate. The need for faster and more accurate algorithms is now more important than ever before. We also want to understand where improvements are impossible by establishing provable lower bounds, both in terms of space and time. We are now a part of the Intelligent Systems Laboratory.
"People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically."
— Donald Knuth
Current interests
| Approximate string matching | Time and space lower bounds | Complexity theory |
| Realtime and online algorithms | Randomised algorithms | Counting complexity |
| Data streaming algorithms | Approximation algorithms | Constraint satisfaction problems |
| Algorithms for dynamically changing data | External memory data structures |
Latest news
For accepted papers, see publications section.
| January 2013 | Two postdoc positions available. Deadline 6 Feb 2013. Please also feel free to email Raphaël Clifford directly if you are interested in working in algorithms and/or lower bounds at Bristol. |
| 7 January 2013 | Talk by Markus Jalsenius at SODA'13 in New Orleans. The paper is Tight Cell-Probe Bounds for Online Hamming Distance Computation and these are the slides. |
| 6 November 2012 | Markus Jalsenius is giving a departmental seminar at the University of Liverpool on the topic of lower bounds for streaming problems. |
| October 2012 | Talk (by Raphaël Clifford) at Oxford Algorithms Instauration: Lower bounds for streaming problems. |
| October 2012 | New Lecturer job advertised. Deadline passed on November 21, 2012. |
| Feb-Aug 2012 | Raphaël Clifford visiting CSE department at University of Washington. |
Some older news
| April 2010 | All the Best Games May Be NP-Hard: a Slashdot post on Flood-It. Also see the Bristol University press release. |
Events
Over the past years there have been a series of successful EPSRC funded workshops, known as Bristol Algorithms Days (BAD), with the aim of exploring new collaborative research programmes at the interface between mathematics and computer science.
- Bristol Algorithms Days 2010
- Bristol Algorithms Days 2009
- Bristol Algorithms Days 2008 (poster)
- Bristol Algorithms Days 2007
In 2008 we hosted the Bristol Summer School on Probabilistic Techniques in Computer Science.
Members
 Raphaël Clifford Reader
|
 Markus Jalsenius Postdoctoral Researcher
|
 Leon Atkins PhD Student
|
 Benjamin Sach Visiting Fellow (only occasionally at Bristol)
|
Previous members
 Aram Harrow University of Washington
|
 Ashley Montanaro University of Cambridge
|
 Igor Nor HP Labs
|
 Alexandru Popa University of Aalto
|
Research projects
Here are examples of funded research projects.
Current research grants
- EPSRC fellowship awarded to Raphael Clifford for "Next generation pattern matching" (Oct 2012--Sept 2017). EP/J019283/1.
- EPSRC grant for "Dynamic pattern matching: Faster Algorithms and New Bounds". (Jan 2012--Dec 2014). EP/J011940/1 (PI Raphaël Clifford).
Past research grants
Recent publications
Publications from 2005 to present day co-authored by current members of the Algorithms team whilst at Bristol. For other publications from past or visiting members, please see their respective web pages.| Preprints |
| Sliding windows with limited storage [ arXiv ] Paul Beame, Raphaël Clifford, and Widad Machmouchi Preprint (submitted). |
| To appear |
| Pattern matching under polynomial transformation [ arXiv ] A. Butman, P. Clifford, R. Clifford, M. Jalsenius, N. Lewenstein, B. Porat, E. Porat, and B. Sach To appear in SIAM Journal on Computing. |
| Parameterized matching in the streaming model [ arXiv ] Markus Jalsenius, Benny Porat, and Benjamin Sach To appear in STACS 2013. |
| Space lower bounds for online pattern matching [ arXiv ] Raphaël Clifford, Markus Jalsenius, Ely Porat, and Benjamin Sach To appear in Theoretical Computer Science. |
| The complexity of approximating bounded-degree Boolean #CSP [ arXiv ] M. Dyer, L. A. Goldberg, M. Jalsenius, and D. Richerby To appear in Information and Computation. |
| 2013 |
| Tight cell-probe bounds for online hamming distance computation [ arXiv ] Raphaël Clifford, Markus Jalsenius, and Benjamin Sach In SODA '13: Proc. 24th ACM-SIAM Symp. on Discrete Algorithms, 2013. |
| 2012 |
| Pattern matching in multiple streams [ arXiv ] Raphaël Clifford, Markus Jalsenius, Ely Porat, and Benjamin Sach In CPM '12: Proc. 23nd Annual Symp. on Combinatorial Pattern Matching, pages 97–109, 2012. |
| Mismatch sampling [ PDF ] Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat, and Amir Rothschild Information and Computation, 214:112–118, 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. |
| Sampling colourings of the triangular lattice [ arXiv ] Markus Jalsenius Random Structures & Algorithms, 40(4):501–533, 2012. |
| The complexity of flood filling games [ arXiv ] Raphaël Clifford, Markus Jalsenius, Ashley Montanaro, and Benjamin Sach Theory of Computing Systems, 50(1):79–92, 2012. |
| 2011 |
| Speed scaling to manage temperature [ PDF ] L. Atkins, G. Aupy, D. Cole, and K. Pruhs Theory and Practice of Algorithms in (Computer) Systems, pages 9–20, 2011. |
| Restricted common superstring and restricted common supersequence [ arXiv ] Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein, and Alexandru Popa In CPM '11: Proc. 22nd Annual Symp. on Combinatorial Pattern Matching, pages 467–478, 2011. |
| Space lower bounds for online pattern matching [ arXiv ] Raphaël Clifford, Markus Jalsenius, Ely Porat, and Benjamin Sach In CPM '11: Proc. 22nd Annual Symp. on Combinatorial Pattern Matching, pages 184–196, 2011. |
| Lower bounds for online integer multiplication and convolution in the cell-probe model [ arXiv ] Raphaël Clifford and Markus Jalsenius In ICALP '11: Proc. 28th International Colloquium on Automata, Languages and Programming, pages 593–604, 2011. |
| Pattern matching in pseudo real-time [ PDF ] Raphaël Clifford and Benjamin Sach Journal of Discrete Algorithms, 9(1):67–81, 2011. |
| A black box for online approximate pattern matching [ PDF ] Raphaël Clifford, Klim Efremenko, Benny Porat, and Ely Porat Information and Computation, 209(4):731–736, 2011. |
| Maximum subset intersection Raphaël Clifford and Alexandru Popa Information Processing Letters, 111(7):323–325, 2011. |
| 2010 |
| The complexity of approximating bounded-degree Boolean #CSP [ arXiv ] Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, and David Richerby In STACS '10: Proc. 27th Annual Symp. on Theoretical Aspects of Computer Science, pages 323–334, 2010. |
| Permuted function matching [ PDF ] Raphaël Clifford and Benjamin Sach Information Processing Letters, 110(22):1012–1015, 2010. |
| The complexity of flood filling games [ arXiv ] David Arthur, Raphaël Clifford, Markus Jalsenius, Ashley Montanaro, and Benjamin Sach In FUN '10: Proc. 5th International Conference on Fun with Algorithms, pages 307–318, 2010. |
| Pseudo-realtime pattern matching: Closing the gap Raphaël Clifford and Benjamin Sach In CPM '10: Proc. 21st Annual Symp. on Combinatorial Pattern Matching, pages 101–111, 2010. |
| Pattern matching with don't cares and few errors [ PDF ] Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild Journal of Computer System Sciences, 76(2):115–124, 2010. |
| A filtering algorithm for k-mismatch with don't cares [ PDF ] Raphaël Clifford and Ely Porat Information Processing Letters, 110(22):1021–1025, 2010. |
| (In)approximability results for pattern matching problems Raphaël Clifford and Alexandru Popa In Prague Stringology Conference (PSC), pages 52–62, 2010. |
| 2009 |
| Online approximate matching with non-local distances Raphaël Clifford and Benjamin Sach In CPM '09: Proc. 20th Annual Symp. on Combinatorial Pattern Matching, pages 142–153, 2009. |
| From coding theory to efficient pattern matching [ PDF ] Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild In SODA '09: Proc. 20th ACM-SIAM Symp. on Discrete Algorithms, pages 778–784, 2009. |
| Generalised matching [ PDF ] Raphaël Clifford, Aram Wettroth Harrow, Alexandru Popa, and Benjamin Sach In SPIRE '09: Proc. 16th International Symp. on String Processing and Information Retrieval, pages 295–301, 2009. |
| 2008 |
| Mismatch sampling Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat, and Amir Rothschild In SPIRE '08: Proc. 15th International Symp. on String Processing and Information Retrieval, pages 99–108, 2008. |
| An empirical study of cache-oblivious priority queues and their application to the shortest path problem [ arXiv ] Benjamin Sach and Raphaël Clifford arXiv, 2008. Preprint. |
| A black box for online approximate pattern matching Raphaël Clifford, Klim Efremenko, Benny Porat, and Ely Porat In CPM '08: Proc. 19th Annual Symp. on Combinatorial Pattern Matching, pages 143–151, 2008. |
| Scheduling algorithms for procrastinators [ arXiv ] Michael A. Bender, Raphaël Clifford, and Kostas Tsichlas Journal of Scheduling, 11(2):95–104, 2008. |
| Necklace swap problem for rhythmic similarity measures Y. Ardila, R. Clifford, C. S. Iliopoulos, G. M. Landau, and M. Mohamed International Journal of Computational Methods, 5(3):1–13, 2008. |
| 2007 |
| k-mismatch with don't cares Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild In ESA '07: Proc. 15th Annual European Symp. on Algorithms, pages 151–162, 2007. |
| Fast approximate point set matching for information retrieval Raphaël Clifford and Benjamin Sach In SOFSEM '07: Proc. 33rd Conference on Current Trends in Theory and Practice of Computer Science, pages 212–223, 2007. |
| Self-normalised distance with don't cares Peter Clifford and Raphaël Clifford In CPM '07: Proc. 18th Annual Symp. on Combinatorial Pattern Matching, pages 63–70, 2007. |
| A filtering algorithm for k-mismatch with don't cares Raphaël Clifford and Ely Porat In SPIRE '07: Proc. 14th International Symp. on String Processing and Information Retrieval, pages 130–136, 2007. |
| Simple deterministic wildcard matching Peter Clifford and Raphaël Clifford Information Processing Letters, 101(2):53–54, 2007. |
| 2006 |
| A fast, randomised, maximal subset matching algorithm for document-level music retrieval Raphaël Clifford, M. Christodoulakis, T. Crawford, D. Meredith, and G. Wiggins In ISMIR '06: Proc. 7th International Conference on Music Information Retrieval, pages 150–155, 2006. |
| Algorithms on extended (δ, γ)-matching Inbok Lee, Raphaël Clifford, and Sung-Ryul Kim In ICCSA'06: International Conference on Computational Science and its Applications, number 3, pages 1137–1142, 2006. |
| 2005 |
| Faster algorithms for δ,γ-matching and related problems Peter Clifford, Raphaël Clifford, and C.S. Iliopoulos In CPM '05: Proc. 16th Annual Symp. on Combinatorial Pattern Matching, pages 68–78, 2005. |
| Music retrieval algorithms for the lead sheet problem Raphaël Clifford, R. Groult, C. Iliopoulos, and R. Byrd Journal of New Music Research, 34(4):311–317, 2005. |
| Distributed suffix trees Raphaël Clifford Journal of Discrete Algorithms, 3(2–4):176–197, 2005. |
| Necklace swap problem for rhythmic similarity measures Y. Ardila, R. Clifford, and M. Mohamed In SPIRE '05: Proc. 12th International Symp. on String Processing and Information Retrieval, pages 234–245, 2005. |
Contact us
For contact details, click on the name of the member you wish to contact.