[About] | [News] | [Events] | [Members] | [Teaching] | [Projects] | [Publications] |
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 always looking for strong PhD applicants in the general areas of algorithms, lower bounds and the theory of computing.
If you have a strong background in computer science and/or mathematics, and are interested in any of our research areas, please get in touch.
"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
For accepted papers, see publications section.
July 2016 | He Sun will give a talk on spectral sparsification at the Graph Limits and Statistics workshop in Isaac Newton Institute for Mathematical Sciences. |
June 2016 | Ashley Montanaro gave an invited talk at the QCumber workshop in Windsor Park. |
June 2016 | Tatiana Starikovskaya attended the 27th Annual Symposium on Combinatorial Pattern Matching and presented the paper on the longest common substring with approximately k mismatches problem. |
May 2016 | Ashley Montanaro's paper Efficient quantum walk on a quantum processor with Xiaogang Qiang et al appeared in Nature Communications. The press release is here. |
April 2016 | Very pleased to announce that a paper by Raphaël Clifford and Tatiana Starikovskaya Approximate Hamming distance in a stream has been accepted at ICALP 2016. In the paper we consider the problem of computing a (1+ϵ)-approximation of the Hamming distance between a pattern and successive substrings of a stream. We show several communication complexity bounds and then give a streaming algorithm for the problem. Ashley Montanaro and Sam Pallister's paper Quantum algorithms and the finite element method appeared in Physical Review A. |
February 2016 | On Tuesday 9th of February Ashley Montanaro will give a public talk on quantum computing to the South West Futurists group. Ashley also participated in an invitation-only Knowledge Transfer Network innovation workshop on quantum algorithms in finance, London. |
January 2016 | Tania Starikovskaya and Allyx Fontaine attended the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Allyx presented the paper on the k-mismatch problem. |
January 2016 | Laura Mancinska, Ashley Montanaro and Stephen Piddock attended the 19th Conference on Quantum Information Processing QIP 2016, the premier international conference on quantum information. Laura and Ashley both had work accepted for talks: Laura's paper was on a complexity classification of 2-qubit commuting Hamiltonians, while Ashley's was on quantum walk speedup of backtracking algorithms. Stephen presented a poster on the complexity of antiferromagnetic interactions and 2D lattices, and Laura also presented a poster on maximally entangled states in pseudo-telepathy games. |
January 2016 | Ashley Montanaro's invited survey paper Quantum algorithms: an overview has appeared in the new Nature open access journal npj Quantum Information. |
January 2016 | Welcome to Laura Mancinska who joins the group as a Research Associate working on quantum information theory. |
December 2015 | Raphaël Clifford gave a talk [video] on lower bounds and open problems in streams at the Workshop on Computational Complexity of Low-Polynomial Time Problems in Simons Institute for the Theory of Computing. |
November 2015 | The website of Bristol Algorithms Days, workshop on efficient algorithms and lower bounds being held on 2nd and 3rd February 2016, is now available. The poster can be found here. |
October 2015 | Raphaël Clifford and He Sun attended the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), where were presented the papers: "New Unconditional Hardness Results for Dynamic and Online Problems" Raphaël Clifford and Allan Grønlund and Kasper Green Larsen and "Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time" by He Sun and Yin Tat Lee. |
September 2015 | Raphaël Clifford and Benjamin Sach attended the ATI scoping workshop on Statistical and Computational Challenges in Large-Scale Data Analysis, where Ben gave an invited talk with the title “New algorithms for streaming pattern matching”. |
September 2015 |
Tatiana Starikovskaya and Allyx Fontaine attended the 23rd European Symposium on Algorithms, where Tatiana Starikovskaya presented a paper “Dictionary matching in a stream” by E. Porat from U. Bar-Ilan, R. Clifford, A. Fontaine, B. Sach, and T. Starikovskaya.
Tatiana Starikovskaya attended the 22nd the International Symposium on String Processing and Information Retrieval (SPIRE’15), where she gave a talk on computing longest unbordered substrings. Together with Travis Gagie from the University of Helsinki she also organised the 2015 Workshop on Compression, Text and Algorithms. Allyx Fontaine attended the workshop and presented a talk on a paper “The k-mismatch problem revisited” by E. Porat from U. Bar-Ilan, R. Clifford, A. Fontaine, B. Sach, and T. Starikovskaya, which was recently accepted at SODA 2016. |
August 2015 |
Ashley Montanaro and Stephen Piddock attended 15th Asian Quantum Information Science Conference (AQIS’15). Ashley gave an invited talk on quantum speedup of Monte Carlo methods and Stephen presented a talk on the complexity of antiferromagnetic interactions and 2D lattices.
Allyx Fontaine and Tatiana Starikovskaya attended MADALGO summer school on streaming algorithms in Aarhus, Denmark. Allyx presented a poster on k-mismatch streaming pattern matching. Benjamin Sach is visiting the Danish Technical University, Copenhagen, Denmark. |
July 2015 |
He Sun and Luca Zanetti attended the Conference On Learning Theory (COLT’15) in Paris, France. They presented their work on well-clustered graphs partitioning.
Allyx Fontaine and Tatiana Starikovskaya attended the 26th Annual Symposium on Combinatorial Pattern Matching (CPM’15) in Ischia, Italy. Tatiana presented a talk on unbordered factors of strings. |
June 2015 |
Two of our papers have been accepted to FOCS 2015. The first paper is by He Sun and Yin Tat Lee from MIT, who obtained a new world-record algorithm for sparsifying any positive semi-definite matrices. The second paper is by Raphaël Clifford and Allan Grønlund and Kasper Green Larsen from Aarhus university, who showed new unconditional hardness results for matrix-vector multiplication as well as a number of dynamic data structure problems.
Ashley Montanaro and Stephen Piddock attended the 12th Central European Quantum Information Processing Workshop (CEQIP’15) in Telč, Czech Republic. Ashley presented a talk on quantum speedup of Monte Carlo methods and Stephen gave a talk on the complexity of antiferromagnetic qubit interactions and 2D lattices. |
April 2015 | Allyx Fontaine, Raphaël Clifford, Benjamin Sach, Tatiana Starikovskaya, and Luca Zanetti attended Oxford Algorithms Day. |
March 2015 | Welcome to He Sun as a new lecturer who has joined us from the Max-Planck-Institut für Informatik in Saarland. He works on spectral graph theory and algorithms. Welcome also to Luca Zanetti as a new PhD student who will also be working on spectral graph theory. |
January 2015 | Welcome to Nicolas Wu as a new lecturer who has joined us from Oxford University. He is joining the group as our first expert on programming languages. Welcome also to Tatiana Starikovskaya who joins us as a postdoc to work on algorithms and lower bounds. |
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. |
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. |
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.
Links to older versions of units taught by members the group. For current units in CS and Maths follow the links from the relevant departmental home pages.
Here are examples of funded research projects.
To appear |
A survey of quantum property testing [ bib |
arXiv ]
A. Montanaro and R. de Wolf To appear in Theory of Computing Graduate Surveys. |
2016 |
The k-mismatch problem revisited [ bib ]
Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana A. Starikovskaya pages 2039–2052, 2016. |
The k-mismatch problem revisited [ bib ]
Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana A. Starikovskaya In SODA '16: Proc. 27th ACM-SIAM Symp. on Discrete Algorithms, pages 2039–2052, 2016. |
2015 |
Constructing linear-sized spectral sparsification in almost-linear
time [ bib |
arXiv ]
Yin Tat Lee and He Sun arXiv, 2015. Preprint. |
New unconditional hardness results for dynamic and online problems [ bib ]
Raphaël Clifford, Allan Grønlund, and Kasper Green Larsen In FOCS '15: Proc. 56th Annual Symp. Foundations of Computer Science, pages 1089–1107, 2015. |
Quantum reverse hypercontractivity [ bib |
arXiv ]
T. Cubitt, M. Kastoryano, A. Montanaro, and K. Temme arXiv, 2015. Preprint. |
Extremal eigenvalues of local Hamiltonians [ bib |
arXiv ]
A. Harrow and A. Montanaro arXiv, 2015. Preprint. |
On exact quantum query complexity [ bib |
arXiv ]
A. Montanaro, R. Jozsa, and G. Mitchison Algorithmica, 71(4):775–796, 2015. |
Fusion for free - efficient algebraic effect handlers [ bib ]
Nicolas Wu and Tom Schrijvers In MPC '15: Proc. Mathematics of Program Construction - 12th International Conference, pages 302–322, 2015. |
Conjugate hylomorphisms - or: The mother of all structured recursion
schemes [ bib ]
Ralf Hinze, Nicolas Wu, and Jeremy Gibbons In POPL '15: Proc. 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 527–538, 2015. |
Partitioning well-clustered graphs: Spectral clustering works [ bib ]
Richard Peng, He Sun, and Luca Zanetti In COLT '15: Proc. 28th Conference on Learning Theory, pages 1423–1455, 2015. |
A suffix tree or not a suffix tree [ bib ]
Tatiana Starikovskaya and Hjalte Wedel Vildhøj Journal of Discrete Algorithms, 32:14–23, 2015. |
On maximal unbordered factors [ bib ]
Alexander Loptev, Gregory Kucherov, and Tatiana Starikovskaya In CPM '15: Proc. 26nd Annual Symp. on Combinatorial Pattern Matching, pages 343–354, 2015. |
Wavelet trees meet suffix trees [ bib ]
Maxim Babenko, Pawel Gawrychowski, Tomasz Kociumaka, and Tatiana Starikovskaya In SODA '15: Proc. 26th ACM-SIAM Symp. on Discrete Algorithms, pages 572–591, 2015. |
Average-case complexity versus approximate simulation of commuting
quantum computations [ bib |
arXiv ]
Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd arXiv, 2015. Preprint. |
The quantum complexity of approximating the frequency moments [ bib |
arXiv ]
Ashley Montanaro arXiv, 2015. Preprint. |
The complexity of antiferromagnetic interactions and 2d lattices [ bib |
arXiv ]
Stephen Piddock and Ashley Montanaro arXiv, 2015. Preprint. |
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. |
Gossip vs. markov chains, and randomness-efficient rumor spreading [ bib |
arXiv ]
Z. Guo and H. Sun In SODA '15: Proc. 26th ACM-SIAM Symp. on Discrete Algorithms, 2015. |
Dictionary matching in a stream [ bib |
arXiv ]
Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya In ESA '15: Proc. 23rd Annual European Symp. on Algorithms, 2015. In press. |
2014 |
Quantum pattern matching fast on average [ bib |
arXiv ]
A. Montanaro arXiv, 2014. Preprint. |
Quantum algorithms for search with wildcards and combinatorial group
testing [ bib |
arXiv ]
A. Ambainis and A. Montanaro Quantum Information & Computation, 14(5-6):439–453, 2014. |
Time-space trade-offs for longest common extensions [ bib |
arXiv ]
P. Bille, I. Gørtz, B. Sach, and H. Vildhøj Journal of Discrete Algorithms, 25:42–50, 2014. |
Balls into bins via local search: cover time and maximum load [ bib ]
Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, and He Sun In STACS '14: Proc. 31st Annual Symp. on Theoretical Aspects of Computer Science, pages 187–198, 2014. |
Complexity classification of local Hamiltonian problems [ bib |
arXiv ]
T. Cubitt and A. Montanaro In FOCS '14: Proc. 55th Annual Symp. Foundations of Computer Science, pages 120–129, 2014. |
A composition theorem for decision tree complexity [ bib |
arXiv ]
A. Montanaro Chicago Journal of Theoretical Computer Science, 2014(6), 2014. |
2013 |
Element distinctness, frequency moments, and sliding windows [ bib |
slides |
PDF ]
Paul Beame, Raphaël Clifford, and Widad Machmouchi FOCS '13: Proc. 54th 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. |
For contact details, click on the name of the member you wish to contact.