Logic and Random Discrete Structures

Suppose edges in an underlying graph $G$ appear independently with some probability in our observed graph $G^{\prime }$ – or alternately that we can query uniformly random edges. We describe how high a sampling probability we need to infer the modularity of the underlying graph.

Modularity is a function on graphs which is used in algorithms for community detection. For a given graph $G$, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in $G$. The (max) modularity $q^{\ast }(G)$ of the graph $G$ is defined to be the maximum over all vertex partitions of the modularity score, and satisfies $0\le q^{\ast }(G)\le 1$.

In the seminar I will spend time on intuition for the behaviour of modularity, how it can be approximated, links to other graph parameters and to present some open problems.

While the focus of research on Random SAT have been on uniformly distributed instances, several models were suggested, in which the distribution from which instances are sampled is far from uniform. Sometimes such models are motivated by analyzing ‘practical’ distributions, sometimes they appear to be mathematically natural and sound. We study one such model, the Configuration Model, which is parametrized by a distribution of degrees of variables. To sample from this model we start with a set of variables, then for each of them we sample a degree and create the prescribed number of copies. Each copy (or clone) is then negated with probability 1/2, and all the clones are grouped into clauses uniformly at random. We study properties of Random SAT problems generated this way for a wide range of degree distributions.

There are two natural ways to see permutations as models of some logical theory: either as bijections from a set $A$ to itself or as a pair of linear orders on a set $A$. In this talk we discuss the question of finding convergence laws for models of random permutations. In particular, we prove a convergence law for uniform 231-avoiding permutations, seen as pairs of orders.

Property testing (for a property $P$) asks for a given graph, whether it has property $P$, or is “structurally far” from having that property. A “testing algorithm” is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as “extremely efficient”, making them relevant in the context of large data sets.

In this talk I will present recent positive and negative results about testability of properties definable in first-order logic and monadic second-order logic on classes of bounded-degree graphs.

Let $G_n$ be the binomial random graph $G(n,p=c/n)$ in the sparse regime, which as is well-known undergoes a phase transition at $c=1$. Lynch [1] showed that for every first order sentence $\varphi$, the limiting probability that $G_n$ satisfies $\varphi$ as $n\to \mathrm{\infty }$ exists, and moreover it is an analytic function of $c$. In this paper we consider the closure $\overline{L_c}$ in the interval $[0,1]$ of the set $L_c$ of all limiting probabilities of first order sentences in $G_n$. We show that there exists a critical value $c_0\approx 0.93$ such that $\overline{L_c}=[0,1]$ when $c\ge c_0$, whereas $\overline{L_c}$ misses at least one subinterval when .

The Mallows distribution samples a permutation on $1,\mathrm{\dots },n$ at random, where each permutation has probability proportional to $q^{\text{inv}(\pi )}$, where $q>0$ is a parameter and inv(.) denotes the number of inversions of $\pi$. So in particular, setting $q=1$ we retrieve the uniform distribution.

In the talk, I discussed some preliminary results on logical limit laws for Mallows random permutations, using two different logical languages of permutations, called “theory of one bijection” (TOOB) and “theory of two orders” (TOTO) by Albert, Bouvel and Feray.

Clique can be solved in expected FPT time on uniformly distributed graphs of size $n$ while this is not clear for Dominating Set. We show that it is indeed unlikely that Dominating Set can be solved efficiently on random graphs: If yes, then every first-order expressible graph property can be solved in expected FPT time, too. Furthermore, this remains true when we consider random graphs with an arbitrary constant edge probability. There is a very simple problem on random matrices that is equally hard to solve on average: Given a square boolean matrix, are there k rows whose logical AND is the zero vector?

In probabilistic databases the data is uncertain and is modeled by a probability distribution. The central problem in probabilistic databases is query evaluation, which requires performing not only traditional data processing such as joins, projections, unions, but also probabilistic inference in order to compute the probability of each item in the answer. At their core, probabilistic databases are a proposal to integrate logic with probability theory. This talk gives an overview of the probabilistic data models and the main results on query evaluation on probabilistic databases.

One of the challenges in explanations for data-analysis tools is the quantification of the responsibility of individual data items to the overall result. Nowadays a common approach is to deploy concepts from the theory of cooperative games. A primary example is the Shapley value – a conventional and well-studied function for determining the contribution of a player to the coalition. I will describe our recent research on the computation of the Shapley value (and values of a similar nature) of a database tuple as its contribution to the result of a query. It turns out that the complexity of this task has tight connections to the complexity of query evaluation over tuple-independent probabilistic databases. Moreover, this connection highlights the need to understand the complexity of query evaluation in cases where probability assignments are restricted, such as the uniform case where each tuple has the probability 0.5 (and the task is to count the database subsets that satisfy the query). I will present a recent resolution of the uniform case, as well as every case where the probability is fixed in every relation, for an important class of database queries.

Probabilistic databases (PDBs) are usually introduced as probability spaces over the subsets of a finite set of possible facts. Probabilistic query evaluation (PQE) is the problem of finding the probability that a Boolean query evaluates to true on a given PDB. The data complexity of PQE is well-understood for the class of unions of conjunctive queries on tuple-independent PDBs: for every query, the problem can be classified to be either solvable in polynomial time, or is #P-hard [1].

In this talk, we discuss a version of PQE, where both the query evaluation, and the probabilistic databases use a bag semantics. That is, the input PDB may contain duplicates, and the query evaluation takes tuple multiplicities into account. Our main focus lies on self-join free conjunctive queries where we obtain a dichotomy similar to the one above. This is achieved by combining known results for the set version of the problem with novel techniques that are required to handle distributions over multiplicities.

How to represent limits of networks? In this survey, several kinds of limits are considered: elementary limits, left limits, local limits, and structural limits, as well as different types of limits objects (distributional or analytical). A particular attention is given to the notion of structural limits, based on the convergence of the satisfaction probabilities of first-order formulas, which generalize classical notions and offers a both a distributional limit objects (as a probability distribution on a Stone space) and an analytic limit object (a modeling, which is a totally Borel structure on a standard probability space).

Semiring semantics evaluates logical statements by values in some commutative semiring $K$, and random semiring interpretations, induced by a probability distribution on $K$, generalise random structures. In this talk, we investigate how the classical 0-1 laws of Glebskii et al. and Fagin generalise to semiring semantics.

Using algebraic representations of FO-formulae, we show that for many semirings, including min-max-semirings and the natural semiring, 0-1 laws hold under reasonable assumptions on the probability distribution. We can further partition the FO-sentences into classes ${({\mathrm{\Phi }}_j)}_{j\in K}$ for all semiring elements $j$, such that all sentences in ${\mathrm{\Phi }}_j$ almost surely evaluate to $j$ in random semiring interpretations. For finite min-max and lattice semirings, this partition actually collapses to just three classes ${\mathrm{\Phi }}_0$, ${\mathrm{\Phi }}_1$ and ${\mathrm{\Phi }}_{\epsilon }$ of sentences that, respectively, almost surely evaluate to 0, to the greatest semiring value 1, and to the smallest non-zero value $\epsilon$. Computing this almost sure valuation is a Pspace-complete problem.

We present a variant of the parallel Moser-Tardos Algorithm [1] and show that, for a class of problems whose dependency graphs have some subexponential growth, the expected number of random bits used by the algorithm is constant. In particular the expected number of used random bits is independent from the total number of variables. This is achieved by using the same random bits to resample variables which are far enough in the dependency graph.

Distributions over rankings are used to model user preferences in elections, commerce, and more. The Repeated Insertion Model (RIM) gives rise to various known probability distributions over rankings, in particular to the popular Mallows model. However, probabilistic inference over RIM is provably intractable in the general case. In this talk, I will describe an algorithm for computing the marginal probability of an arbitrary partially ordered set over RIM. The complexity of the algorithm is captured in terms of a new measure termed the “cover width”. I will briefly discuss an application of RIM for the task of estimating the probability of an outcome in an election over probabilistic votes.

Noisy or inconsistent databases that violate one or more integrity constraints expected to hold on the database are abundant in practice. First, I will discuss the complexity of computing an optimal “repair” for an inconsistent database where integrity constraints are Functional Dependencies, both in terms of “subset repairs” (by a minimum number of tuple deletion) and “update repairs” (by a minimum number of value or cell updates), and draw a connection to the complexity of the “most probable database” problem. Then I will discuss theoretical properties of “measures” of inconsistencies in a database where integrity constraints are violated, which can be useful for reliability estimation for datasets and progress indication in data repair.

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.

This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobás, and Morris [1] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Finally, it provides a model-theoretic characterization of classes with bounded twin-width.