CS545:

Stanford Data Science / Infoseminar

Winter 2015

# Applying theory to practice (and practice to theory)

## Ronald Fagin, IBM Research - Almaden

## Abstract

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 Gödel 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 conference.

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

Ronald Fagin is an IBM Fellow at IBM Research – Almaden. IBM Fellow is IBM's
highest technical honor. There are currently 87 active IBM Fellows (out of
430,000 IBM employees worldwide), and there have been only 257 IBM Fellows in
the 51-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 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 Sciences.