Ronald Fagin

Ronald Fagin
Born	1945 Oklahoma City, United States
Occupation(s)	Mathematician, computer scientist, IBM Fellow
Years active	1973–present
Known for	Fagin's theorem, database theory, finite model theory, epistemic reasoning

Ronald Fagin (born 1945) is a distinguished American mathematician and computer scientist, currently serving as an IBM Fellow at the IBM Almaden Research Center. He is widely acknowledged for his influential work in database theory, finite model theory, and epistemic reasoning.

Biography

Originating from Oklahoma City, Fagin completed his undergraduate education at Dartmouth College. He obtained his doctorate in Mathematics in 1973 from the University of California, Berkeley under the mentorship of Robert Vaught. That same year, he joined IBM Research, initially working at the Thomas J. Watson Research Center before transferring to the IBM Almaden Research Center in 1975.

Fagin has led several prominent conferences, including the 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).

His honors encompass election to the National Academy of Sciences, National Academy of Engineering, and the American Academy of Arts and Sciences. He is a fellow of IBM, ACM, IEEE, the American Association for the Advancement of Science, and the Asia-Pacific Artificial Intelligence Association. Fagin’s research on optimal aggregation algorithms was recognized with the prestigious Gödel Prize. He has been awarded honorary doctorates by both the University of Paris and the University of Calabria. The IEEE bestowed upon him the W. Wallace McDowell Award as well as the Technical Achievement Award; meanwhile, ACM honored him with the SIGMOD Edgar F. Codd Innovations Award. Together with collaborators, he received the Alonzo Church Award for Logic and Computation. IBM has acknowledged his contributions through multiple Outstanding Innovation Awards, Patent Issue Awards for significant patents, Technical Achievement Awards, and Corporate Awards.

His publications have earned Best Paper distinctions at leading conferences such as IJCAI (1985), ACM PODS (2001), and ICDT (2010, 2015), along with 10-year Test-of-Time Awards at PODS (2011, 2014) and ICDT (2013).

Fagin's theorem

Fagin's theorem, established in his doctoral dissertation, demonstrates that existential second-order logic precisely captures the complexity class NP. In other words, a decision problem can be formulated in existential second-order logic if and only if it can be decided by a non-deterministic Turing machine within polynomial time. This seminal result laid foundational groundwork for the discipline of finite model theory.

Other contributions

Within his PhD thesis, Fagin also established that first-order logic satisfies a zero-one law: for any first-order sentence composed solely of relational symbols, the fraction of n-element structures that satisfy it approaches either 0 or 1 as n increases indefinitely. This finding was independently proven earlier in Russia through a different approach.

Fagin made substantial advances in database theory, particularly concerning advanced normal forms such as 4NF, 5NF, and DK/NF.

Besides Fagin's theorem, several concepts bear his name: "Fagin's algorithm" for combining scores efficiently; the "Fagin-inverse" utilized in data exchange contexts; and "Fagin games" along with "Ajtai–Fagin games," which are instrumental in demonstrating logical inexpressibility results.

Publications

Ronald Fagin has contributed extensively to the field through a variety of significant articles and an essential book:

• Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Reasoning about Knowledge. MIT Press (1995). Paperback edition released in 2003.

Notable articles include:

• Ronald Fagin. "Generalized first-order spectra and polynomial-time recognizable sets". In *Complexity of Computation*, SIAM-AMS Proceedings, Volume 7 (1974): pages 43-73.
• Ronald Fagin and colleagues. "Extendible hashing—a rapid access technique for dynamic files." *ACM Transactions on Database Systems* 4, no. 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.
• Ronald Fagin et al. "Data exchange: semantics and query answering." *Theoretical Computer Science* 336 (2005): 89-124.

External links

• Ronald Fagin’s IBM research profile