as a shield and seeking holes in and
paths around that shield is a natural,
exciting part of the drama of science,
and is likely to continue for decades to
come as new models, techniques, and
attacks are formulated and studied.
This study will clearly benefit from the
broadest possible participation, and
we urge any interested readers—and
most especially those early in their
careers—to bring their own time and
skills to bear on the many problems
that glimmer in the young, important,
challenging study of the complexity of
elections.
acknowledgments
We are deeply grateful to Preetjot
Singh, Communications editors Georg
Gottlob, Moshe Vardi, and Andrew Yao,
and the anonymous referees for helpful suggestions and encouragement.
Piotr Faliszewski was supported
in part by Polish Ministry of Science
and Higher Education grant N-N206-
378637, AGH-UST grant 11. 11.120.865,
and by the Foundation for Polish Sci-ence's Homing Program. Edith Hemaspaandra was supported in part
by NSF grant IIS-0713061 and a Friedrich Wilhelm Bessel Research Award
from the Alexander von Humboldt
Foundation. Lane A. Hemaspaandra
was supported in part by NSF grants
CCF-0426761 and CCF-0915792 and
a Friedrich Wilhelm Bessel Research
Award from the Alexander von Humboldt Foundation.
References
1. ajtai, m. Worst-case complexity, average-case
complexity and lattice problems. Documenta
Mathematica, extra Volume Icm III (1998), 421–428.
2. Bartholdi, III, J. and orlin, J. single transferable vote
resists strategic voting. Social Choice and Welfare 8, 4
(1991) 341–354.
3. Bartholdi, III, J., tovey, c. and trick, m. the
computational difficulty of manipulating an election.
Social Choice and Welfare 6, 3 (1989) 227–241.
4. Bartholdi, III, J., tovey, c. and trick, m. Voting
schemes for which it can be difficult to tell who won
the election. Social Choice and Welfare 6, 2 (1989),
157–165.
5. Bartholdi, III, J., tovey, c. and trick, m. How hard is
it to control an election? Mathematical and Computer
Modeling 16, 8/9 (1992), 27–40.
6. Betzler, n., fellows, m., guo, J., niedermeier, r. and
rosamond, f. fixed-parameter algorithms for Kemeny
scores. In Proceedings of the 4th International
Conference on Algorithmic Aspects in Information
and Management. Lecture notes in computer science
#5034 (June 2008). springer-Verlag, 60–71.
7. Betzler, n., guo, J., niedermeier, r. parameterized
computational complexity of Dodgson and young
elections. In Proceedings of the 11th Scandinavian
Workshop on Algorithm Theory. Lecture notes in
computer science #5124 (July 2008). springer-Verlag, 402–413.
8. Brelsford, e., faliszewski, p., Hemaspaandra, e.,
schnoor, H., and schnoor, I. approximability of
manipulating elections. In Proceedings of the 23rd
AAAI Conference on Artificial Intelligence (July
2008). aaaI press, 44–49.
Piotr Faliszewski ( faliszew@agh.edu.pl) is an assistant
professor at the agH university of science and
technology, Kraków, poland.
Edith hemaspaandra ( eh@cs.rit.edu) is a professor at
the rochester Institute of technology, rochester, ny.
Lane A. hemaspaandra ( lane@cs.rochester.edu) is a
professor at the university of rochester, rochester, ny.
© 2010 acm 0001-0782/10/1100 $10.00