THEORY CANAL: The Rochester Theory Seminar Series 2009-2010
The THEORY CANAL meeting (the Rochester Theory Seminar) is a joint project of the RIT and UR theory groups, and the focus is all areas of theoretical computer science. THEORY CANAL meets (when RIT and UR classes are in session) on the first and third Monday (and usually, when a fifth exists, the fifth Monday) of each month. (Due to slot demand, school holidays, and religious holidays, there are sometimes exceptions to that rule: Mondays of that form that we skip and Mondays not of that form that we don't skip. So see the schedule below for the actual dates.) The talks start at 12:30PM and typically take 60 to 75 minutes.
The meetings this semester will be held in Room 703, Computer Studies Building, University of Rochester, Rochester, NY 14627.
The meetings are open to the public; all are very welcome.
Chronological list of 12:30PM THEORY CANAL talks for the
2009-2010 academic year:
Speaker: Piotr Faliszewski, AGH University Krakow
Topic: Multimode Control Attacks on Elections
In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections---attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.
This talk is based on joint work with Edith Hemaspaandra and Lane A. Hemaspaandra.
Speaker: Daniel Stefankovic, UR
Topic: Crossing numbers
Crossing numbers of graphs are important, yet inadequately understood. To learn more about the concept diverse variants (geometric, topological, and algebraic) were proposed by Mohar, Pach, Toth, and Tutte. I will describe the known connections as well as some new results (joint work with Marcus Schaefer and Michael Pelsmajer).
Speaker: Qi Ge, UR
Topic: On approximately counting independent sets in bipartite graphs
Counting independent sets is proved to be #P-hard even in planar bipartite graphs, however whether there is a fully polynomial randomized approximation scheme remains open. In this work, we investigate the problem of approximately counting independent sets in bipartite graphs. This is a joint work with Daniel Stefankovic.
Speaker: Mark Wilson, University of Auckland
Speaker: Curtis Menton, RIT
Topic: Range Voting is Resistant to Control
Social choice theory is concerned with developing and evaluating voting systems, both for the use of political and organizational elections and for use as decision making process for multiagent systems. Particularly in the context of multiagent systems, computational resistance to various types of control has become a desired property of a voting system. Though manipulative actions may always be possible, strong computational barriers to efficient control can give us sufficient confidence in the integrity of an election.
Range Voting is a natural extension of approval voting that is resistant to a large number of cases of control. In particular, the variant Normalized Range Voting has the largest number of control resistances among natural voting systems.
Speaker: Aris Pagourtzis, National Technical University of Athens
Speaker: Ivona Bezakova, RIT