Name
Abstract | ||
|---|---|---|
The class of polynomials computable by polynomial size log-depth arithmetic circuits (VNC 1) is known to be computable by constant width polynomial degree circuits (VsSC 0), but whether the converse containment holds is an open problem. As a partial answer to this question, we give a construction which shows that syntactically multilinear circuits of constant width and polynomial degree can be depth-reduced, which in our notation shows that sm-VsSC 0 $${\subseteq}$$ 驴 sm-VNC 1. We further strengthen this inclusion, by giving a separate construction that provides a width-efficient simulation for constant width syntactically multilinear circuits by constant width syntactically multilinear algebraic branching programs; in our notation, sm-VsSC 0 $${\subseteq}$$ 驴 sm-VBWBP. We then focus on polynomial size syntactically multilinear circuits and study relationships between classes of functions obtained by imposing various resource (width, depth, degree) restrictions on these circuits. Along the way, we also observe a characterization of the class NC 1 in terms of a restricted class of planar branching programs of polynomial size. Finally, in contrast to the general case, we report closure and stability of coefficient functions for the syntactically multilinear classes studied in this paper. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00037-013-0072-x | Computational Complexity |
Keywords | Field | DocType |
polynomial degree,resource trade-offs,syntactically multilinear class,polynomial size syntactically multilinear,polynomial size log-depth arithmetic,constant width polynomial degree,syntactically multilinear arithmetic circuits,class nc,polynomial size,constant width,syntactically multilinear circuit,constant width syntactically multilinear | Converse,Discrete mathematics,Combinatorics,Notation,Algebraic number,Open problem,Polynomial,Degree of a polynomial,Electronic circuit,Multilinear map,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 3 | 1420-8954 |
Citations | PageRank | References |
3 | 0.40 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maurice Jansen | 1 | 63 | 6.93 |
| Meena Mahajan | 2 | 688 | 56.90 |
| B. V. Rao | 3 | 3 | 0.40 |