Computational Social Choice and Computational Complexity: BFFs?

Authors

  • Lane Hemaspaandra University of Rochester

Keywords:

computational social choice, computational complexity, classification, search versus decision

Abstract

We discuss the connection between computational social choice (comsoc) and computational complexity. We stress the work so far on, and urge continued focus on, two less-recognized aspects of this connection. Firstly, this is very much a two-way street: Everyone knows complexity classification is used in comsoc, but we also highlight benefits to complexity that have arisen from its use in comsoc. Secondly, more subtle, less-known complexity tools often can be very productively used in comsoc.

Downloads

Published

2018-04-29

How to Cite

Hemaspaandra, L. (2018). Computational Social Choice and Computational Complexity: BFFs?. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/12220