期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The orbit of an n-variate polynomial f(x) over a field F is the set f(Ax+b)AGL(nF) and bFn , and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over field with characteristic zero or greater than d, we construct a hitting set of size (ndw)O(w2lognminw2dlogw) for the orbit of ROABPs in unknown variable order where d is the individual degree and w is the width of ROABPs. We also give hitting set of size (ndw)O(minw2dlogw) for the orbit of polynomials computed by w-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey \cite{Saha-Thankey'21} who gave an (ndw)O(dlogw) size hitting set for the orbit of commutative ROABPs (a subclass of \textit{any-order} ROABPs) and (nw)O(w6logn) size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance dn, was asked as an open problem by \cite{Saha-Thankey'21} and this work solves it in small width setting. We prove some new rank concentration results by establishing \emph{low-cone concentration} for the polynomials over vector spaces, and they strengthen some previously known \emph{low-support} based rank concentrations shown in \cite{FSS14}. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets.
