Eldar Fischer, Frederic Magniez, Michel de Rougemont

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. ...
more >>>

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

We consider the problem of constructing binary codes to recover from $k$-bit deletions with efficient encoding/decoding, for a fixed $k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ ... more >>>

Boris Bukh, Venkatesan Guruswami

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>

Shafi Goldwasser, Dhiraj Holden

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 >>>

Alexander A. Sherstov, Pei Wu

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>