Dr. Ronald (Ron) Fagin

An American computer scientist and an IBM Fellow at the IBM Almaden Research Center, he is best known for his pioneering work in database theory, finite model theory, and reasoning about knowledge. He was born and grew up in Oklahoma City, where he attended Northwest Classen High School. Following that, he completed his undergraduate degree at Dartmouth College. He received his Ph.D. in Mathematics from the University of California, Berkeley in 1973, where he worked under the supervision of Robert Vaught. His theorem, which he proved in his PhD thesis, states that existential second-order logic coincides with the complexity class NP in the sense that a decision problem can be expressed in existential second-order logic if and only if it can be solved by a nondeterministic Turing machine in polynomial time. This work was seminal to the area of finite model theory. Another well-known result that he proved is that first-order logic has a zero-one law, a tool for proving inexpressibility results for database query languages. This result was proven independently by Glebskiĭ et al. slightly earlier in Russia. He is also known for his work on higher Normal Forms in Database Theory, particularly 4NF. He joined the IBM Research Division in 1973, spending two years at the Thomas J. Watson Research Center, and then transferred in 1975 to what is now the IBM Almaden Research Center in San Jose, California. He has served as Program Committee Chair for ACM Symposium on Principles of Database Systems 1984, Theoretical Aspects of Reasoning about Knowledge 1994, ACM Symposium on Theory of Computing 2005, and the International Conference on Database Theory 2009. He has received numerous professional awards for his work. He was named IBM Fellow in 2012, the highest honor a scientist, engineer, or programmer at IBM can achieve. In addition, he was elected Member of the National Academy of Engineering, American Academy of Arts and Sciences, ACM Fellow, IEEE Fellow, and Fellow of the American Association for the Advancement of Science. He won the 2014 G?del Prize and he received a Docteur Honoris Causa from the University of Paris. In 2012, he received the IEEE granted him the IEEE W. Wallace McDowell Award Popularly referred to as the "IT Nobel," the W. Wallace McDowell Award is awarded by the IEEE Computer Society for outstanding recent theoretical, design, educational, practical, or other similar innovative contributions that fall within the scope of Computer Society interest. He was also presented with the 2011 IEEE Technical Achievement Award for pioneering contributions to the theory of rank and score aggregation. He received the ACM the ACM SIGMOD Edgar F. Codd Innovations Award. He is the recipient of eight IBM Outstanding Innovation Awards, two IBM supplemental Patent Issue Awards, given for key IBM patents, the IBM Outstanding Technical Achievement Award, and the IBM Corporate Award. He is listed among the "Highly Cited Researchers." He won Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, and the 2010 International Conference on Database Theory. He won 10-year Test-of-Time Awards at the 2011 ACM Symposium on Principles of Database Systems, the 2013 International Conference on Database Theory, and the 2014 ACM Symposium on Principles of Database Systems. He has authored or co-authored many publications in his fields of expertise. He co-authored a book, ?Reasoning About Knowledge?, with Ronald, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi, MIT press (1995), Paperback edition (2003). He also authored or co-authored several articles, including: "Generalized First-Order Spectra And Polynomial-Time Recognizable Sets". Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings, Vol. Vol. 7 (1974):43-73; with Jurg Nievergelt, Nicholas J. Pippenger, and H. Raymond Strong. "Extendible Hashing?A Fast Access Method For Dynamic Files" ACM Transactions on Database Systems (TODS) 4.3 (1979): 315-344; "Combining Fuzzy Information From Multiple Systems" Journal of Computer and System Sciences 58 (1999): 83-99. (Special issue for selected papers from the 1996 ACM Symposium on Principles of Database Systems); with Amnon Lotem, and Moni Naor. "Optimal Aggregation Algorithms for Middleware" Journal of Computer and System Sciences 66 (2003): 614-656. (Special issue for selected papers from the 2001 ACM Symposium on Principles of Database Systems); and with Phokion Kolaitis, Renee J Miller, and Lucian Popa. Data Exchange: Semantics and Query Answering, Theoretical Computer Science 336 (2005): 89-124. (Special issue for selected papers from the 2003 International Conference on Database Theory).