### Abstract

We construct an explicit polynomial f(x_{1},..., x_{n}), with coefficients in {0,1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Ω(n^{4/3}/ log ^{2} n). The lower bound holds over any field.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 |

Pages | 438-448 |

Number of pages | 11 |

DOIs | |

State | Published - Dec 1 2007 |

Externally published | Yes |

Event | 48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States Duration: Oct 20 2007 → Oct 23 2007 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

Other | 48th Annual Symposium on Foundations of Computer Science, FOCS 2007 |
---|---|

Country | United States |

City | Providence, RI |

Period | 10/20/07 → 10/23/07 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)

## Fingerprint Dive into the research topics of 'A lower bound for the size of syntactically multilinear arithmetic circuits'. Together they form a unique fingerprint.

## Cite this

Raz, R., Shpilka, A., & Yehudayoff, A. (2007). A lower bound for the size of syntactically multilinear arithmetic circuits. In

*Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007*(pp. 438-448). [4389514] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2007.4389514