Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-179 | 12th November 2025 12:53

Wide Replacement Products Meet Gray Codes: Toward Optimal Small-Bias Sets

RSS-Feed




TR25-179
Authors: Gil Cohen, Itay Cohen
Publication: 16th November 2025 08:04
Downloads: 188
Keywords: 


Abstract:

Optimal small-bias sets sit at the crossroads of coding theory and pseudorandomness. Reaching optimal parameters would, in particular, meet the long-standing goal of matching the Gilbert-Varshamov bound for binary codes in the high-distance regime. In a breakthrough, Ta-Shma (STOC 2017) constructed near-optimal small-bias sets via the Rozenman-Wigderson expander-walk framework, using the wide-replacement product to maintain $s$ "secure" registers and to route the walk through them. Within this framework, two barriers remain en route to optimal small-bias sets: (i) the cost of maintaining registers and (ii) limitations inherited from spectral-gap bounds for expanders.

We overcome the first—arguably the more critical—barrier. Our key technical insight is that registers can be reused even after they are exposed. Using a Gray–code–style reuse schedule, we recycle the same $s$ registers exponentially many times in $s$, thereby reducing the register–maintenance cost exponentially. This yields the first improvement over Ta-Shma's construction in nearly a decade---quantitatively modest but an important first step toward a truly optimal construction. The remaining barrier is fairly standard in isolation; the challenge is to overcome it in concert with our register-reuse framework.



ISSN 1433-8092 | Imprint