  A strong direct product theorem states that if we want to compute $k$
independent instances of a function, using less than $k$ times the resources
needed for one instance, then the overall success probability will be
exponentially small in $k$. We establish such a theorem for the randomized
communication complexity of the Disjointness problem, i.e., with communication
$const\cdot kn$ the success probability of solving $k$ instances of size $n$
can only be exponentially small in $k$. We show that this bound even holds for
$AM$ communication protocols with limited ambiguity. This also implies a new
lower bound for Disjointness in a restricted 3-player NOF protocol, and optimal
communication-space tradeoffs for Boolean matrix product. Our main result
follows from a solution to the dual of a linear programming problem, whose
feasibility comes from a so-called Intersection Sampling Lemma that generalizes
a result by Razborov.
