We are going to show an Omega (sqrt (n)) lowerbound for this problem. The proof is based on basic concepts of Fourier analysis, and the so-called Bonami-Gross-Beckner, or Hypercontractivity inequality. This is also an interesting example to get communication complexity lowerbound from Fourier analysis since Ran Raz introduced the concept in 1995.