Edit distance is a measure of similarity of two strings based
onthe minimum number of character insertions, deletions, and
substitutions required to transform one string into the other. The edit
distance can be computed exactly using a dynamic programming algorithm
that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a
nearly linear time algorithm that approximates edit distance within
approximation factor $\text{poly}(\log n)$. In this talk, I will
describe an algorithm with running time $\tildeO(n^{2-2/7})$ that
approximates the edit distance within a constant factor.
This is a joint work with Diptarka Chakraborty, Elazar Goldenberg,
Michal Koucky, Michael Saks
Complexity seminar
The seminar takes place in the seminar room of IM, rear building, ground floor, Friday at 14:00 - 16:00Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Debarati Das
Charles University
Friday, 23. November 2018 - 13:30 to 15:00
in IM, rear building, ground floor
The Journey from NP to TFNP Hardness
Pavel Hubáček
MFF UK
Friday, 8. June 2018 - 13:30 to 15:00
in IM, rear building, ground floor
The complexity class TFNP is the search analogue of the class NP with the additional guarantee that any
instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that
capture the computational complexity of important search problems from algorithmic game theory,
combinatorial optimization and computational topology. Thus, one of the main research objectives in the
context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving
hardness results where efficient algorithms cannot exist.
In my talk, I will show that hard-on-average TFNP problems exist under the weak assumption that there exists
a hard-on-average language in NP. In terms of techniques, our results demonstrate an interesting interplay
between problems in TFNP, derandomization techniques, and zero-knowledge proofs.
Based on joint work with Moni Naor and Eylon Yogev.
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty
Charles University
Friday, 25. May 2018 - 13:30 to 15:00
in IM, rear building, ground floor
The conjectured hardness of Boolean matrix-vector multiplication has been
used with great success to prove conditional lower bounds for numerous
important data structure problems, see Henzinger et al. [STOC'15]. In recent
work, Larsen and Williams [SODA'17] attacked the problem from the upper
bound side and gave a surprising cell probe data structure (that is, we only
charge for memory accesses, while computation is free). Their cell probe
data structure answers queries in $\tilde{O}(n^{7/4})$ time and is succinct
in the sense that it stores the input matrix in read-only memory, plus an
additional $\tilde{O}(n^{7/4})$ bits on the side. In this talk, we present a
new cell probe data structure with query time $\tilde{O}(n^{3/2})$ storing
just $\tilde{O}(n^{3/2})$ bits on the side. We then complement our data
structure with a matching lower bound showing that any data structure
storing $r$ bits on the... more
Matroids, 3-regular graphs and random restrictions
Pavel Pudlák
IM, CAS
Friday, 11. May 2018 - 13:30 to 15:00
in IM, rear building, ground floor
I will show some connections between matroids and random restrictions of Tseitin tautologies on 3-regular graphs. In particular I will show that the domains of the restrictions are flats in a matroid that is dual to a bicircular matroid. I will pose several problems concerning how these facts can be generalized to other kinds of restrictions and other graphs. This talk will be a sort of a continuation of Navid's, but I will recall everything that is needed.