2 citations · 2 across the 4 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DS2020
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
Bartłomiej Dudek, Paweł Gawrychowski
Permutation appears in permutation if there exists a subsequence of that is order-isomorphic to . The natural question is to check if appears in , and if so c…
cs.DS2020
Generalised Pattern Matching Revisited
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
In the problem of [STOC'94, Muthukrishnan and Palem], we are given a text of length over an alphabet , a patter…
cs.DS2020
Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
The popular 3SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements su…