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.
Chronological list of 12:30PM THEORY CANAL talks for the
2012-2013 academic year:
Speaker: Andreas Galanis
Topic: Inapproximability of the Partition Function for the
Antiferromagnetic Ising and Hard-Core Models
A 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Speaker: Yongqi Sun
Topic: Wheel and Star-critical Ramsey Numbers for Quadrilateral
The star-critical Ramsey number r*(H1,H2) is the smallest integer
k such that every 2-coloring of the edges of Kn - K1,n-k-1 contains
either a red copy of H1 or a blue copy of H2, where n is the graph Ramsey number R(H1,H2).
In this paper we study the cases of r*(C4,Cn)
and R(C4,Wn), where Wn is a wheel with a hub connected by n - 1
spokes to a cycle Cn-1. In particular, we prove that r*(C4,Cn) = 5
for n ≥ 4, and establish the exact values of R(C4,Wn) 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(C4,Wn) which are very
near to their upper bounds.