Ronald Fagin
IBM Research – Almaden
Title: Applying theory of data to practice
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 less than 100 active IBM Fellows (out of around 400,000 IBM employees worldwide), and there have been only around 250 IBM Fellows in the over 50-year history of the program. Fagin 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, and Laurea Honoris Causa by the University of Calabria (the highest honor of the Italian university system) . He won the IEEE Technical Achievement Award, IEEE W. Wallace McDowell Award (the highest award of the IEEE Computer Society), and ACM SIGMOD Edgar F. Codd Innovations Award (a lifetime achievement award in databases). One of his papers won the Gödel Prize, the top prize for a paper in theoretical computer science. He was elected to the US National Academy of Engineering and the American Academy of Arts and Sciences.
Joseph Halpern
Joesph C. Ford Professor, Cornell University
Title: Actual Causality
Abstract: what does it mean that an event C “actually caused” event E? The problem of defining actual causation goes beyond mere philosophical speculation. For example, in many legal arguments, it is precisely what needs to be established in order to determine responsibility. (What exactly was the actual cause of the car accident or the medical problem?) The hilosophy literature has been struggling with the problem of defining causality since the days of Hume, in the 1700s. Many of the definitions have been couched in terms of counterfactuals. (C is a cause of E if, had C not happened, then E would not have happened.) In 2001, Judea Pearl and I introduced a new definition of actual cause, using Pearl’s notion of structural equations to model counterfactuals. The definition has been revised twice since then, extended to deal with notions like “responsibility” and “blame”, and applied in databases and program verification. I survey the last 15 years of work here, including joint work with Judea Pearl, Hana Chockler, and Chris Hitchcock. The talk will be completely self-contained.
Bio:
Joseph Halpern received a B.Sc. in mathematics from the University of Toronto in 1975 and a Ph.D. in mathematics from Harvard in 1981. In between, he spent two years as the head of the Mathematics Department at Bawku Secondary School, in Ghana. After a year as a visiting scientist at MIT, he joined the IBM Almaden Research Center in 1982, where he remained until 1996, also serving as a consulting professor at Stanford. In 1996, he joined the Computer Science Department at Cornell University, where he is currently the Joesph C. Ford Professor and was department chair 2010-14.
Halpern’s major research interests are in reasoning about knowledge and uncertainty, security, distributed computation, decision theory, and game theory. Together with his former student, Yoram Moses, he pioneered the approach of applying reasoning about knowledge to analyzing distributed protocols and multi-agent systems. He has coauthored 5 patents, three books (“Reasoning About Knowledge”, “Reasoning about Uncertainty”, and “Actual Causality”), and over 360 technical publications.
Halpern is a Fellow of AAAI, AAAS (American Association for the Advancement of Science), the American Academy of Arts and Sciences, ACM, IEEE, the Game Theory Society, the National Academy of Engineering, and SAET (Society for the Advancement of Economic Theory). Among other awards, he received the Kampe de Feriet Award in 2016, the ACM SIGART Autonomous Agents Research Award in 2011, the Dijkstra Prize in 2009, the ACM/AAAI Newell Award in 2008, the Godel Prize in 1997, was a Guggenheim Fellow in 2001-02, and a Fulbright Fellow in 2001-02 and 2009-10. Two of his papers have won best-paper prizes at IJCAI (1985 and 1991), and another two received best-paper awards at the Knowledge Representation and Reasoning Conference (2006 and 2012). He was editor-in-chief of the Journal of the ACM (1997-2003) and has been program chair of a number of conferences, including the Symposium on Theory in Computing (STOC), Logic in Computer Science (LICS), Uncertainty in AI (UAI), Principles of Distributed Computing (PODC), and Theoretical Aspects of Rationality and Knowledge (TARK). He started and continues to be the administrator of CoRR, the computer science section of arxiv.org.