'''Computational Social Choice and Computational Complexity: BFFs (Best Friends Forever)?'''

''Lane A. Hemaspaandra

University of Rochester

Abstract:

We discuss the connection between computational complexity and computational social choice (aka "comsoc," which for this talk will
mostly be the study of computational aspects of election systems: who wins, how elections can be manipulatively attacked, etc.). 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, less-known complexity tools often can be very productively used in comsoc.

This is an updated version of a talk first presented in the AAAI 2018 Senior Member Track.  No prior knowledge of computational social
choice or computational complexity is required to understand this talk.