Long common subsequences between bit-strings and the zero-rate threshold of deletion-correcting codes
Speaker: Venkatesan Guruswami, UC Berkeley Title: Long common subsequences between bit-strings and the zero-rate threshold of deletion-correcting codes Abstract: Suppose we transmit n bits on a noisy channel that deletes some fraction of the bits arbitrarily. What’s the supremum p* of deletion fractions that can be corrected with a binary code of non-vanishing rate? Evidently p* is at […]