Computational Social Choice and Computational Complexity: BFFs?

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 lessrecognized aspects of this connection. Firstly, this is very much a two-way street: Everyone knows complexity classi- fication 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.

Authors

• Lane Hemaspaandra

Keywords

No keywords are indexed for this paper.