Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,..., xn}: 1. Noise-resistant. A syntactically multilinear formula computing a polynomial h is ε-noiseresistant, if it approximates h even when each of its edges is multiplied by an arbitrary value that is ε close to 1 (we think of this value as noise). Any formula is 0-noise-resistant, and, more generally, the smaller ε is the less restricted an ε-noise-resistant formula is. We prove an Ω(n/k) lower bound for the depth of 2 −k-noise-resistant syntactically multilinear formulas, for every k ∈ N. 2. Non-cancelling. A syntactically multilinear formula is τ-non-cancelling, if for every sum gate v in Φ, the norm of the polynomial computed by v is at least τ times the norm of the polynomial computed by both children of v. Any formula is 0-non-cancelling, and, more generally, the smaller τ is the less restricted a τ-non-cancelling formula is. We prove an Ω(n/k) lower bound for the depth of 2 −k-non-cancelling syntactically multilinear formulas, for every k ∈ N