Vortrag Prof. Dr. Lane A. Hemaspaandra

Date / Time:
17.01.19   /  12:30 - 14:30

Hörsaal 5K, Geb. 25.31


Einladung des Lehrstuhls "Komplexitätstheorie und Kryptologie" zu einem

Vortrag mit dem Thema

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

von Herrn Prof. Dr. Lane A. Hemaspaandra (University of Rochester)


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, more subtle, less-known complexity tools often can be very productively used in comsoc.


Lane A. Hemaspaandra is a professor of computer science at the University of Rochester. He a specialist in the theory of computation and its uses in protecting elections from manipulation. He and his research collaborators have determined the computational complexity of Lewis Carroll's 1876 election system, have constructed election systems that computationally resist all standard attacks, and have proven that there are settings in which quantum computers are almost-everywhere exponentially faster than classical computers. He is an author of more than one hundred refereed journal publications and two textbooks. Lane has been awarded the NSF Presidential Young Investigator Award, the Friedrich Wilhelm Bessel Research Award of the Alexander von Humboldt Foundation, the SIGACT Distinguished Service Prize, and his university's best-teacher award. He serves on the editorial boards of Computational Complexity, Electronic Proceedings in Theoretical Computer Science, Information and Computation (EPTCS), and the Journal of Universal Computer Science, and serves on the advisory boards of the EATCS-Springer Texts in Theoretical Computer Science series, the EATCS-Springer Monographs in Theoretical Computer Science series, and EPTCS. His BS, MS, and PhD degrees are from Yale, Stanford, and Cornell.


Responsible for the content: E-MailWE Informatik