loading...
Multilinear- NC₁ ≠ Multilinear- NC₂
Rome, Italy October 17-October 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.4245th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.