mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
and
computer scientist
A computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...
IBM Almaden Research Center
IBM Research is the research and development division for IBM, an American multinational information technology company headquartered in Armonk, New York, with operations in over 170 countries. IBM Research is the largest industrial research org ...
finite model theory Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to inte ...
, and reasoning about knowledge.
Biography
Ron Fagin was born and grew up in
Oklahoma City
Oklahoma City (), officially the City of Oklahoma City, and often shortened to OKC, is the capital and largest city of the U.S. state of Oklahoma. The county seat of Oklahoma County, it ranks 20th among United States cities in population, a ...
, where he attended Northwest Classen High School. He was later elected to the Northwest Classen Hall of Fame. He completed his undergraduate degree at
Dartmouth College
Dartmouth College (; ) is a private research university in Hanover, New Hampshire. Established in 1769 by Eleazar Wheelock, it is one of the nine colonial colleges chartered before the American Revolution. Although founded to educate Native A ...
. Fagin received his Ph.D. in Mathematics from the
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...
in 1973, where he worked under the supervision of
Robert Vaught
Robert Lawson Vaught (April 4, 1926 – April 2, 2002) was a mathematical logician and one of the founders of model theory.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
IBM Research is the research and development division for IBM, an American multinational information technology company headquartered in Armonk, New York, with operations in over 170 countries. IBM Research is the largest industrial research org ...
in
San Jose, California
San Jose, officially San José (; ; ), is a major city in the U.S. state of California that is the cultural, financial, and political center of Silicon Valley and largest city in Northern California by both population and area. With a 2020 popul ...
.
He has served as program committee chair for ACM Symposium on Principles of Database Systems 1984, ACM Symposium on Principles of Database Systems 1984, Theoretical Aspects of Reasoning about Knowledge 1994, Theoretical Aspects of Reasoning about Knowledge 1994, ACM Symposium on Theory of Computing 2005, Symposium on Theory of Computing 2005, and the International Conference on Database Theory 2009.
Fagin has received numerous professional awards for his work. He is a Member of the
National Academy of Sciences
The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nati ...
American Academy of Arts and Sciences
The American Academy of Arts and Sciences (abbreviation: AAA&S) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and ...
IEEE
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...
Fellow, and Fellow of the
American Association for the Advancement of Science
The American Association for the Advancement of Science (AAAS) is an American international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific respons ...
. One of his papers won the Gödel Prize. He received a Docteur Honoris Causa from the
University of Paris
, image_name = Coat of arms of the University of Paris.svg
, image_size = 150px
, caption = Coat of Arms
, latin_name = Universitas magistrorum et scholarium Parisiensis
, motto = ''Hic et ubique terrarum'' (Latin)
, mottoeng = Here and a ...
, and a Laurea Honoris Causa from the University of Calabria in Italy. The IEEE granted him the IEEE
W. Wallace McDowell Award
The W. Wallace McDowell Award is awarded by the IEEE Computer Society for outstanding theoretical, design, educational, practical, or related innovative contributions that fall within the scope of Computer Society interest. This is the highest tec ...
and the IEEE Technical Achievement Award (now known as the Edward J. McCluskey Technical Achievement Award ); and the ACM granted him the ACM SIGMOD Edgar F. Codd Innovations Award. The European Association for Theoretical Computer Science (in conjunction with the ACM Special Interest Group for Logic and Computation, the European Association for Computer Science Logic, and the Kurt Gödel Society) granted him and the co-authors of two of his papers, the Alonzo Church Award for Logic and Computation. IBM granted him eight IBM Outstanding Innovation Awards, two IBM supplemental Patent Issue Awards, given for key IBM patents, three IBM Outstanding Technical Achievement Awards, and two IBM Corporate Awards. He won Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, the 2010 International Conference on Database Theory, and the 2015 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.
Work
Fagin's theorem
Fagin's theorem
Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithm ...
, 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 non-deterministic Turing machine in polynomial time. This work helped found the area of
finite model theory Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to inte ...
.
Other contributions
Another result that he proved in his PhD thesis is that first-order logic has a zero-one law, which says that if S is a first-order sentence with only relational symbols (no function or constant symbols), then the fraction of n-node structures that satisfy S converges as n goes to infinity, and in fact converges to 0 or 1. This result was proved independently by Glebskiĭ et al. earlier (1969) in Russia, with a very different proof.
He is also known for his work on higher
normal forms
Database normalization or database normalisation (see spelling differences) is the process of structuring a relational database in accordance with a series of so-called normal forms in order to reduce data redundancy and improve data integrity. ...
5NF Fifth normal form (5NF), also known as projection–join normal form (PJ/NF), is a level of database normalization designed to remove redundancy in relational databases recording multi-valued facts by isolating semantically related multiple relation ...
and DK/NF.
Besides Fagin's Theorem, other concepts named after Fagin are "Fagin's algorithm" for score aggregation, the "Fagin-inverse" for data exchange, and "Fagin games" and "Ajtai Fagin games" for proving inexpressibility results in logic.
Publications
Fagin has authored or co-authored numerous articles,Ronald Fagin The DBLP Computer Science Bibliography and a book:
* Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Reasoning about knowledge. MIT press (1995). Paperback edition (2003).
Articles, a selection:
* Ronald Fagin. "Generalized first-order spectra and polynomial-time recognizable sets". Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings, Vol. Vol. 7 (1974):43-73.
* Ronald Fagin, 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.
* Ronald Fagin, 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).
* Ronald Fagin,
Phokion G. Kolaitis
Phokion G. Kolaitis ACM (born July 4, 1950) is a computer scientist who is currently a Distinguished Research Professor at UC Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include pr ...
, 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).