179 citations · 219 across the 20 of their papers we have counts for
26 papers
Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence
Peter Clifford, Raphaël Clifford
We study exact uniform sampling of permutations of length whose longest increasing subsequence (LIS) has prescribed length . Our main result is, to the best of our knowledge…
The Dynamic k-Mismatch Problem
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2
The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length and all length- substrings of a given text of length $n…
Faster classical Boson Sampling
Peter Clifford, Raphaël Clifford
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 …
RLE edit distance in near optimal time
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2
We show that the edit distance between two run-length encoded strings of compressed lengths and respectively, can be computed in time. This improv…
Upper and lower bounds for dynamic data structures on strings
Raphael Clifford, Allan Grønlund, Kasper Green Larsen +1
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 patte…
The streaming -mismatch problem
Raphaël Clifford, Tomasz Kociumaka, Ely Porat
We consider the streaming complexity of a fundamental task in approximate pattern matching: the -mismatch problem. It asks to compute Hamming distances between a pattern of leng…