Title: Digital fingerprinting codes--problems, constructions and identification of traitors

Speaker: **Hartmut Klauck**, Institute for Advanced Study, Princeton

Date: March 11, 2003, 4:30-5:30

Location: Hill Center, room 705, (Note room change) Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We investigate the complexity of sorting in the model of sequential
quantum circuits. While it is known that in general a quantum
algorithm based on comparisons cannot outperform classical sorting
algorithms by more than a constant factor in time complexity, this is
wrong in a space bounded setting. We observe that for all storage
bounds n log n>S>log^{3} n one can devise a quantum algorithm that sorts
n numbers (using comparisons only) in time T=O(n^{3/2} log^{3/2} n /
sqrt S). We then show the following lower bound on the time-space
tradeoff for sorting n numbers from a polynomial size range in a
general sorting algorithm (not necessarily based on comparisons):
TS=Omega(n^{3/2}). Hence for small values of S the upper bound is
almost tight. Classically the time-space tradeoff for sorting is
TS=Theta(n^{2}).