Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for +publisher:"Rutgers University" +contributor:("Bulatov, Andrei"). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Rutgers University

1. Xu, Yixin, 1985-. Impossibility theorems and the universal algebraic toolkit.

Degree: PhD, Computer Science, 2015, Rutgers University

In 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).

Advisors/Committee Members: Szegedy, Mario (chair), Allender, Eric (internal member), Saks, Michael (internal member), Bulatov, Andrei (outside member).

Subjects/Keywords: Algebra

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Xu, Yixin, 1. (2015). Impossibility theorems and the universal algebraic toolkit. (Doctoral Dissertation). Rutgers University. Retrieved from https://rucore.libraries.rutgers.edu/rutgers-lib/48728/

Chicago Manual of Style (16th Edition):

Xu, Yixin, 1985-. “Impossibility theorems and the universal algebraic toolkit.” 2015. Doctoral Dissertation, Rutgers University. Accessed September 20, 2020. https://rucore.libraries.rutgers.edu/rutgers-lib/48728/.

MLA Handbook (7th Edition):

Xu, Yixin, 1985-. “Impossibility theorems and the universal algebraic toolkit.” 2015. Web. 20 Sep 2020.

Vancouver:

Xu, Yixin 1. Impossibility theorems and the universal algebraic toolkit. [Internet] [Doctoral dissertation]. Rutgers University; 2015. [cited 2020 Sep 20]. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/48728/.

Council of Science Editors:

Xu, Yixin 1. Impossibility theorems and the universal algebraic toolkit. [Doctoral Dissertation]. Rutgers University; 2015. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/48728/

.