SFU Canada Research Chairs Seminar Series "Fingerprinting Digital Documents"
11:30 - 12:30
Rm10900
Dr. Gabor Tardos, Canada Research Chair in Computational Complexity and Geometric Arrangements
School Of Computing Science
Abstract
Including a unique code in each copy of a distributed document is an effective way of fighting intellectual piracy. Codes designed for this purpose that are secure against collusion attacks are called fingerprinting codes. In this talk we describe the mathematical model for this cryptographic problem and survey old and recent results on fingerprinting. We will put special emphasis to show how the tight analysis of a simple looking problem can use results in several far away fields of mathematics and computer science. From the problem description it is not surprising that results from probability theory and coding theory are useful, but we will see - perhaps more surprisingly - that results from game theory, approximation theory, information theory and hypergraph theory all find their way into constructions of efficient fingerprinting codes, their analysis or into the proofs establishing bounds on how efficient such codes can possibly be. Many of the recent results surveyed represent joint work with Ehsan Amiri.
About the Speaker
Dr. Gabor Tardos completed his undergraduate degree with a Diploma in Mathematics and his Ph.D in Mathematics, under the supervision of Professor Lszl Babai and Professor Pter Plfy, at Etvs University, Budapest,Hungary. In the period 1990 - 2005 he was a Research Fellow at the prestigious Alfrd Rnyi Institute of Mathematics at the Hungarian Academy of Sciences. Between 1992 - 2003 Dr. Tardos was a Professor at the Department of Computer Science, Etvs University. He was also a Visiting Professor at the Computer Science Departments of the Rutgers University (1990 - 1992) and at the University of Toronto (1995 - 1996), and a Member of the Institute for Advanced Study (1996 - 1997). Dr. Tardos joined Simon Fraser University in 2005 as a Professor at the School of Computing Science and as a Canada Tier 1 Research Chair in Computational Complexity and Geometric Arrangements. In his scientific career Dr. Tardos has been the recipient of multiple grants, awards, and honors. The Prize of the European Congress of Mathematics and the Erds Prize of the Hungarian Academy of Sciences are just two examples. Dr. Tardos has authored a large number of scientific papers with topics in combinatorics, discrete and computational geometry, and complexity theory and has greatly contributed to each of those fields. D. Zeilberger describes Dr. Tardos' work on the Fredi-Hajnal conjecture in the following way, "Just because a conjecture has been posed by brilliant people, and attempted, unsuccessfully, by quite a few other brilliant people, does not mean that the ultimate proof has to be complicated. We saw this (...) with (...) the brilliant proof of the Fredi-Hajnal conjecture, and hence the Stanley-Wilf conjecture by Adam Marcus and Gabor Tardos. Once I saw their proof, I kicked myself, as I am sure did many other people. Once you see it is so NATURAL and "obvious". But if it is so "obvious", how come no-one (including myself) could come up with it? So like most of the truly great discoveries, it is a posteriori `obvious', but definitely not `a priori'."
