Dept. of Comp. Sci.   »   ISL   »   Algorithms
Theory and Algorithms
Group

About

We are currently advertising for PhD applicants in the general areas of Algorithms and Theory of Computing. Deadline: 5 January 2015. If you have a strong background in computer science and/or mathematics, and are interested in any of our research areas, please follow the link above.

We study various aspects of the theory and practice of algorithms. 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

Latest news

For accepted papers, see publications section.

December 2014 Two postdoctoral positions are available to work on the theory of quantum computation. The job advert is here and the deadline is 25 January 2015. Please contact Ashley Montanaro with any informal enquiries.
December 2014 Ph.D. positions now available in the Theory and Algorithms group. Deadline for applications: 5 January 2015.
September 2014 Welcome to Allyx Fontaine who has joined us from Université Bordeaux 1. She will work as a post-doc on both algorithms and lower bounds.
September 2014 Ashley's talk at the recent Turing Gateway to Mathematics event on post-quantum research is now available.
September 2014 Welcome to Stephen Piddock, who joins the team as a PhD student working on quantum computation.
September 2014 Very pleased to announce that our paper Cell-probe bounds for online edit distance and other pattern matching problems has been accepted at SODA 2015. This paper shows how to prove lower bounds for streaming problems in the bit-probe model for the first time as well as giving a new exponentially faster solution for edit-distance in the cell-probe model.
September 2014 A postdoctoral position in the Algorithms Team is available. The job advert is here and the application deadline is October 13, 2014. Please contact Raphaël Clifford with any informal enquiries.
September 2014 We are very happy to announce that Benjamin Sach has joined the Computer Science department and the Algorithms Team as a new lecturer. This follows the successful completion of his postdoctoral EPSRC fellowship.
Summer 2014 We are pleased to welcome Dom Moylett who has joined us for an EPSRC summer vacation project. He will be implementing pattern matching algorithms for streaming data. He is also writing a blog about his progress.
June 2014 Three lectureship positions in the Computer Science Department available. One 3 year fixed term position in Theory/Algorithms, one permanent position in core computer science and one further 3 year fixed term lectureship in core computer science (follow the previous link). The application deadline is 22 June 2014.
June 2014 Two postdoctoral positions in the theory of quantum computation are available. The job advert is here and the application deadline is 26 June 2014. Please contact Ashley Montanaro with any informal enquiries.
May 2014 Ashley was in Cambridge at the Turing Gateway for Mathematics workshop "Post-Quantum Research - Identifying Future Challenges and Directions", giving a talk titled "The Power of Quantum Computation". The video is available here, and slides are here.
March 2014 New postdoc position available. Application deadline April 30, 2014. Please email Raphael Clifford directly with any informal enquiries. Applicants are strongly advised to explain in their cover letter what interests them about algorithms and/or lower bound research and why they feel they will be able to contribute to these areas.
March 2014 Chancellor George Osborne has announced the foundation of the Alan Turing Institute to research and analyse big data and algorithms. We're very excited about this strong commitment by the government into theoretical computer science in the UK.
February 2014 Benjamin Sach visited Philip Bille, Inge Li Gørtz and Hjalte Wedel Vildhøj at the Danish Technical University in Copenhagen.
January 2014 A guest post by Ashley Montanaro about quantum property testing has appeared on the Property Testing Review blog.

Click to hide older news...

Click to show older news...

November 2013 Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj and Søren Vind visited us from the Danish Technical University. A productive and enjoyable week was had by all.
November 2013 The paper "Complexity Classification of Local Hamiltonian Problems" by Toby Cubitt and Ashley Montanaro has appeared on the arXiv. Ashley will give an invited talk on this work at the Heilbronn Quantum Algorithms Meeting in Cambridge on the 27th November.
October 2013 PhD positions available, see above for details. Feel free to email Raphaël Clifford or Ashley Montanaro directly if you are interested.
October 2013 The paper "A Survey of Quantum Property Testing" by Ashley Montanaro and Ronald de Wolf has appeared on the arXiv.
October 2013 Semester one begins! Ashley will be teaching Data Structures and Algorithms (second year) while Ben and Markus will be teaching Advanced Algorithms (third year). We hope that the students enjoy them.
September 2013 Two postdoc positions available. These are rolling adverts with no fixed deadline. Feel free to email Raphaël Clifford directly if you are interested in working in algorithms and/or lower bounds at Bristol.
September 2013 The workshop New Mathematical Directions for Quantum Information, organised by Ashley Montanaro, is taking place in Cambridge.
August 2013 Congratulations to Dr Leon Atkins who passed his viva today.
July 2013 Welcome to Ashley Montanaro and Benjamin Sach who joined the Algorithms Team.
May 2013 Raphaël Clifford, Markus Jalsenius and Benjamin Sach (currently University of Warwick) visited Joshua Brody at Aarhus University, Denmark. Both Markus and Ben gave talks on recent work - Markus' talk focused on recent work on lower bounds for streaming problems while Ben's talk focused on upper bounds.
April 2013 Two new ex-Bristol appointments to join the Algorithms Team in the Summer of 2013. Ashley Montanaro has been appointed as a Lecturer in Quantum Computing and Benjamin Sach will be rejoining the team as a research fellow, mostly working on lower and upper bounds for streaming problems.
March 2013 Markus Jalsenius is giving a talk at Birkbeck, University of London, on the topic of lower bounds for streaming problems. Slides for the talk can be found here.
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.
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.
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.
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.

In 2008 we hosted the Bristol Summer School on Probabilistic Techniques in Computer Science.

Members


Allyx Fontaine
Researcher

Markus Jalsenius
Researcher

Ashley Montanaro
Lecturer

Stephen Piddock
PhD Student

Benjamin Sach
Lecturer

He Sun
Lecturer
(starting March 2015)

Nicolas Wu
Lecturer
(starting January 2015)

Previous members


Leon Atkins
CHP Consulting

Igor Nor
HP Labs

Alexandru Popa
Masaryk University

Teaching

Research projects

Here are examples of funded research projects.

Current research grants

Past research grants

Recent publications

Publications from 2005 to present day co-authored by current members of the Theory and Algorithms Group whilst at Bristol. For other publications from past or visiting members, please see their respective web pages.
To appear
Quantum algorithms for search with wildcards and combinatorial group testing [ bib | arXiv ]
A. Ambainis and A. Montanaro
To appear in Quantum Information & Computation.
On exact quantum query complexity [ bib | arXiv ]
A. Montanaro, R. Jozsa, and G. Mitchison
To appear in Algorithmica.
A composition theorem for decision tree complexity [ bib | arXiv ]
A. Montanaro
To appear in Chicago Journal of Theoretical Computer Science.
Time-space trade-offs for longest common extensions [ bib | arXiv ]
P. Bille, I. Gørtz, B. Sach, and H. Vildhøj
To appear in Journal of Discrete Algorithms.
2015
Cell-probe bounds for online edit distance and other pattern matching problems [ bib | arXiv ]
R. Clifford, M. Jalsenius, and B. Sach
In SODA '15: Proc. 26th ACM-SIAM Symp. on Discrete Algorithms, 2015.
2013
Element distinctness, frequency moments, and sliding windows [ bib | slides | PDF ]
Paul Beame, Raphaël Clifford, and Widad Machmouchi
FOCS '13: Proc. 54st Annual Symp. Foundations of Computer Science, 2013.
Sparse suffix tree construction in small space [ bib | slides ]
P. Bille, J. Fischer, I. Gørtz, T. Kopelowitz, B. Sach, and H. Vildhøj
In ICALP '13: Proc. 40th International Colloquium on Automata, Languages and Programming, 2013.
Fingerprints in compressed strings [ bib ]
P. Bille, P. Cording, I.Gørtz, B. Sach, H. Vildhøj, and S. Vind
In WADS '13: Proc. 13th Workshop on Algorithms and Data Structures, 2013.
Space lower bounds for online pattern matching [ bib | arXiv | slides ]
R. Clifford, M. Jalsenius, E. Porat, and B. Sach
Theoretical Computer Science, 483:58–74, 2013.
Pattern matching under polynomial transformation [ bib | 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.
Parameterized matching in the streaming model [ bib | arXiv | slides ]
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 [ bib | arXiv | slides ]
Raphaël Clifford, Markus Jalsenius, and Benjamin Sach
In SODA '13: Proc. 24th ACM-SIAM Symp. on Discrete Algorithms, pages 664–674, 2013.
Testing product states, quantum Merlin-Arthur games and tensor optimisation [ bib | arXiv ]
A. Harrow and A. Montanaro
J. ACM, 60(1), 2013.
Weak multiplicativity for random quantum channels [ bib | arXiv ]
A. Montanaro
Communications in Mathematical Physics, 319(2):535–555, 2013.
2012
Time-space trade-offs for longest common extensions [ bib | arXiv ]
P. Bille, I. Gørtz, B. Sach, and H. Vildhøj
In CPM '12: Proc. 23nd Annual Symp. on Combinatorial Pattern Matching, 2012.
The complexity of approximating bounded-degree Boolean #CSP [ bib | arXiv ]
M. Dyer, L. A. Goldberg, M. Jalsenius, and D. Richerby
Information and Computation, 220:1–14, 2012.
Pattern matching in multiple streams [ bib | arXiv | slides ]
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 [ bib | 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 [ bib | 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 [ bib | arXiv ]
Markus Jalsenius
Random Structures & Algorithms, 40(4):501–533, 2012.
The complexity of flood filling games [ bib | arXiv | slides ]
Raphaël Clifford, Markus Jalsenius, Ashley Montanaro, and Benjamin Sach
Theory of Computing Systems, 50(1):79–92, 2012.
The quantum query complexity of learning multilinear polynomials [ bib | arXiv ]
A. Montanaro
Information Processing Letters, 112(11):438–442, 2012.
Some applications of hypercontractive inequalities in quantum information theory [ bib | arXiv ]
A. Montanaro
Journal of Mathematical Physics, 53:122206, 2012.
Almost all decision trees do not allow significant quantum speed-up [ bib | arXiv ]
A. Montanaro
Chicago Journal of Theoretical Computer Science, 2012, 2012.
2011
Speed scaling to manage temperature [ bib | 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 [ bib | 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 [ bib | 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 [ bib | arXiv | slides ]
Raphaël Clifford and Markus Jalsenius
In ICALP '11: Proc. 38th International Colloquium on Automata, Languages and Programming, pages 593–604, 2011.
Pattern matching in pseudo real-time [ bib | PDF ]
Raphaël Clifford and Benjamin Sach
Journal of Discrete Algorithms, 9(1):67–81, 2011.
A black box for online approximate pattern matching [ bib | PDF ]
Raphaël Clifford, Klim Efremenko, Benny Porat, and Ely Porat
Information and Computation, 209(4):731–736, 2011.
Maximum subset intersection [ bib ]
Raphaël Clifford and Alexandru Popa
Information Processing Letters, 111(7):323–325, 2011.
Limitations on quantum dimensionality reduction [ bib | arXiv ]
A. W. Harrow, A. Montanaro, and A. J. Short
In Proc. International Conference on Automata, Languages and Programming 2010 (ICALP'10), pages 86–97, 2011.
A new exponential separation between quantum and classical one-way communication complexity [ bib | arXiv ]
A. Montanaro
Quantum Information and Computation, 11(7&8):574–591, 2011.
2010
The complexity of approximating bounded-degree Boolean #CSP [ bib | 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 [ bib | PDF ]
Raphaël Clifford and Benjamin Sach
Information Processing Letters, 110(22):1012–1015, 2010.
The complexity of flood filling games [ bib | arXiv | slides ]
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 [ bib ]
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 [ bib | 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 [ bib | PDF ]
Raphaël Clifford and Ely Porat
Information Processing Letters, 110(22):1021–1025, 2010.
(In)approximability results for pattern matching problems [ bib ]
Raphaël Clifford and Alexandru Popa
In Prague Stringology Conference (PSC), pages 52–62, 2010.
An efficient test for product states, with applications to quantum Merlin-Arthur games [ bib | arXiv ]
A. Harrow and A. Montanaro
In Proc. Foundations of Computer Science 2010 (FOCS'10), pages 633–642, 2010.
Quantum search with advice [ bib | arXiv ]
A. Montanaro
In Proc. Theory of Quantum Computing 2010 (TQC'10), 2010.
Nonadaptive quantum query complexity [ bib | arXiv ]
A. Montanaro
Information Processing Letters, 110(24):1110–1113, 2010.
Quantum boolean functions [ bib | arXiv ]
A. Montanaro and T. Osborne
Chicago Journal of Theoretical Computer Science, 2010, 2010.
2009
Online approximate matching with non-local distances [ bib ]
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 [ bib | 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 [ bib | 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.
Quantum algorithms for shifted subset problems [ bib | arXiv ]
A. Montanaro
Quantum Information and Computation, 9(5&6):500–512, 2009.
Quantum search of partially ordered sets [ bib | arXiv ]
A. Montanaro
Quantum Information and Computation, 9(7&8):628–647, 2009.
2008
Mismatch sampling [ bib ]
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 [ bib | arXiv ]
Benjamin Sach and Raphaël Clifford
arXiv, 2008. Preprint.
A black box for online approximate pattern matching [ bib ]
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 [ bib | 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 [ bib ]
Y. Ardila, R. Clifford, C. S. Iliopoulos, G. M. Landau, and M. Mohamed
International Journal of Computational Methods, 5(3):1–13, 2008.
A lower bound on the probability of error in quantum state discrimination [ bib | arXiv ]
A. Montanaro
In Proc. IEEE Information Theory Workshop 2008, pages 378–380, 2008.
Unbounded error quantum query complexity [ bib | arXiv ]
A. Montanaro, H. Nishimura, and R. Raymond
In Proc. 19th International Symposium on Algorithms and Computation (ISAAC 2008), 2008.
On the dimension of subspaces with bounded Schmidt rank [ bib | arXiv ]
T. Cubitt, A. Montanaro, and A. Winter
Journal of Mathematical Physics, 49:022107, 2008.
Counterexamples to additivity of minimum output p-Renyi entropy for p close to 0 [ bib | arXiv ]
T. Cubitt, A. W. Harrow, D. Leung, A. Montanaro, and A. Winter
Communications in Mathematical Physics, 284:281–290, 2008.
2007
k-mismatch with don't cares [ bib ]
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 [ bib ]
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 [ bib ]
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 [ bib ]
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 [ bib ]
Peter Clifford and Raphaël Clifford
Information Processing Letters, 101(2):53–54, 2007.
Quantum walks on directed graphs [ bib | arXiv ]
A. Montanaro
Quantum Information and Computation, 7(1):93–102, 2007.
On the distinguishability of random quantum states [ bib | arXiv ]
A. Montanaro
Communications in Mathematical Physics, 273(3):619–636, 2007.
A lower bound on entanglement-assisted quantum communication complexity [ bib | arXiv ]
A. Montanaro and A. Winter
In Proc. International Conference on Automata, Languages and Programming 2007 (ICALP'07), pages 122�–133, 2007.
On the quantum chromatic number of a graph [ bib | arXiv ]
P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, and A. Winter
Electronic Journal of Combinatorics, 14(1), 2007.
2006
A fast, randomised, maximal subset matching algorithm for document-level music retrieval [ bib ]
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 [ bib ]
Inbok Lee, Raphaël Clifford, and Sung-Ryul Kim
In ICCSA'06: International Conference on Computational Science and its Applications, volume 3, pages 1137–1142, 2006.
2005
Faster algorithms for δ,γ-matching and related problems [ bib ]
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 [ bib ]
Raphaël Clifford, R. Groult, C. Iliopoulos, and R. Byrd
Journal of New Music Research, 34(4):311–317, 2005.
Distributed suffix trees [ bib ]
Raphaël Clifford
Journal of Discrete Algorithms, 3(2–4):176–197, 2005.
Necklace swap problem for rhythmic similarity measures [ bib ]
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.