We prove that the OR function on {-1,1\} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous results were either not tight or had ε = Ω (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known. We prove that the OR function on {−1,1}n can be pointwise approximated with error ϵ by a polynomial of degree O(k) and weight 2O(nlog(1/ϵ)/k) , for any k≥nlog(1/ϵ) . This result is tight for any k≤(1−Ω(1))n . Previous results were either not tight or had ϵ=Ω(1) . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF . For these two classes no such result was known. One motivation for such results comes from the study of indistinguishability. Two distributions P , Q over n -bit strings are (k,δ) -indistinguishable if their projections on any k bits have statistical distance at most δ . The above approximations give values of (k,δ) that suffice to fool OR , symmetric functions, and bounded-width CNF , and the first result is tight for all k while the second result is tight for k≤(1−Ω(1))n . We also show that any two (k,δ) -indistinguishable distributions are O(nk/2δ) -close to two distributions that are (k,0) -indistinguishable, improving the previous bound of O(n)kδ . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.
We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and ϵ > 0 be a constant. Let R 1,pub ϵ ( f ) represent the communication complexity of f , with worst-case error ϵ in this model. We show that if for computing f k ( k independent copies of f ) in this model, o ( k ċ R 1, pub 1/3 ( f )) communication is used, then the success is exponentially small in k . We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest. Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω( n ) for the set-disjointness problem on n -bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.
We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and e > 0 be a constant. Let R1,pube(f) represent the communication complexity of f, with worst-case error e in this model. We show that if for computing fk (k independent copies of f) in this model, o(k c R1, pub1/3(f)) communication is used, then the success is exponentially small in k. We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest.Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω(n) for the set-disjointness problem on n-bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.