## Abstract

We study a new method for proving lower bounds for subclasses of arithmetic circuits. Roughly speaking, the lower bound is proved by bounding the correlation between the coefficients' vector of a polynomial and the coefficients' vector of any product of two polynomials with disjoint sets of variables. We prove lower bounds for several old and new subclasses of circuits. Monotone Circuits: We prove a tight 2^{Ω(n)} lower bound for the size of monotone arithmetic circuits. The highest previous lower bound was 2^{Ω(√n)}. Orthogonal Formulas: We prove a tight 2 ^{Ω(n)} lower bound for the size of orthogonal multilinear formulas (defined, motivated, and studied by Aaronson). Previously, nontrivial lower bounds were only known for subclasses of orthogonal multilinear formulas. Non-Cancelling Formulas: We define and study the new model of non-cancelling multilinear formulas. Roughly speaking, in this model one is not allowed to sum two polynomials that almost cancel each other. The non-cancelling multilinear model is a generalization of both the monotone model and the orthogonal model. We prove lower bounds of n^{Ω(1)} for the depth of non-cancelling multilinear formulas. Noise-Resistant Formulas: We define and study the new model of noise-resistant multilinear formulas. Roughly speaking, noise-resistant formulas are formulas that compute the required polynomial even in the presence of noise. We prove lower bounds of n^{Ω(1)} for the depth of noise-resistant multilinear formulas. One ingredient of our proof is an explicit map f : {0,1}^{n} → {0,1} that has exponentially small discrepancy for every partition of {1,..., n} into two sets of roughly the same size. We give two additional applications of this property to extractors construction and to communication complexity. Mixed-Source Extractors: A mixed-2-source is a source of randomness whose bits arrive from two independent sources (of size n/2 each), but they arrive in a fixed but unknown order. We are able to extract a linear number of almost perfect random bits from such sources. Communication Complexity: We prove a tight Ω(n) lower bound for the randomized best-partition communication complexity off. The best lower bound previously known for this model is Ω(√n).

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

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

Pages | 273-282 |

Number of pages | 10 |

DOIs | |

State | Published - 2008 |

Externally published | Yes |

Event | 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States Duration: Oct 25 2008 → Oct 28 2008 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

Other | 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 |
---|---|

Country/Territory | United States |

City | Philadelphia, PA |

Period | 10/25/08 → 10/28/08 |

## All Science Journal Classification (ASJC) codes

- General Computer Science