loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
Multilinear- NC₁ ≠ Multilinear- NC₂
Rome, Italy
October 17-October 19
ISBN: 0-7695-2228-9
ASCII Text
x 
 
Ran Raz, "Multilinear- NC₁ ≠ Multilinear- NC₂," Foundations of Computer Science, IEEE Annual Symposium on, pp. 344-351, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.42,
author = {Ran Raz},
title = {Multilinear- NC₁ ≠ Multilinear- NC₂},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {344-351},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.42},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Multilinear- NC₁ ≠ Multilinear- NC₂
SN - 0272-5428
SP344
EP351
A1 - Ran Raz,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Ran Raz, Weizmann Institute
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(x1, ..., xn), 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 f is of size n^{\Omega (\log n)}.
    • This gives a super-polynomial gap between multilinear circuit and formula size, and separates multilinear NC₁ circuits from multilinear NC₂ circuits.
    Citation:
    Ran Raz, "Multilinear- NC₁ ≠ Multilinear- NC₂," focs, pp.344-351, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.