Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LONGEST COMMON SUBSEQUENCE:
Reports tagged with longest common subsequence:
TR16-056 | 8th April 2016
Shafi Goldwasser, Dhiraj Holden

#### On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances

We set out to study the impact of having access to correlated instances on the fine grained complexity of polynomial time problems, which have notoriously resisted improvement.
In particular, we show how to use a logarithmic number of auxiliary correlated instances to obtain $o(n^2)$ time algorithms for the longest common ... more >>>

TR21-079 | 9th June 2021
Venkatesan Guruswami, Xiaoyu He, Ray Li

#### The zero-rate threshold for adversarial bit-deletions is less than 1/2

We prove that there exists an absolute constant $\delta>0$ such any binary code $C\subset\{0,1\}^N$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{\poly\log N}$ and thus have rate asymptotically approaching $0$. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate ... more >>>

ISSN 1433-8092 | Imprint