Summary: We give improved explicit constructions of hitting-sets for read-once oblivious algebraic branching programs (ROABPs) and related models. For ROABPs in an unknown variable order, our hitting-set has size polynomial in \((nr)^{\frac{\log n}{\max\{1,\log\log n-\log\log r\}}}d\) over a field whose characteristic is zero or large enough, where \(n\) is the number of variables, \(d\) is the individual degree, and \(r\) is the width of the ROABP. A similar improved construction works over fields of arbitrary characteristic with a weaker size bound.
Based on a result by P. Bisht and N. Saxena [Electronic Colloquium on Computational Complexity (ECCC), 2020. https://eccc.weizmann.ac.il/report/2020/042], we also give an improved explicit construction of hitting-sets for sum of several ROABPs. In particular, when the characteristic of the field is zero or large enough, we give polynomial-size explicit hitting-sets for sum of constantly many log-variate ROABPs of width \(r=2^{O(\log d/\log\log d)}\).
Finally, we give improved explicit hitting-sets for polynomials computable by width-\(r\) ROABPs in any variable order, also known as any-order ROABPs. Our hitting-set has polynomial size for width \(r\) up to \(2^{O(\log(nd)/\log\log(nd))}\) or \(2^{O(\log^{1-\varepsilon}(nd))}\), depending on the characteristic of the field. Previously, explicit hitting-sets of polynomial size are unknown for \(r=\omega(1)\).
For the entire collection see [Zbl 1445.68009].