The Forrelation problem, first introduced by Aaronson  and Aaronson and Ambainis , is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity ; the first separation between poly-logarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes BQP and PH ; and improved separations between quantum and classical communication complexity . In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than ≈ 1/√N, that is, the success probability is larger than ≈ 1/2 + 1/√N. This is unavoidable as ≈ 1/√N is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage ≈ 1/√N, in all these models. To achieve separations when the classical protocol has smaller advantage, we study in this work the xor of k independent copies of (a variant of) the Forrelation function (where k ≪ N). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level 2k is bounded by αk (that is, the sum of the absolute values of all Fourier coefficients at level 2k is bounded by αk), cannot compute the xor of k independent copies of the Forrelation function with advantage better than (Equation presented). This is a strengthening of a result of , that gave a similar statement for k = 1, using the technique of . We give several applications of our result. In particular, we obtain the following separations: Quantum versus Classical Communication Complexity. We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where Alice and Bob also share polylog(N) EPR pairs), and such that, any classical randomized protocol of communication complexity at most õ(N1/4), with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [10, 12]. Quantum Query Complexity versus Bounded Depth Circuits. We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity polylog(N), and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constant-depth circuit has polynomially small advantage were known .