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: Muthuramakrishnan Venkitasubramaniam, UR
Topic: Adaptive and Concurrent Secure Computation from New Adaptive, Non-Malleable Commitments
We present a unified approach for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Using our approach we essentially obtain all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions in known models. Additionally, we provide the first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and the non-uniform simulation model. As a corollary we also obtain the first adaptively secure multiparty computation protocol in the plain model that is secure under bounded-concurrency. A key element in our construction is a commitment scheme that satisfies a strong definition of non-malleability. Our new primitive of concurrent equivocal nonmalleable commitments, intuitively, guarantees that even when a man-in-the-middle adversary observes concurrent equivocal commitments and decommitments, the binding property of the commitments continues to hold for commitments made by the adversary. This definition is stronger than previous ones, and may be of independent interest. Previous constructions that satisfy our definition have been constructed in setup models, but either require existence of stronger encryption schemes such as CCA-secure encryption or require independent "trapdoors" provided by the setup for every pair of parties to ensure non-malleability. A main technical contribution of this work is to provide a construction that eliminates these requirements and requires only a single trapdoor.
Joint work with Dana Dachman-Soled, Tal Malkin and Mariana Raykova.
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: Complexity of Manipulation, Bribery, and Campaign Management in Bucklin and Fallback Voting
A central theme in computational social choice is to study the extent to which voting systems computationally resist manipulative attacks seeking to influence the outcome of elections, such as manipulation (i.e., strategic voting), control, and bribery. Bucklin and fallback voting are among the voting systems with the broadest resistance (i.e., NP-hardness) to control attacks. However, only little is known about their behavior regarding manipulation and bribery attacks. We comprehensively investigate the computational resistance of Bucklin and fallback voting for many of the common manipulation and bribery scenarios; we also complement our discussion by considering several campaign management problems for Bucklin and fallback.
This talk is based on joint work with Piotr Faliszewski, Yannick Reisch, and Lena Schend.
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: Special Cases of Homomorphic Encryption
We discuss known methods of homomorphic encryption: computing operations on encrypted data, yielding an encrypted result. There are known encryption systems that support homomorphic evaluation of any polynomial-sized circuit, but not all circuits are equally efficient to evaluate. We present a few special cases of avoiding the large polynomial time cost of evaluating general circuits on encrypted data. Particularly efficient methods exist for homomorphic evaluation of addition, logarithmic depth circuits, and branching programs.
Speaker: Joel Seiferas, UR
Topic: Cobham's Theorem
Let's try to understand a proof of Cobham's 1969 theorem that any set of numbers (whose representations are) regular in two ``independent'' bases (e.g., 2 and 10) is actually regular in *every* base (including 1!).
Speaker: Zack Fitzsimmons, RIT
Topic: An Overview of Single-Peakedness
Single-peakedness is one of the most commonly examined domain restrictions on preferences. We provide a general overview of single-peaked preferences and their implications in elections. We focus on algorithms and complexity results for the single-peaked consistency problem, that is, determining if a given preference profile is single-peaked or not. The preference profiles discussed are not restricted to total linear orders, we also look at partial and weak preference orders and how this affects determining single-peakedness. In addition, different notions of "nearly" single-peakedness, where a preference profile is close to single-peaked with respect to some distance measure, will be discussed.
Speaker: Christopher Homan, RIT
Topic: Dynamic social choice with evolving preferences
Parkes and Procaccia, in "Dynamic social choice with evolving preferences," consider the problem of voting in multiple rounds where the voters' preferences change dynamically as a function of their preferences in the previous round. Such settings are motivated by multiagent systems and crowdsourcing. I will summarize their model, which uses Markov decision problems to represent the dynamic behavior of the voters, and results, and consider manipulation in this setting.