THEORY CANAL: The Rochester Theory Seminar Series 2013-2014 |
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 Mondays 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 (exceptions if any will be noted in the detailed list below) start at 12:30PM, and typically run 50-60 minutes. (Of course, plans can change and at the start of the year some of the listings may be tentative; so please make sure you are subscribed to the Theory Canal mailing list---how to do so is described below---so that you hear of all changes in speakers/topics/etc.!)
The Meetings this year will be held (except as noted otherwise below) 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 THEORY CANAL talks for the
2013-2014 academic year:
Speaker: Gabor Erdelyi, University of Siegen, Germany
Topic: Algorithms and Elections
This talk aims to provide a general overview of the computational aspects of elections. Its main focus will be on the complexity of problems that model various ways of tampering with the outcome of an election, such as manipulation, control, and bribery. Each of these actions are very different in nature: while manipulation concerns the insincere behavior on the part of one or several voters, in control settings the election's chair seeks to change the outcome of an election by making structural changes in the election such as adding/deleting/partitioning either candidates or voters, and finally, bribery is given if an external agent attempts to change one or several voters' votes. These manipulative actions will be examined in the context of several voting systems, with one example being fallback voting, proposed by Brams and Sanver (2006), which - being computationally resistant to 20 of the 22 common types of control - is the system currently known to display the broadest resistance to control among all natural voting systems with an easy winner determination procedure.
Speaker: Scott Ames, UR
Topic:
TBA
Speaker: Henning Schnoor, University of Kiel, Germany
Topic:
Deciding Epistemic and Strategic Properties of Cryptographic
Protocols
We propose a new, widely applicable model for analyzing knowledge-based (epistemic) and strategic properties of cryptographic protocols. We prove that the corresponding model checking problem with respect to an expressive epistemic strategic logic is decidable. As corollaries, we obtain decidability of complex security properties including coercion-resistance of voting protocols, accountability of protocols using a trusted third party, and abuse-freeness of contract signing protocols.
Speaker: Joerg Rothe, University of Duesseldorf, Germany
Topic:
TBA
Speaker: Zack Fitzsimmons, RIT
Topic: Control in the Presence of Manipulators: Cooperative and Competitive Cases
Control and manipulation are two of the most studied types of attacks on elections. In this paper, we study the complexity of control attacks on elections in which there are manipulators. We study both the case where the "chair" who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet we for a Borda-voting case show that such clashes raise the complexity unless NP=coNP.
This is joint work with Edith Hemaspaandra and Lane A. Hemaspaandra.
Speaker: Scott Ames, UR
Topic: TBA
Speaker: Christopher Homan, RIT
Topic: TBA
Speaker: Joel Seiferas, UR
Topic: TBA
Speaker: Zack Fitzsimmons, RIT
Topic: TBA
Speaker: Muthuramakrishnan Venkitasubramaniam, UR
Topic: TBA