Multilinear-NC 1 ≠ multilinear-NC 2

Research output: Contribution to journalConference article

18 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