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

## Fingerprint

Dive into the research topics of 'Multilinear-NC_{1}≠ multilinear-NC

_{2}'. Together they form a unique fingerprint.