## THEORY CANAL: The Rochester Theory Seminar Series 2012-2013 |

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 minutes.

The meetings this year will be alternating between UofR and RIT.

The meetings are open to the public; all are very welcome.

(2) **Reply to that message to subscribe.**

(2) **Reply to that message to unsubscribe.**

**Chronological list of 12:30PM THEORY CANAL talks for the
2012-2013 academic year:**

**September 3, 2012, 12:30pm**(No Meeting: Labor Day)**September 17, 2012, 12:30pm, room CSB 703**(University of Rochester, Department of Computer Science)*Speaker*:**Andreas Galanis**

*Topic*: Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core ModelsA beautiful picture was recently established for the complexity of counting independent sets in graphs of maximum degree Delta. Inapproximability results of Sly, together with an approximation algorithm presented by Weitz, determined precisely a computational transition in the complexity of counting weighted independent sets in the hard-core model with activity lambda>0, where an independent set I has weight lambda^|I|. These results established a rigorous connection between the computational tractability of counting/sampling and the theory of phase transitions in Statistical Physics.

In this talk, we will focus on the inapproximability side of this connection. We consider the analogous counting problem in a wider class of two state spin models, placing emphasis on the well-studied cases of the antiferromagnetic Ising and hard-core models. In particular, we provide tight inapproximability results matching previously known algorithmic bounds.

Joint work with Daniel Stefankovic and Eric Vigoda.

**September 24, 2012, 12:30pm, room GOL-3000**: the CS conference room (Rochester Institute of Technology, Golisano College of Computing and Information Sciences)

Directions to the College of Computing and Information Sciences (building 70), and on Parking and Getting a Visitor's Parking Pass (free).

**NOTICE: non-standard parity Monday***Speaker*:**Joerg Rothe**

*Topic*:**Online Manipulation and Control in Sequential Elections**Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential, and manipulators may know the already cast votes but may not know the future votes. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that in this setting manipulation can be extremely complex even for election systems with simple winner problems. Yet we also show that for some of the most important election systems such manipulation is simple in certain settings. This suggests that when using sequential voting, one should pay great attention to the details of the setting in choosing one's voting rule.

Among the highlights of our classifications are: We show that, depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonunique-winner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first P^{NP[1]}-completeness and P^{NP}-completeness results in the field of computational social choice, in particular proving such completeness for, respectively, the complexity of 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections.

We also introduce a related framework that models online voter control in sequential elections. Previous work on (non-online) voter control in simultaneous elections, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters' preferences and that all votes are cast simultaneously. We show that the related problems can be much harder (namely, PSPACE-complete) than in the standard (non-online) case, yet we also show that for plurality, online control by deleting or adding voters is in P, and for partitioning voters is coNP-hard.

This talk is based on joint work with Edith Hemaspaandra and Lane A. Hemaspaandra.

**October 1, 2012**(No meeting. Come to EAGL.)**October 15, 2012**(No meeting.)**October 29, 2012, 12:30pm, room CSB 703**(University of Rochester, Department of Computer Science)*Speaker*:**Curtis Menton**

*Topic*:**Control Complexity of Schulze Voting**Schulze voting is a recently introduced voting system enjoying unusual popularity and a high degree of real-world use, with users including the Wikimedia foundation, several branches of the Pirate Party, and MTV. It is a Condorcet voting system that determines the winners of an election using information about paths in a graph representation of the election. We fully characterize the worst-case behavior of Schulze voting under control. We find that it falls short of the best known voting systems in terms of control resistance, demonstrating vulnerabilities of concern to some prospective users of the system.

**November 5, 2012**(No meeting. We will have a meeting next week - a non-standard parity Monday, see below.)**November 12, 2012, 12:30pm, room CSB 703**(University of Rochester, Department of Computer Science)*Speaker*:**Scott Ames**

*Topic*:**New Constructions of Universal One-Way Hash-Functions from Regular One-Way Functions**In this work we present new and efficient constructions of universal one-way hash-function (UOWHF) families from regular one-way functions. We show that the Randomized Iterate, introduced by Goldreich, Krawczyk and Luby, of a (regular) one-way function can be used to build a Universal One-Way Hash- Function (UOWHF) families with O(n^2) key length and O(n) input length where n is the security parameter. We then show how improve the efficiency of the previous construction using Shoup's technique for UOWHF domain extension.

Towards this, we present the Reusable Generalized Randomized Iterate which consists of k >= n+1 iterations of a regular one-way function composed at each iteration with a pairwise independent hash function, where we only use log k such hash functions, and we ``schedule'' them according to the same scheduling of Shoup's domain extension technique. The end result is a UOWHF construction from regular one-way functions with an O(n log n) key. These are the first such efficient constructions of UOWHF from regular one-way functions of unknown regularity.

Finally we show that the Shoup's domain extension technique can also be used in lieu of derandomization techniques to improve the efficiency of PRGs and of hardness amplification constructions for regular one-way functions.

**November 19, 2012**(No meeting: RIT break.)**December 3, 2012, 12:30pm, room 703**(University of Rochester, Department of Computer Science)*Speaker*:**Rahman Lavaee**

*Topic*:**Unweighted Coalitional Manipulation Under the Borda Rule is NP-hard**The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m- 1 points, the second m- 2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? In 2011, two groups independently showed that the problem is NP-hard. Although both groups used the same problem to reduce from, one group achieved a stronger result. They showed NP-hardness even for two manipulators and three input votes.

**December 17, 2012, 12:30pm**(No meeting: UofR final exams.)**December 31, 2012, 12:30pm**(No meeting: UofR/RIT break.)**January 14, 2013, 12:30pm**(No meeting: UofR break.)**January 28, 2013, 12:30pm, room GOL-3000**: the CS conference room (Rochester Institute of Technology, Golisano College of Computing and Information Sciences)*Speaker*:**Alex Lange**

*Topic*:**Ramsey Numbers Involving the Quadrilateral**The Ramsey number R(C4,Km) is the smallest n such that any graph on n vertices contains either a cycle of length four or an independent set of order m. We approach these numbers from both theoretical and computational perspectives, and present known asymptotics as well as exact values for small m. An important step in understanding R(C4,Km) is the study of C4-free graphs. We survey known constructions of such graphs, including one by Erdos, Renyi, and Sos based on finite projective planes. Knowledge of the Turan number ex(n,C4), defined as the maximum number of edges possible in a C4-free n-vertex graph, is also useful. Prior to this work, the exact values for R(C4,Km) were known for 3 <= m <= 8. We present a computational proof of R(C4,K9)=30 and improved bounds for m=10,11, with the hopes of settling the case for m=10 in the near future.

**February 4, 2013, 12:30pm, room 703**(University of Rochester, Department of Computer Science)*Speaker*:**Curtis Menton**

*Topic*:**Search versus Decision for Election Manipulation Problems**Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated, rather than the search problem of finding the successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If integer factoring is hard, then for election manipulation, election bribery, and some types of election control, there are election systems for which recognizing which instances can be successfully manipulated is in polynomial time but producing the successful manipulations cannot be done in polynomial time.

**March 4, 2013, 12:30pm, room 703**(University of Rochester, Department of Computer Science)*Speaker*:**Gabor Erdelyi**

*Topic*:**Manipulation Under Voting Rule Uncertainty**1. Manipulation Under Voting Rule Uncertainty (Joint work with Edith Elkind)

An important research topic in the field of computational social choice is the complexity of various forms of dishonest behavior, such as manipulation, control, and bribery. While much of the work on this topic assumes that the cheating party has full information about the election, recently there have been a number of attempts to gauge the complexity of non-truthful behavior under uncertainty about the voters' preferences. In this talk, I will analyze the complexity of (coalitional) manipulation for the setting where there is uncertainty about the voting rule: the manipulator(s) know that the election will be conducted using a voting rule from a given list, and need to select their votes so as to succeed no matter which voting rule will eventually be chosen.

_________________________________2. The Complexity of Nearly Single-Peaked Consistency (Joint work with Martin Lackner and Andreas Pfandler)

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting systems are in the general case computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these problems suddenly become easy to solve. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the complexity of dishonest behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this talk, I will introduce several new distance measures regarding single-peakedness. I will show that determining whether a given profile is nearly single-peaked is in many cases NP-complete.

**March 18, 2013, 12:30pm, room GOL-3000**: the CS conference room (Rochester Institute of Technology, Golisano College of Computing and Information Sciences)*Speaker*:**Stanisław P. Radziszowski**

*Topic*:**Bounds on Shannon Capacity and Ramsey Numbers from Product of Graphs**In this paper we study Shannon capacity of channels in the context of classical Ramsey numbers. We overview some of the results on capacity of noisy channels modelled by graphs, and how some constructions may contribute to our knowledge of this capacity. We present an improvement to the constructions by Abbott and Song and thus establish new lower bounds for a special type of multicolor Ramsey numbers. We prove that our construction implies that the supremum of the Shannon capacity over all graphs with independence number 2 cannot be achieved by any finite graph power. This can be generalized to graphs with bounded independence number.

**April 1, 2013, 12:30pm**(No meeting: Passover/Easter.)**April 15, 2013, 12:30pm, room 703**(University of Rochester, Department of Computer Science)*Speaker*:**Marcus Schaefer**

*Topic*:**Toward a Theory of Planarity: An algorithm for simultaneous planarity?**We study relationships between various notions of planarity and show how some recent results on Hanani-Tutte style theorems for those planarity notions suggest a uniform algebraic approach to all these notions. As a result, we can exhibit a polynomial-time algorithm that may decide simultaneous planarity, c-planarity, partially embedded planarity, etc., with the one caveat that we can only prove correctness of the algorithm relative to some redrawing conjectures. The algorithm is self-aware in the sense that it would recognize a counterexample to its correctness.

**April 29, 2013, 12:30pm, room GOL-3000**: the CS conference room (Rochester Institute of Technology, Golisano College of Computing and Information Sciences)*Speaker*:**Yongqi Sun**

*Topic*:**Wheel and Star-critical Ramsey Numbers for Quadrilateral**The star-critical Ramsey number r

_{*}(H_{1},H_{2}) is the smallest integer k such that every 2-coloring of the edges of K_{n}- K_{1,n-k-1}contains either a red copy of H_{1}or a blue copy of H_{2}, where n is the graph Ramsey number R(H_{1},H_{2}). In this paper we study the cases of r_{*}(C_{4},C_{n}) and R(C_{4},W_{n}), where W_{n}is a wheel with a hub connected by n - 1 spokes to a cycle C_{n-1}. In particular, we prove that r_{*}(C_{4},C_{n}) = 5 for n ≥ 4, and establish the exact values of R(C_{4},W_{n}) for 9 cases of n between 18 and 44. In addition, by the results of cages and our constructions, we give some lower bounds on R(C_{4},W_{n}) which are very near to their upper bounds.

- 2011-2012
- 2010-2011
- 2009-2010
- 2008-2009
- 2007-2008
- 2006-2007
- 2005-2006
- 2004-2005
- 2003-2004
- 2002-2003
- 2001-2002
- 2000-2001

The seminar series is open to public, and is being organized this year by Ivona Bezakova of RIT and Daniel Stefankovic, and Curtis Menton of UR. If you have any questions, please send email to "ib" (in the domain cs.rit.edu) or "stefanko" or "menton" (in the domain cs.rochester.edu).