Dissertation committee:
Ελευθέριος Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών ΕΚΠΑ (επιβλέπων)
Δημήτριος Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)
Josep Díaz, Professor Emeritus, Department of Computer Science, Universitat Politècnica de Catalunya
Marcel Fernandez, Associate Professor, Telecommunications, Engineering School of Barcelona, Universitat Politècnica de Catalunya
Φωκίων Κολαΐτης, Distinguished Research Professor, Computer Science and Engineering Department, University of California, Santa Cruz
Δημήτριος Φωτάκης, Αναπληρωτής Καθηγητής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Summary:
In this Ph.D thesis, we work in one of the most well studied class of problems
in Computer Science, that of Constraint Satisfaction Problems (CSPs). In
one of their usual formulations, CSPs consist of a set of variables that take
values in a common domain set. Groups of variables are tied by constraints
that restrict the possible combinations of values that the variables can have
in a solution. In such a setting, there are many objectives that one might be
interested in: checking if there is a solution, finding or approximating one,
or considering how fast an algorithmic procedure can do all that.
The framework of CSPs is broad enough to model a great number of in-
teresting problems in computer science, like the satisfiability of propositional
formulas and graph coloring problems. It is also a very developed field on its
own accord, with a lot of interesting results that classify the computational
complexity of classes of CSPs and delineate the bounds between tractability
and NP-hardness. The machinery used to tackle such problems is broad,
including polynomial-time algorithms that solve classes of CSPs, random-
ized ones that find or approximate solutions given some conditions that the
CSP in question must satisfy and algebraic manipulations that allow us to
relate their computational complexity with structural properties of their sets
of constraints.
We begin with an overview of various approaches to CSPs: defining them
in the language of Propositional, First or Second Order Logic and via homo-
morphisms and we consider the subclass of multi-sorted CSPs, that is CSPs
whose variables are divided in different sorts and take values in independent
domains. Some of these variations are discussed to show the versatility of
CSPs and provide some context to our work, while others are utilized to
prove our results.
The first part of our results concerns what is known as the probabilistic
approach. Here, we devise randomized algorithms that (i) prove conditions
56
that guarantee the existence of solutions to a given instance of a CSP and (ii)
in case a solution exists, find it efficiently. A solution in this setting is usually
expressed as a point in a probability space such that no event, from a set of
events that are deemed as “undesirable”, occurs. We work with the seminal
Lovász Local Lemma (LLL) and its variation, Shearer’s Lemma, which, given
some bounds concerning the probabilities of undesirable events and the way
these events depend on each other, provide conditions that imply all the
events can be avoided with positive probability. A solution in this setting,
is a point in a probability space such that none of the events occur. All
our work is situated in the variable framework of Moser and Tardos, where
the events are assumed to be defined upon independent random variables.
Although this is a restriction of the general setting, it is a broad framework
that easily translates to the language of CSPs and that is particularly handy
for algorithmic purposes.
Specifically, we define two new notions of dependency between the events,
the variable-directed lopsidependency (VDL) and the directed dependency (d-
dependency), which are specifically tailored to facilitate the algorithmic ma-
nipulation of events that are negatively correlated. It is quite common in
practice to depict dependencies between the events by a dependency graph,
where the nodes correspond to the events and unconnected events are con-
sidered independent. We thus discuss how the directed dependency graphs
that our notions give rise to, relate with other such graphs in the bibliogra-
phy. Furthermore, we show that the d-dependency condition gives rise to a
sparser dependency graph than other known such conditions in the variable
framework, thus allowing for stronger versions of the LLL to be proven.
We then proceed to prove the simple version of the LLL of the VDL
condition. That is, we design an algorithm which, if the probabilities of
the events are upper bounded by a common number p ∈ [0, 1), the VDL
graph has maximum degree d and epd ≤ 1, efficiently finds a point in the
probability space such that none of the events occur, thus showing at the
same time that such a point must exist in the first place. We also prove the
more general asymmetric version of the LLL for the d-dependency graph,
where the probability of each event is bounded by a number relating to the
probabilities of the events depending on it. We then prove the even stronger
Shearer’s lemma for the underlying undirected graph of the d-dependency
one, which bounds the probabilities of the events by polynomials defined
over the independent sets of the graph.
The proofs for these versions of the LLL and Shearer’s lemma employ a7
direct probabilistic approach, in which we show that the probability that our
algorithms last for at least n steps is inverse exponential to n, by express-
ing it by a recurrence relation which we subsequently solve using advanced
analytic tools, such as Bender and Richmond’s Lagrange Inversion Formula
and Gelfand’s Formula for the spectral radius of matrices. In contrast, most
extant work bounds only the expectation of the steps performed by such
algorithms. We believe that this fact is interesting in each own accord. Nev-
ertheless, we have applied our method in two interesting combinatorial prob-
lems. First, we show that 2∆ − 1 colors suffice to acyclicaly color the edges
of a graph with maximum degree ∆, that is, we want the resulting coloring
to contain neither incident edges with the same color, nor bichromatic cy-
cles. We thus match the best possible bound for Moser-like algorithms, as
observed by Cai et al. [Acyclic edge colourings of graphs with large girth.
Random Structures & Algorithms, 50(4):511–533, 2017]. We also show how
to explicitly construct binary c-separating codes whose rate matches the op-
timal known one. c-separating codes are M × n matrices over some alphabet
Q, where, in any two sets U and V of at most c rows, there is at least one
column such that the set of elements in U is disjoint with that in V . Al-
though such codes are very useful for applications, explicit constructions are
scarce.
The second part of our results lies in Social Choice Theory and, specifi-
cally, in Judgment Aggregation, where a group of agents collectively decides
a set of issues and where, both the individual positions of each agent and
the aggregated positions (the social outcome) needs to adhere to some re-
strictions that reflect logical consistency requirements. The aim is to find
aggregating procedures that preserve these requirements and do not degen-
erate to dictatorships, that is aggregators that always output the positions
of a specific agent.
Firstly, we consider the case where these restrictions are expressed by a
set of m-ary vectors X over some finite domain D, where m is the number of
issues to be decided. That is, m contains the allowed combinations of votes
over the issues and a vector not in X is deemed “irrational”. In this setting,
we characterize possibility domains, that is sets X where non-dictatorial ag-
gregation is possible, via the types of aggregators they admit. Furthermore,
we provide an analogous characterization for a subclass of possibility do-
mains we named uniform possibility domains, which are domains that admit
aggregators that are not dictatorial even when restricted to any issue and
any binary subset of allowed positions. We also show that uniform possi-8
bility domains give rise to tractable multi-sorted CSPs, while any domain
that is not uniform, gives rise to NP-complete multi-sorted CSPs, thus tying
the possibility of non-dictatorial aggregation with a dichotomy result in the
complexity of multi-sorted CSPs.
We then proceed to consider Boolean such domains, that are given as the
sets of models of propositional formulas, which, in the bibliography, are called
integrity constraints. We provide syntactic characterizations for integrity
constraints that give rise to (uniform) possibility domains and also to domains
admitting a variety of non-dictatorial aggregators with specific properties
that have appeared in the bibliography. We also show how to efficiently
identify integrity constraints of these types and how to efficiently construct
such constraints given a Boolean domain X of the corresponding type.
Finally, we turn our attention to the problem of recognizing if a domain
admits a (uniform) non-dictatorial aggregator. In case X is provided explic-
itly, as a set of m-ary vectors, we design polynomial-time algorithms that
solve this problem. In case X is Boolean and provided either via an integrity
constraint, or, as in the original framework of Judgment Aggregation, as
the set of consistent evaluations of a set of propositional formulas, called an
agenda, we provide upper and lower complexity bounds in the polynomial
hierarchy. We extend these results to include the cases where X admits
non-dictatorial aggregators with desirable properties.
