### Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

**2016-01-29**

1601.08031 | cs.CC

We give improved hitting sets for two special cases of Read-once Oblivious
Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known
order of the variables. The best previously known hitting set for this case had
size $(nw)^{O(\log n)}$ where $n$ is the number of variables and $w$ is the
width of the ROABP. Even for a constant-width ROABP, nothing better than a
quasi-polynomial bound was known. We improve the hitting-set size for the
known-order case to $n^{O(\log w)}$. In particular, this gives the first
polynomial-size hitting set for constant-width ROABP (known-order). However,
our hitting set only works when the characteristic of the field is zero or
large enough. To construct the hitting set, we use the concept of the rank of
the partial derivative matrix. Unlike previous approaches which build up from
mapping variables to monomials, we map variables to polynomials directly.
The second case we consider is that of polynomials computable by width-$w$
ROABPs in any order of the variables. The best previously known hitting set for
this case had size $d^{O(\log w)}(nw)^{O(\log \log w)}$, where $d$ is the
individual degree. We improve the hitting-set size to $(ndw)^{O(\log \log w)}$.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-04-28**

1904.12337 | cs.CC

Hrube\v{s} and Wigderson [HW14] initiated the study of noncommutative
arithmetic circuits with divis… show more

**2019-03-06**

1903.02366 | cs.CC

In this note, we give a short, simple and almost completely self contained
proof of a classical resu… show more

**2019-02-13**

1902.04740 | cs.CC

We study the complexity of Boolean constraint satisfaction problems (CSPs)
when the assignment must … show more

**2017-05-31**

1706.00080 | math.AG

Tropical algebra emerges in many fields of mathematics such as algebraic
geometry, mathematical phys… show more

**2018-11-04**

1811.01351 | cs.CC

We show that if a system of degree-$k$ polynomial constraints on~$n$ Boolean
variables has a Sums-of… show more

**2019-01-14**

1901.04377 | cs.CC

Proving super-polynomial size lower bounds for syntactic multilinear
Algebraic Branching Programs(sm… show more

**2018-10-25**

1810.11068 | math.NT

We present a probabilistic Las Vegas algorithm for computing the local zeta
function of a genus-$g$ … show more

**2018-07-12**

1807.04496 | cs.DS

In this paper we develop an efficient procedure for computing a (scaled)
Hadamard product for \emph{… show more

**2018-07-17**

1807.06323 | cs.CC

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel
[Ore22,DL78,Zip79,Sch80] states that any n… show more

**2018-08-20**

1808.06655 | math.AC

In this paper we study the problem of deterministic factorization of sparse
polynomials. We show tha… show more

**2017-01-19**

1701.05328 | cs.CC

We formalize a framework of algebraically natural lower bounds for algebraic
circuits. Just as with … show more

**2018-12-17**

1812.06828 | cs.CC

The existence of string functions, which are not polynomial time computable,
but whose graph is chec… show more

**2018-12-26**

1812.10249 | cs.CC

We study the question of algebraic rank or transcendence degree preserving
homomorphisms over finite… show more

**2018-08-31**

1808.10787 | cs.DS

Let $\mathbb{F}[X]$ be the polynomial ring over the variables $X=\{x_1,x_2,
\ldots, x_n\}$. An ideal… show more

**2017-11-20**

1711.07320 | cs.CC

We analyse how the standard reductions between constraint satisfaction
problems affect their proof c… show more

**2018-11-05**

1811.01600 | math.CO

We give a self-contained proof of the strongest version of Mason's
conjecture, namely that for any m… show more