zbMATH — the first resource for mathematics

Separation of multilinear circuit and formula size. (English) Zbl 1213.68301
Summary: An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit polynomial $$f(x_{1},\dots ,x_{n})$$ with coefficients in $$\{0,1\}$$ such that over any field, $$f$$ can be computed by a polynomial-size multilinear circuit of depth $$O(\log ^{2}n)$$, and any multilinear formula for $$f$$ is of size $$n\Omega (\log n)$$. This gives a super-polynomial gap between multilinear circuit and formula size, and separates multilinear $$\text{NC}_{1}$$ circuits from multilinear $$\text{NC}_{2}$$ circuits.

MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68Q25 Analysis of algorithms and problem complexity 94C05 Analytic circuit theory
Full Text: