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³ 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²).