Doctoral Dissertation uoadl:2932687 291 Read counter

Department of Mathematics

Library of the School of Science

Library of the School of Science

2021-01-14

2021

Livieratos John

Ελευθέριος Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών ΕΚΠΑ (επιβλέπων)

Δημήτριος Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)

Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)

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

Δημήτριος Φωτάκης, Αναπληρωτής Καθηγητής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ

Δημήτριος Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)

Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)

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

Δημήτριος Φωτάκης, Αναπληρωτής Καθηγητής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ

Constraint Satisfaction Problems: A Probabilistic Approach and Applications to Social Choice Theory

English

Constraint Satisfaction Problems: A Probabilistic Approach and Applications to Social Choice Theory

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.

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.

Science

Lovasz Local Lemma, Aggregation

No

0

Yes

219

326