Multilinear formulas,maximal-partition discrepancy and mixed-sources extractors |
| |
Authors: | Ran Raz Amir Yehudayoff |
| |
Affiliation: | Faculty of Mathematics and Computer Science, Weizmann Institute, Rehovot, Israel;University of Wisconsin – Madison Computer Sciences Department 1210 West Dayton Street Room 4393 Madison, WI 53706 U.S.A. PHONE: (608) 262-3158 FAX: (608) 262-9777 Email: jyc@cs.wisc.edu;University at Buffalo, The State University of New York Department of Computer Science and Engineering 201 Bell Hall Buffalo, NY 14260-2000 U.S.A. Phone: (716) 645-4742 FAX: (716) 645-3464 Email: selman@@buffalo.edu |
| |
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, orthogonal formulas, non-canceling formulas, and noise-resistant formulas. One ingredient of our proof is an explicit map that has exponentially small discrepancy for every partition of the input variables into two sets of roughly the same size. We give two additional applications of this explicit map: to extractors construction and to communication complexity. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|