ML p(r)ior | Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

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

2016-01-29
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)}$.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-04-28

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

Highlights - Most important sentences from the article

2019-03-06

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

Highlights - Most important sentences from the article

2019-02-13

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

Highlights - Most important sentences from the article

2017-05-31
1706.00080 | math.AG

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-01-14
1901.04377 | cs.CC

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-07-12

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

Highlights - Most important sentences from the article

2018-07-17

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

Highlights - Most important sentences from the article

2018-08-20

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

Highlights - Most important sentences from the article

2017-01-19

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-12-26

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

Highlights - Most important sentences from the article

2018-08-31

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

Highlights - Most important sentences from the article

2017-11-20
1711.07320 | cs.CC

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

Highlights - Most important sentences from the article

2018-11-05

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

Highlights - Most important sentences from the article