CS Events Monthly View

PhD Defense

Impossibility Theorems and the Universal Algebraic Toolkit


Download as iCal file

Monday, January 26, 2015, 01:00pm


In this dissertation, we elucidate a close connection between the
theory of Judgment Aggregation (more generally, Evaluation
Aggregation), and a relatively young but rapidly growing field of
universal algebra, that was primarily developed to investigate
constraint satisfaction problems. Our connection yields a full
classification of non-binary evaluations into possibility and
impossibility domains both under the idempotent and the supportive
conditions. Prior to the current result E. Dokow and R. Holzman nearly
classified non-binary evaluations in the supportive case, by
combinatorial means. The algebraic approach gives us new insights to
the easier binary case as well, which had been fully classified by the
above authors. We give a classification theorem for the majoritarian
aggregator and show how Sen's well known theorem follows from it. Our
algebraic view lets us put forth a suggestion about a strengthening of
the non-dictatorship criterion, that helps us avoid ``outliers'' like
the affine subspace. Finally, we give upper bounds on the complexity of
computing if a domain is impossible or not (to our best knowledge no
finite time bounds were given earlier).

Speaker: Yixin Xu



Location : CoRE B(Room 305)


Mario Szegedy(Chair), Eric Allender, Mike Saks, Andrei Bulatov (Simon Fraser University)

Event Type: PhD Defense



Rutgers University