welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

Revision 1 as of 2021-03-12 09:29:23

location: AbstractLaneHemaspaandra

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.