Zobrazeno 1 - 10
of 82
pro vyhledávání: '"Clifford, Raphaël"'
Autor:
Clifford, Raphaël, Gawrychowski, Paweł, Kociumaka, Tomasz, Martin, Daniel P., Uznański, Przemysław
The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length $m$ and all length-$m$ substrings of a given text of length $n\ge m$. We focus on the $k$-mismatch version of the problem, where a d
Externí odkaz:
http://arxiv.org/abs/2105.06166
Autor:
Clifford, Peter, Clifford, Raphaël
Since its introduction Boson Sampling has been the subject of intense study in the world of quantum computing. The task is to sample independently from the set of all $n \times n$ submatrices built from possibly repeated rows of a larger $m \times n$
Externí odkaz:
http://arxiv.org/abs/2005.04214
Autor:
Clifford, Raphaël, Gawrychowski, Paweł, Kociumaka, Tomasz, Martin, Daniel P., Uznański, Przemysław
We show that the edit distance between two run-length encoded strings of compressed lengths $m$ and $n$ respectively, can be computed in $\mathcal{O}(mn\log(mn))$ time. This improves the previous record by a factor of $\mathcal{O}(n/\log(mn))$. The r
Externí odkaz:
http://arxiv.org/abs/1905.01254
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length $m$ and a substring of a longer text. We give both condit
Externí odkaz:
http://arxiv.org/abs/1802.06545
We consider the streaming complexity of a fundamental task in approximate pattern matching: the $k$-mismatch problem. It asks to compute Hamming distances between a pattern of length $n$ and all length-$n$ substrings of a text for which the Hamming d
Externí odkaz:
http://arxiv.org/abs/1708.05223
Autor:
Clifford, Peter, Clifford, Raphaël
We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed by Aaronson and Arkhip
Externí odkaz:
http://arxiv.org/abs/1706.01260
Autor:
Neville, Alex, Sparrow, Chris, Clifford, Raphaël, Johnston, Eric, Birchall, Patrick M., Montanaro, Ashley, Laing, Anthony
Publikováno v:
Nature Physics 13, 1153-1157 (2017)
It is predicted that quantum computers will dramatically outperform their conventional counterparts. However, large-scale universal quantum computers are yet to be built. Boson sampling is a rudimentary quantum algorithm tailored to the platform of p
Externí odkaz:
http://arxiv.org/abs/1705.00686
We consider the problem of computing a $(1+\epsilon)$-approximation of the Hamming distance between a pattern of length $n$ and successive substrings of a stream. We first look at the one-way randomised communication complexity of this problem, givin
Externí odkaz:
http://arxiv.org/abs/1602.07241
We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming
Externí odkaz:
http://arxiv.org/abs/1508.00731