Title:
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs.

Joint work with Per Austrin, Petteri Kaski and Mikko Koivisto.

Abstract:
Two sets A, B of binary strings of length n form a Uniquely Decodable Code Pair (UDCP) if every pair a in A, b in B yields a distinct sum a+b, where the addition is over Z^n. We show that every UDCP (A, B), with |A| = 2^{(1-eps)n} and |B| = 2^{b*n}, satisfies b <= 0.4229 +\sqrt{eps}. For sufficiently small eps this improves previous bounds by (among others) van Tilborg (‘78), Urbanke & Li (’98) and Ordentlich & Shayevitz (’15), which upper bound b respectively by 0.5, 0.4921 and 0.4798, as eps approaches 0.