C4AI Perspectives in AI: Ronald Fagin

The Perspectives in AI seminar of the C4AI will host Dr. Ronald Fagin, (IBM Fellow at IBM Research Center – Almaden, USA) on November 29th, 17h – 18h30​​ Brasilia time (3pm – 4:30pm EST), to talk about “Applying Theory to Practice: From the Threshold Algorithm to Logical Neural Nets”.

Title: “Applying Theory to Practice: From the Threshold Algorithm to Logical Neural Nets”
Date:  November 29th, 17h-18h30​​ Brasilia time (3pm – 4:30pm EST)

Available at C4AI Youtube Channel:  https://www.youtube.com/watch?v=Ef33n3l3glI  

Abstract: The speaker will talk about applying theory to practice, with a focus on three 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 work won the 2020 Alonzo Church Award, the highest prize for research in logic and computation. The third case study, on real-valued logics, arose as part of a large “Logical Neural Nets” (LNN) project at IBM. The inputs to, say, an “and” gate could be any numbers in the interval [0,1]. The system builders of LNN wanted a sound and complete axiomatization for real-valued logic, which this very recent work provides. It also allows weights, where the importance of some formulas can be greater than that of other formulas. This talk will be completely self-contained. The talk is aimed at both theoreticians and practitioners, to show them the mutual benefits of working together.

Short Bio: Ronald Fagin is an IBM Fellow at IBM Research – Almaden. IBM Fellow is IBM’s highest technical honor. There are currently about 100 active IBM Fellows (out of around 350,000 IBM employees worldwide), and there have been only around 300 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 member of the National Academy of Sciences, the National Academy of Engineering and the American Academy of Arts and Sciences. He is a Fellow of ACM and AAAS (American Association for the Advancement of Science), and a Life Fellow of IEEE. He has co-authored four papers that won Best Paper Awards and three papers that won Test-of-time Awards, all in major conferences. One of his papers won the Gödel Prize, the top prize for a paper in theoretical computer science. His work on data exchange won the ACM SIGLOG Alonzo Church Award for Outstanding Contributions to Logic and Computation. 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).