  The computational complexity of winner determination under common voting
rules is a classical and fundamental topic in the field of computational social
choice. Previous work has established the NP-hardness of winner determination
under some commonly-studied voting rules, especially the Kemeny rule and the
Slater rule. In a recent blue-sky paper, Baumeister, Hogrebe, and Rothe (2020)
questioned the relevance of the worst-case nature of NP-hardness in social
choice and proposed to conduct smoothed complexity analysis (Spielman and Teng
2009) under Blaser and Manthey (2015)'s framework.
  In this paper, we develop the first smoothed complexity results for winner
determination in voting. We illustrate the inappropriateness of Blaser and
Manthey (2015)'s smoothed complexity framework in social choice contexts by
proving a paradoxical result, which states that the exponential-time brute
force search algorithm is smoothed poly-time according to their definition. We
then prove the smoothed hardness of Kemeny and Slater using the classical
smoothed complexity analysis, and prove a parameterized typical-case smoothed
easiness result for Kemeny. Overall, our results show that smoothed complexity
analysis in computational social choice is a challenging and fruitful topic.
