Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ZERO-ERROR INFORMATION THEORY:
Reports tagged with zero-error information theory:
TR18-096 | 13th May 2018
Venkatesan Guruswami, Andrii Riazanov

#### Beating Fredman-Komlós for perfect $k$-hashing

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... 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