### DIMACS Theoretical Computer Science Seminar

Title: Quantum and Classical Strong Direct Product Theorems and Optimal
Time-Space Tradeoffs

Speaker: **Robert Spalek**, Charles University

Date: September 13, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A strong direct product theorem says that if we want to compute k independent
instances of a function, using less than k times the resources needed for one
instance, then our overall success probability will be exponentially small in
k. We establish such theorems for the classical as well as quantum query
complexity of the OR function. This implies slightly weaker direct product
results for all total functions. We prove a similar result for quantum
communication protocols computing k instances of the Disjointness function.

Our direct product theorems imply a time-space tradeoff T^2*S=Omega(N^3) for
sorting N items on a quantum computer, which is optimal up to polylog factors.
They also give several tight time-space and communication-space tradeoffs for
the problems of Boolean matrix-vector multiplication and matrix multiplication