Computational Social Choice and Computational Complexity: BFFs?

AAAI 2018 pp. 7971-7977

doi:10.1609/AAAI.V32I1.12220 /aaai/2018/hemaspaandra2018aaai-computational/

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.

PDF AAAI Semantic Scholar

Cite

Text

Hemaspaandra. "Computational Social Choice and Computational Complexity: BFFs?." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.12220

Markdown

[Hemaspaandra. "Computational Social Choice and Computational Complexity: BFFs?." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/hemaspaandra2018aaai-computational/) doi:10.1609/AAAI.V32I1.12220

BibTeX

@inproceedings{hemaspaandra2018aaai-computational,
  title     = {{Computational Social Choice and Computational Complexity: BFFs?}},
  author    = {Hemaspaandra, Lane A.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {7971-7977},
  doi       = {10.1609/AAAI.V32I1.12220},
  url       = {https://mlanthology.org/aaai/2018/hemaspaandra2018aaai-computational/}
}