Home
Resource
Impossibility theorems and the universal algebraic toolkit
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(530.20 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Xu, Yixin. Impossibility theorems and the universal algebraic toolkit. Retrieved from https://doi.org/doi:10.7282/T35M67QF

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleImpossibility theorems and the universal algebraic toolkit
NameXu, Yixin (author); Szegedy, Mario (chair); Allender, Eric (internal member); Saks, Michael (internal member); Bulatov, Andrei (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2015
Other Date2015-10 (degree)
SubjectComputer Science, Algebra
Extent1 online resource (vii, 78 p. : ill.)
DescriptionIn this dissertation, we elucidate a close connection between the theory of Evaluation Aggregation, and a subfield of universal algebra, that was recently applied 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 deciding if a domain is impossible or not (to our best knowledge no finite time bounds were given earlier).
NotePh.D.
NoteIncludes bibliographical references
Noteby Yixin Xu
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T35M67QF
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024