Explicit, almost optimal, epsilon-balanced codes

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance 1-ϵ/2 and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an explicit ϵ-biased set over k bits with support size O ( k /ϵ 2+ o (1) ). This improves upon all previous explicit constructions which were in the order of k 2 /ϵ 2 , k /ϵ 3 or k 5/4 /ϵ 5/2 . The result is close to the Gilbert-Varshamov bound which is O ( k /ϵ 2 ) and the lower bound which is Ω( k /ϵ 2 log1/ϵ).

Authors

• Amnon Ta-Shma

Keywords

• Eps-bias
• Wide replacement product
• Zig-Zag product