Multilinear-NC 1 ≠ multilinear-NC 2

Research output: Contribution to journalConference articlepeer-review

19 Scopus citations

Abstract

An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit example for a polynomial f(x 1, ..., x n), with coefficients in {0,1}, such that over any field: 1. f can be computed by a polynomial-size multilinear circuit of depth O(log 2 n). 2. Any multilinear formula for / is of size n (log n). This gives a super-polynomial gap between multilinear circuit and formula size, and separates multilinear NC 1. circuits from multilinear NC 2 circuits.

Original languageEnglish (US)
Pages (from-to)344-351
Number of pages8
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - Dec 1 2004
Externally publishedYes
EventProceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy
Duration: Oct 17 2004Oct 19 2004

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Multilinear-NC <sub>1</sub> ≠ multilinear-NC <sub>2</sub>'. Together they form a unique fingerprint.

Cite this