Ronald Fagin

MFCS Conference 2024 Conference Paper

On the Number of Quantifiers Needed to Define Boolean Functions

• Marco Carmosino
• Ronald Fagin
• Neil Immerman
• Phokion G. Kolaitis
• Jonathan Lenchner
• Rik Sengupta

The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binary strings with an ordering relation, using a technique we call parallel play, which significantly reduces the number of quantifiers needed in many cases. Ordered structures such as strings have historically been notoriously difficult to analyze in the context of these and similar games. Nevertheless, in this paper, we provide essentially tight bounds on the number of quantifiers needed to characterize different-sized subsets of strings. The results immediately give bounds on the number of quantifiers necessary to define several different classes of Boolean functions. One of our results is analogous to Lupanov’s upper bounds on circuit size and formula size in propositional logic: we show that every Boolean function on n-bit inputs can be defined by a FO sentence having (1+ε)n/log(n) + O(1) quantifiers, and that this is essentially tight. We reduce this number to (1 + ε)log(n) + O(1) when the Boolean function in question is sparse.

KR Conference 2023 Conference Paper

A Framework for Combining Entity Resolution and Query Answering in Knowledge Bases

• Ronald Fagin
• Phokion G. Kolaitis
• Domenico Lembo
• Lucian Popa
• Federico Scafoglieri

We propose a new framework for combining entity resolution and query answering in knowledge bases (KBs) with tuple-generating dependencies (tgds) and equality-generating dependencies (egds) as rules. We define the semantics of the KB in terms of special instances that involve equivalence classes of entities and sets of values. Intuitively, the former collect all entities denoting the same real-world object, while the latter collect all alternative values for an attribute. This approach allows us to both resolve entities and bypass possible inconsistencies in the data. We then design a chase procedure that is tailored to this new framework and has the feature that it never fails; moreover, when the chase procedure terminates, it produces a universal solution, which in turn can be used to obtain the certain answers to conjunctive queries. We finally discuss challenges arising when the chase does not terminate.

MFCS Conference 2022 Conference Paper

On the Number of Quantifiers as a Complexity Measure

• Ronald Fagin
• Jonathan Lenchner
• Nikhil Vyas 0001
• R. Ryan Williams

In 1981, Neil Immerman described a two-player game, which he called the "separability game" [Neil Immerman, 1981], that captures the number of quantifiers needed to describe a property in first-order logic. Immerman’s paper laid the groundwork for studying the number of quantifiers needed to express properties in first-order logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas [Fagin et al. , 2021] rediscovered the game, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer k, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank k, but where the same property needs 2^Ω(k²) quantifiers to be expressed. We next give the precise number of quantifiers needed to distinguish two rooted trees of different depths. Finally, we give a new upper bound on the number of quantifiers needed to express s-t connectivity, improving the previous known bound by a constant factor.

I&C Journal 2013 Journal Article

Solutions and query rewriting in data exchange

• Marcelo Arenas
• Pablo Barceló
• Ronald Fagin
• Leonid Libkin

Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema. Given a source instance, there may be many solutions – target instances that satisfy the constraints of the data exchange problem. Previous work has identified two classes of desirable solutions: canonical universal solutions, and their cores. Query answering in data exchange amounts to rewriting a query over the target schema to another query that, over a materialized target instance, gives the result that is semantically consistent with the source (specifically, the “certain answers”). Basic questions are then: (1) how do these solutions compare in terms of query rewriting? and (2) how can we determine whether a query is rewritable over a particular solution? Our goal is to answer these questions. Our first main result is that, in terms of rewritability by relational algebra queries, the core is strictly less expressive than the canonical universal solution, which in turn is strictly less expressive than the source. To develop techniques for proving queries non-rewritable, we establish structural properties of solutions; in fact they are derived from the technical machinery developed in the rewritability proofs. Our second result is that both the canonical universal solution and the core preserve the local structure of the data, and that every target query rewritable over any of these solutions cannot distinguish tuples whose neighborhoods in the source are similar. This gives us a first simple tool for checking whether a query is non-rewritable over the canonical universal solution or over the core. We also show that these tools generalize to arbitrary transformations that preserve the local structure of the data, and investigate an alternative semantics of query answering in data exchange.

TCS Journal 2005 Journal Article

Data exchange: semantics and query answering

• Ronald Fagin
• Phokion G. Kolaitis
• Renée J. Miller
• Lucian Popa

Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema that reflects the source data as accurately as possible. In this paper, we address foundational and algorithmic issues related to the semantics of data exchange and to the query answering problem in the context of data exchange. These issues arise because, given a source instance, there may be many target instances that satisfy the constraints of the data exchange problem. We give an algebraic specification that selects, among all solutions to the data exchange problem, a special class of solutions that we call universal. We show that a universal solution has no more and no less data than required for data exchange and that it represents the entire space of possible solutions. We then identify fairly general, yet practical, conditions that guarantee the existence of a universal solution and yield algorithms to compute a canonical universal solution efficiently. We adopt the notion of the “certain answers” in indefinite databases for the semantics for query answering in data exchange. We investigate the computational complexity of computing the certain answers in this context and also address other algorithmic issues that arise in data exchange. In particular, we study the problem of computing the certain answers of target queries by simply evaluating them on a canonical universal solution, and we explore the boundary of what queries can and cannot be answered this way, in a data exchange setting.

SODA Conference 2003 Conference Paper

Comparing top k lists

• Ronald Fagin
• Ravi Kumar 0001
• D. Sivakumar 0001

TCS Journal 2000 Journal Article

A formula for incorporating weights into scoring rules

• Ronald Fagin
• Edward L. Wimmers

A “scoring rule” is an assignment of a value to every tuple (of varying sizes). This paper is concerned with the issue of how to modify a scoring rule to apply to the case where weights are assigned to the importance of each argument. We give an explicit formula for incorporating weights that can be applied no matter what the underlying scoring rule is. The formula is surprisingly simple, in that it involves far fewer terms than one might have guessed. It has three further desirable properties. The first desirable property is that when all of the weights are equal, then the result is obtained by simply using the underlying scoring rule. Intuitively, this says that when all of the weights are equal, then this is the same as considering the unweighted case. The second desirable property is that if a particular argument has zero weight, then that argument can be dropped without affecting the value of the result. The third desirable property is that the value of the result is a continuous function of the weights. We show that if these three desirable properties hold, then under one additional assumption (a type of local linearity), our formula gives the unique possible answer.

STOC Conference 2000 Conference Paper

Query strategies for priced information (extended abstract)

• Moses Charikar
• Ronald Fagin
• Venkatesan Guruswami
• Jon M. Kleinberg
• Prabhakar Raghavan
• Amit Sahai

STOC Conference 2000 Conference Paper

Random walks with "back buttons" (extended abstract)

• Ronald Fagin
• Anna R. Karlin
• Jon M. Kleinberg
• Prabhakar Raghavan
• Sridhar Rajagopalan
• Ronitt Rubinfeld
• Madhu Sudan 0001
• Andrew Tomkins

CSL Conference 1998 Conference Paper

Spectra with Only Unary Function Symbols

• Arnaud Durand 0001
• Ronald Fagin
• Bernd Loescher

Abstract The spectrum of a first-order sentence is the set of cardinalities of its finite models. This paper is concerned with spectra of sentences over languages that contain only unary function symbols. In particular, it is shown that a set S of natural numbers is the spectrum of a sentence over the language of one unary function symbol precisely if S is an eventually periodic set.

STOC Conference 1998 Conference Paper

The Closure of Monadic NP (Extended Abstract)

• Miklós Ajtai
• Ronald Fagin
• Larry J. Stockmeyer

TCS Journal 1997 Journal Article

On winning strategies in Ehrenfeucht-Fraïssé games

• Sanjeev Arora
• Ronald Fagin

We present a powerful and versatile new sufficient condition for the second player (the “duplicator”) to have a winning strategy in an Ehrenfeucht-Fraïssé game on graphs. We accomplish two things with this technique. First, we give a simpler and much easier-to-understand proof of Ajtai and Fagin's result that reachability in directed finite graphs is not in monadic NP. (Monadic NP, otherwise known as monadic ∑1 1, corresponds to existential second-order logic with the restriction that the second-order quantifiers range only over sets, and not over relations of higher arity, such as binary relations.) Second, we show that this result holds in the presence of a larger class of built-in relations than was known before.

TARK Conference 1996 Conference Paper

Common Knowledge Revisited

• Ronald Fagin
• Joseph Y. Halpern
• Yoram Moses
• Moshe Y. Vardi

We consider the common-knowledge paradox raised in [HM90]: common knowledge is necessary for coordination, but common knowledge is unattainable in the real world because of temporal imprecision. We discuss two solutions to this paradox: (1) modeling the world with a coarser granularity, and (2) relaxing the requirements for coordination.

AIJ Journal 1995 Journal Article

A nonstandard approach to the logical omniscience problem

• Ronald Fagin
• Joseph Y. Halpern
• Moshe Y. Vardi

We introduce a new approach to dealing with the well-known logical omniscience problem in epistemic logic. Instead of taking possible worlds where each world is a model of classical propositional logic, we take possible worlds which are models of a nonstandard propositional logic we call NPL, which is somewhat related to relevance logic. This approach gives new insights into the logic of implicit and explicit belief considered by Levesque and Lakemeyer. In particular, we show that in a precise sense agents in the structures considered by Levesque and Lakemeyer are perfect reasoners in NPL.

AAAI Conference 1994 Conference Paper

An Operational Semantics for Knowledge Bases

• Ronald Fagin
• Yoram Moses

The standard approach in AI to knowledge representation is to represent an agent’ s knowledge symbolically as a collection of formulas, which we can view as a knowledge base. An agent is then said to know a fact if it is provable from the formulas in his knowledge base. Halpern and Vardi advocated a model-theoretic approach to knowledge representation. In this approach, the key step is representing the agent’ s knowledge using an appropriate semantic model. Here, we model knowledge bases operationally as multi-agent systems. Our results show that this approach offers significant advantages.

TCS Journal 1993 Journal Article

Finite-model theory - a personal perspective

• Ronald Fagin

Finite-model theory is a study of the logical properties of finite mathematical structures. This paper is a very personalized view of finite-model theory, where the author focuses on his own personal history, and results and problems of interest to him, especially those springing from work in his Ph. D. thesis. Among the topics discussed are: 1. Differences between the model theory of finite structures and infinite structures. Most of the classical theorems of logic fail for finite structures, which gives us a challenge to develop new concepts and tools, appropriate for finite structures. 2. The relationship between finite-model theory and complexity theory. Surprisingly enough, it turns out that, in some cases, we can characterize complexity classes (such as NP) in terms of logic, where there is no notion of machine, computation, or time. 3. 0–1 laws. There is a remarkable phenomenon which says that certain properties (such as those expressible in first-order logic) are either almost surely true or almost surely false. 4. Descriptive complexity theory. Here we consider how complex a formula must be to express a given property. In recent years, there has been a re-awakening of interest in finite-model theory. One goal of this paper is to help “fan the flames” of interest, by introducing more researchers to this fascinating area.

TARK Conference 1992 Conference Paper

The Expressive Power of the Kierarchical Approach to Modeling Knowledge and Common Knowledge

• Ronald Fagin
• John Geanakoplos
• Joseph Y. Halpern
• Moshe Y. Vardi

One approach to representing knowledge or belief of agents, which has been explored independently by economists (BSge and Eisele; Mertens and Zamir; Brandenburger and Dekel; Tan and Werlang) and by computer scientists (Fagin, Halpern, and Vardi) involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs about the state of the world, his beliefs about other agents' beliefs about the worlds, his beliefs about other agents' beliefs about other agents' beliefs about the worlds, etc. Economists and computer scientists differ, however, in the way they model beliefs. Economists prefer a probability-based framework, where belief is modeled as a probability distribution on the uncertainty space. In contrast, computer scientists prefer an information-based framework, where belief is modeled as a subset of the underlying space. The idea is that whatever is in the subset is believed to be possible, and whatever is not in the subset is believed to be impossible. We consider the question of when such an infinite hierarchy completely describes the uncertainty of the agents. We provide various necessary and sufficient conditions for this property. It turns out that the probability-based approach can be viewed as satisfying one of these conditions, which explains why the infinite hierarchy always completely describes the uncertainty of the agents in the probability-based approach. An interesting consequence of our conditions is that adequacy of an infinite hierarchy may depend on the "richness" of the states in the underlying state space. We also consider the question of whether an infinite hierarchy completely describes the uncertainty of the agents with respect to "interesting" sets of events and show that the answers depends on the definition of "interesting".

AIJ Journal 1992 Journal Article

Two views of belief: belief as generalized probability and belief as evidence

• Joseph Y. Halpern
• Ronald Fagin

Belief functions are mathematical objects defined to satisfy three axioms that look somewhat similar to the Kolmogorov axioms defining probability functions. We argue that there are (at least) two useful and quite different ways of understanding belief functions. The first is as a generalized probability function (which technically corresponds to the inner measure induced by a probability function). The second is as a way of representing evidence. Evidence, in turn, can be understood as a mapping from probability functions to probability functions. It makes sense to think of updating a belief if we think of it as a generalized probability. On the other hand, it makes sense to combine two beliefs (using, say, Dempster's rule of combination) only if we think of the belief functions as representing evidence. Many previous papers have pointed out problems with the belief function approach; the claim of this paper is that these problems can be explained as a consequence of confounding these two views of belief functions.

I&C Journal 1990 Journal Article

A logic for reasoning about probabilities

• Ronald Fagin
• Joseph Y. Halpern
• Nimrod Megiddo

We consider a language for reasoning about probability which allows us to make statements such as “the probability of E 1 is less than 1 3 ” and “the probability of E 1 is at least twice the probability of E 2, ” where E 1 and E 2 are arbitrary events. We consider the case where all events are measurable (i. e. , represent measurable sets) and the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) Nilsson's probabilistic logic. As we show elsewhere, the general (nonmeasurable) case corresponds precisely to replacing probability measures by Dempster-Shafer belief functions. In both cases, we provide a complete axiomatization and show that the problem of deciding satisfiability is NP-complete, no worse than that of propositional logic. As a tool for proving our complete axiomatizations, we give a complete axiomatization for reasoning about Boolean combinations of linear inequalities, which is of independent interest. This proof and others make crucial use of results from the theory of linear programming. We then extend the language to allow reasoning about conditional probability and show that the resulting logic is decidable and completely axiomatizable, by making use of the theory of real closed fields.

UAI Conference 1990 Conference Paper

A new approach to updating beliefs

• Ronald Fagin
• Joseph Y. Halpern

We define a new notion of conditional belief, which plays the same role for Dempster-Shafer belief functions as conditional probability does for probability functions. Our definition is different from the standard definition given by Dempster, and avoids many of the well-known problems of that definition. Just as the conditional probability Pr (lB) is a probability function which is the result of conditioning on B being true, so too our conditional belief function Bel (lB) is a belief function which is the result of conditioning on B being true. We define the conditional belief as the lower envelope (that is, the inf) of a family of conditional probability functions, and provide a closed form expression for it. An alternate way of understanding our definition of conditional belief is provided by considering ideas from an earlier paper [Fagin and Halpern, 1989], where we connect belief functions with inner measures. In particular, we show here how to extend the definition of conditional probability to non measurable sets, in order to get notions of inner and outer conditional probabilities, which can be viewed as best approximations to the true conditional probability, given our lack of information. Our definition of conditional belief turns out to be an exact analogue of our definition of inner conditional probability.

TARK Conference 1990 Conference Paper

A Nonstandard Approach to the Logical Omniscience Problem

• Ronald Fagin
• Joseph Y. Halpern
• Moshe Y. Vardi

We introduce a new approach to dealing with the well-known logical omniscience problem in epistemic logic. Instead of taking possible worlds where each world is a model of classical propositional logic, we take possible worlds which are models of a nonstandard propositional logic we call NPL, which is somewhat related to relevance logic. This approach gives new insights into the logic of implicit and explicit'belief considered by Levesque and Lakemeyer. In particular, we show that in a precise sense agents in the structures considered by Levesque and Lakemeyer are perfect reasoners in NPL.

FOCS Conference 1988 Conference Paper

Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)

• Miklós Ajtai
• Ronald Fagin

It is shown that for directed graphs, reachability can not be expressed by an existential monadic second-order sentence. The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic. However, it is shown that for directed graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence. One reason for the interest in the main result is that while there is considerable empirical evidence (in terms of the efficiency of algorithms that have been discovered) that reachability in directed graphs is 'harder' than reachability in undirected graphs, this is the first proof in a precise technical sense that this is so. >

TARK Conference 1988 Conference Paper

Reasoning about Knowledge and Probability

• Ronald Fagin
• Joseph Y. Halpern

We provide a model for reasoning about knowledge anti probability together. We a. llow explicit mention of probabilities in formulas, so that our language has formulas tha. t essentia. lly say "a. ccording to agent i, formula. (p holds with probability a. t least o~. " The language is powerfid enough to allow reasoning a~bout higher-order probabilities, as well as allowing explicit comparisons of the probabilities an agent places on distinct events. We present a general framework for interpreting such formulas, a. nd consider various properties that might hold of the interrelationship between agents' subjective probability spaces at different states. We provide a. complete a. xiomatiza. tion for rea. soning about knowledge a. nd probability, prove a. small model property, and obtain decision procedures. We then consider the effects of adding common knowledge and a. probabilistic va. ria. nt of common knowledge to the language.

AIJ Journal 1987 Journal Article

Belief, awareness, and limited reasoning

• Ronald Fagin
• Joseph Y. Halpern

Several new logics for belief and knowledge are introduced and studied, all of which have the property that agents are not logically omniscient. In particular, in these logics, the set of beliefs of an agent does not necessarily contain all valid formulas. Thus, these logics are more suitable than traditional logics for modelling beliefs of humans (or machines) with limited reasoning capabilities. Our first logic is essentially an extension of Levesque's logic of implicit and explicit belief, where we extend to allow multiple agents and higher-level belief (i. e. , beliefs about beliefs). Our second logic deals explicitly with “awareness, ” where, roughly speaking, it is necessary to be aware of a concept before one can have beliefs about it. Our third logic gives a model of “local reasoning, ” where an agent is viewed as a “society of minds, ” each with its own cluster of beliefs, which may contradict each other.

TARK Conference 1986 Conference Paper

Knowledge and Implicit Knowledge in a Distributed Environment: Preliminary Report

• Ronald Fagin
• Moshe Y. Vardi

AAAI Conference 1986 Conference Paper

What Can Machines Know? On the Epistemic Properties of Machines

• Ronald Fagin

It has been argued that knowledge is a useful tool for designing and analyzing complex systems in AI. The notion of knowledge that seems most relevant in this context is an external, information-based notion that can be shown to satisfy all the axioms of the modal logic S5. We carefully examine the properties of this notion of knowledge, and show that they depend crucially, and in subtle ways, on assumptions we make about the system. We present a formal model in which we can capture the types of assumptions frequently made about systems (such as whether they are deterministic or nondeterministic, whether knowledge is cumulative, and whether or not the environment affects the transitions of the system). We then show that under some assumptions certain states of knowledge are not attainable, and the axioms of S5 do not completely characterize the properties of knowledge; extra axioms are needed. We provide complete axiomatizations for knowledge in a number of cases of interest.

STOC Conference 1985 Conference Paper

An Internal Semantics for Modal Logic: Preliminary Report

• Ronald Fagin
• Moshe Y. Vardi

IJCAI Conference 1985 Conference Paper

Belief, Awareness, and Limited Reasoning: Preliminary Report

• Ronald Fagin
• Joseph Y. Halpern

TCS Journal 1985 Journal Article

Bounded-depth, polynomial-size circuits for symmetric functions

• Ronald Fagin
• Maria M. Klawe
• Nicholas J. Pippenger
• Larry Stockmeyer

Let F = {f 1, f 2, …} be a family of symmetric Boolean functions, where f n has n Boolean variables, for each n ⩾ 1. Let μ F (n) be the minimum number of variables of f n that each have to be set to constant values so that the resulting function is a constant function. We show that the growth rate of μ F (n) completely determines whether or not the family F is ‘good’, that is, can be realized by a family of constant-depth, polynomial-size circuits (with unbounded fan-in). Furthermore, if μ F (n) ⩽ (log n) k for some k, then the family F is good. However, if μ F (n) ⩾ n ϵ for some ϵ > 0, then the family is not good.

FOCS Conference 1984 Conference Paper

A Model-Theoretic Analysis of Knowledge: Preliminary Report

• Ronald Fagin
• Joseph Y. Halpern
• Moshe Y. Vardi

Understanding knowledge is a fundamental issue in many disciplines. In computer science, knowledge arises not only in the obvious contexts (such as knowledge-based systems), but also in distributed systems (where the goal is to have each processor "know" something, as in Byzantine agreement). A general semantic model of knowledge is introduced, to allow reasoning about statements such as "He knows that I know whether or not she knows whether or not it is raining. " This approach more naturally models a state of knowledge than previous proposals (including Kripke structures). Using this notion of model, a model theory for knowledge is developed. This theory enables one to interpret such notions as a "finite amount of information" and "common knowledge" in different contexts.

TCS Journal 1981 Journal Article

A note on the existence of continuous functionals

• J.Lawrence Carter
• Ronald Fagin

Let if P = {p i |iϵI} and if Q = {q i |iϵI} be sets of partial functions with the same index set I. We say that Φ is an interpolating function (from P to Q) if if Φ(p i = q i for each i. We give simple necessary and sufficient conditions for the existence of a monotone interpolating functional. We show that these same conditions are necessary and sufficient for the existence of a continuous interpolating functional if the index set I is finite, but that they are not sufficient if the index set is infinite

STOC Conference 1981 Conference Paper

Properties of Acyclic Database Schemes

• Catriel Beeri
• Ronald Fagin
• David Maier 0001
• Alberto O. Mendelzon
• Jeffrey D. Ullman
• Mihalis Yannakakis

There is a class of database descriptions, involving one “acyclic” join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. Further, this class has many desirable properties. Some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. Other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. It is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. This paper is intended to summarize the results that will appear in more detail in [FMU] and [BFMY].

STOC Conference 1980 Conference Paper

Horn Clauses and Database Dependencies (Extended Abstract)

• Ronald Fagin

In the last year or so, a number of generalizations of these dependencies have appeared: Nicolas's mutual dependencies [Ni], which say that a relation is the join of three of its projections; Rissanen's and Aho, Beeri, and Ullman's join dependencies ([Ri], [ABU]), which generalize further to an arbitrary number of projections; Paradaens' transitive dependencies [Pa], which generalize both FDs and MVDs; Sagiv and Walecka's subset dependencies [SW] which generalize embedded MVDs; and Sadri and Ullman's template dependencies [SU], which generalize embedded join dependencies. The purpose of this paper is to help bring order to the chaos by presenting certain mathematical properties shared by all of these dependencies.