Time+Place: Tuesday 19/04/2016 14:30 Room Auditorium 2 Taub Bld.
Title: Applying theory to practice (and practice to theory)
Speaker: Ronald Fagin - TCE Henry Taub Distinguished Visitor http://researcher.watson.ibm.com/researcher/view.php?person=us-fagin
Affiliation: IBM Research - Almaden
Host: Benny Kimelfeld


The speaker will talk about applying theory to practice, with a focus on 
two IBM case studies.  In the first case study, the practitioner 
initiated the interaction. This interaction led to the following 
problem.  Assume that there is a set of "voters" and a set of "candidates", 
where each voter assigns a numerical score to each candidate.  There is a 
scoring function (such as the mean or the median), and a consensus ranking 
is obtained by applying the scoring function to each candidate's scores.  
The problem is to find the top k candidates, while minimizing the number of 
database accesses. The speaker will present an algorithm that is optimal in an 
extremely strong sense:  not just in the worst case or the average case, 
but in every case!  Even though the algorithm is only 10 lines long (!), 
the paper containing the algorithm won the 2014 Goedel Prize, the 
top prize for a paper in theoretical computer science.

The interaction in the second case study was initiated by theoreticians, 
who wanted to lay the foundations for "data exchange", in which data is 
converted from one format to another.  Although this problem may sound 
mundane, the issues that arise are fascinating, and this work made data 
exchange a new subfield, with special sessions in every major database 

This talk will be completely self-contained, and the speaker will derive 
morals from the case studies. The talk is aimed at both theoreticians 
and practitioners, to show them the mutual benefits of working together. 

Bio of speaker:
Ronald Fagin is an IBM Fellow at IBM Research - Almaden.  IBM Fellow is 
IBM's highest technical honor. There are currently around 90 active 
IBM Fellows (out of over 400,000 IBM employees worldwide), and 
there have been only around 250 IBM Fellows in the over 50-year history 
of the program.  Ron received his B.A. in mathematics from Dartmouth 
College and his Ph.D. in mathematics from the University of California 
at Berkeley. He is a Fellow of IEEE, ACM, and AAAS (American Association 
for the Advancement of Science). He has co-authored four papers that won 
Best Paper Awards and three papers that won Test-of-time Awards, all in 
major conferences He was named Docteur Honoris Causa by the University 
of Paris. He won the IEEE Technical Achievement Award, IEEE W. Wallace 
McDowell Award, and ACM SIGMOD Edgar F. Codd Innovations Award (a 
lifetime achievement award in databases). He is a member of the US 
National Academy of Engineering and the American Academy of Arts and 

Refreshments will be served from 14:15
Lecture starts at 14:30