Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-267 | 17th October 2026 15:21

Hitting Set Generators for low-degree F2-polynomials with almost optimal density

RSS-Feed




TR26-267
Authors: Tal Yankovitz
Publication: 21st October 2026 08:10
Downloads: 42
Keywords: 


Abstract:

We construct explicit hitting set generators for $\mathbb{F}_2$-polynomials in $n$ variables of degree at most $d$ with an almost optimal density, and seed length $O(d \log n+d^2)$, which is optimal for $d = O(\log n)$.

Second, we address large-field hitting set generators. The influential state-of-the-art construction by Guruswami and Xing (CCC '14) - which is based on machinery from algebraic geometric codes - had an almost optimal seed length and density. Our first contribution there is a construction with an improved density. Our second large-field contribution is a comparable construction which is based on elementary machinery only.



ISSN 1433-8092 | Imprint