DIMACS Discrete Math/Theory of Computing Seminar

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


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>log3 n one can devise a quantum algorithm that sorts n numbers (using comparisons only) in time T=O(n3/2 log3/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(n3/2). Hence for small values of S the upper bound is almost tight. Classically the time-space tradeoff for sorting is TS=Theta(n2).