Multilinear-NC 1 ≠ multilinear-NC 2

Ran Raz

Multilinear-NC ₁ ≠ multilinear-NC ₂

Research output: Contribution to journal › Conference article › peer-review

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 ₁, ..., 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 ² 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 ₁. circuits from multilinear NC ₂ circuits.

Original language	English (US)
Pages (from-to)	344-351
Number of pages	8
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
State	Published - 2004
Externally published	Yes
Event	Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy Duration: Oct 17 2004 → Oct 19 2004

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@article{ad6dae2ae3724dd997c310d71a3a8e8e,

title = "Multilinear-NC 1 ≠ multilinear-NC 2 ",

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.",

author = "Ran Raz",

year = "2004",

language = "English (US)",

pages = "344--351",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

note = "Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 ; Conference date: 17-10-2004 Through 19-10-2004",

}

TY - JOUR

T1 - Multilinear-NC 1 ≠ multilinear-NC 2

AU - Raz, Ran

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/17744399362

UR - https://www.scopus.com/inward/citedby.url?scp=17744399362&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:17744399362

SN - 0272-5428

SP - 344

EP - 351

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004

Y2 - 17 October 2004 through 19 October 2004

ER -

Multilinear-NC ₁ ≠ multilinear-NC ₂

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this