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-178 | 6th September 2026 17:29

Optimal Hitting Set Generators via A Potential-Descent Framework

RSS-Feed




TR26-178
Authors: Gonen Krak
Publication: 13th September 2026 15:23
Downloads: 95
Keywords: 


Abstract:

We use this framework to construct HSGs for read-once CNFs and read-once CNFs with parities. For formulas on $n$ variables with density at least $\varepsilon$, our generators use $O(\log(n/\varepsilon))$ seed bits. This bound is optimal up to a constant factor. Applying the hitting reduction of Gopalan, Meka, Reingold, Trevisan, and Vadhan gives the same seed bound for general ordered width-3 read-once branching programs. For this class, our construction is the first to achieve optimal dependence on both length and acceptance density. The result provides further evidence supporting the longstanding conjecture $\mathrm{L} = \mathrm{RL}$



ISSN 1433-8092 | Imprint