Skip to main content

Theory researchers present five papers at BCTCS 2010

News Image

06 April 2010



More News...
Algorithms and theory researchers at Bristol University have been accepted to give five talks at the British Colloquium for Theoretical Computer Science (BCTCS) April 6-9, 2010 in Edinburgh.

"Pattern Matching Algorithms For Streaming Data" will discuss the exciting new area of low-latency pattern matching. The talk is based on a recent paper by Bristol University academics Raphael Clifford and Benjamin Sach and will present a surprising result: in many cases restricting the system to a hard time-bound per input symbol still allows the same performance to be achieved.

"Permuted Common Supersequence" tackles variants of the classic NP-hard problem known as Shortest Common Supersequence (SCS). SCS is a very important problem in computer science with applications to data compression, scheduling, query optimization, text comparison and analysis, and biological sequence comparisons and analysis. New hardness results are given as well as both deterministic and randomised approximation schemes. This is joint work with Raphael Clifford, Zvika Gotthilf, Moshe Lewenstein and Alexandru Popa.

Flood-It is a computer game played by millions the world over. The object is to turn a board full of coloured squares into one single colour in a limited number of flood filling moves. In "Flood-It: The Colourful Game of Board Domination", David Arthur, Raphael Clifford, Markus Jalsenius, Ashley Montanaro and Benjamin Sach explore the game's many fascinating mathematical properties, showing that it is NP-hard and hence as hard as many real-world problems in Computer Science. Among other consequences, this implies that anyone who provided a quick solution to this game would win one of the seven famous Clay Mathematics million-dollar prizes.

One of the most famous results in the field of quantum computation is that quantum computers can search an unstructured list for a special "marked" item more efficiently than standard ("classical") computers. However, in realistic search problems, there is often some prior information ("advice") about the location of the marked item. This can be used to guide the search process, and sometimes obtain much better performance than naive unstructured quantum search. In a talk titled "Quantum Search With Advice", Ashley Montanaro will present new quantum algorithms that take advantage of such advice, given in the form of a probability distribution. The algorithms can achieve significant speed-ups over any possible classical algorithm. In some cases, exponential speed-ups can be achieved (on average).

In the final talk, "From Coding Theory to Efficient Pattern Matching", the problem of pattern matching in the presence of promiscuous symbols (wildcards) is presented. A brief history of the wide range of techniques developed to tackle this problem is given and an intimate link between inexact matching with wildcards and algebraic coding theory is discussed. This work is by Peter Clifford, Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild.

Markus Jalsenius and Alexandru Popa are both funded from EPSRC grant EP/F02682X/1. Ashley Montanaro is an EPSRC postdoctoral fellow in Theoretical Computer Science. Benjamin Sach is currently funded by a university PhD scholarship and has been awarded an EPSRC postdoctoral fellowship in Theoretical Computer Science, to commence October 2010.