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