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 [Ta-Shma, 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.

The Zig-Zag product of two graphs,$Z= G\bigcirc{\!\!\!\!\!\! \mathrm{z}}\ H$, was introduced in the seminal work of Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound, which is used throughout, states that the spectral expansion of the Zig-Zag product can be bounded roughly by the sum of the spectral expansions of the individual graphs,$\omega z\leq\omega_{H}+\omega_{G}$. In this work we derive, for every (vertex-transitive) c-regular graph$H$on$d$vertices, a tight bound for$\omega z$by taking into account the entire spectrum of$H$. Our work reveals that the bound, which holds for every graph$G$, is precisely the minimum value of the function \begin{equation*}\frac{x}{c^2} \cdot \sqrt{1-\frac{d \cdot h(x)}{x \cdot h^{\prime}(x)}}\end{equation*} in the domain$(c^{2},\ \infty)$, where$h(x)$is the characteristic polynomial of$H^{2}$. As a consequence, we establish that Zig-Zag products are indeed intrinsically quadratic away from being Ramanujan. We further prove tight bounds for the spectral ex-pansion of the more fundamental replacement product. Our lower bounds are based on results from analytic combinatorics, and we make use of finite free probability to prove their tightness. In a broader context, our work uncovers intriguing links between the two fields and these well-studied graph operators.

More than twenty years ago, Capalbo, Rein-gold, Vadhan and Wigderson gave the first (and up to date only) explicit construction of a bipartite expander with almost full combinatorial expansion. The construction incorporates zig-zag ideas together with extractor technology, and is rather complicated. We give an alternative construction that builds upon recent constructions of hyper-regular, high-dimensional expanders. The new construction is, in our opinion, simple and elegant.Beyond demonstrating a new, surprising, and intriguing, application of high-dimensional expanders, the construction employs totally new ideas which we hope may lead to progress on the still remaining open problems in the area.