Theory Seminar

Impossibility Theorems and the Universal Algebraic Toolkit

Yixin Xu

PhD student
Rutgers University
Friday, May 23, 2014
10:30am - 12:00pm
3941 BBB


About the Event

We elucidate a close connection between the Theory of Judgment Aggregation and a relatively young but rapidly growing field of universal algebra, that was primarily developed to investigate constraint satisfaction problems. We show that theorems in the above field translate (often directly) to impossibility, classification and robustness theorems in social choice theory. We refine the classification of E. Dokow, R. Holzman of binary evaluations, complete their classification theorem for non-binary evaluations, give a new classification theorem for the majoritarian aggregator and show how Sen's well known theorem follows from it, define new aggregator classes and also prove theorems about them. We also give upper bounds on the complexity of computing if a domain is impossible or not. Joint with Mario Szegedy


Yixin Xu is a PhD student in the Computer Science department at Rutgers University under the supervision of Mario Szegedy. His main interests are the algebraic theory of constant satisfaction problems and quantum computing. He has received the best student paper award in the 8th International Computer Science Symposium in Russia, CSR 2013.

Additional Information

Contact: Yaoyun Shi

Sponsor: CSE

Open to: Public