## THEORY CANAL: The Rochester Theory Seminar Series 2010-2011 |

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 held in Room 70-3000 (the CS conference room; 3rd floor), Golisano College of Computing and Information Sciences, Rochester Institute of Technology, Rochester, NY 14623.

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
2010-2011 academic year:**

**September 6, 2010, 12:30pm**(No Meeting: Labor Day)**September 20, 2010, 12:30pm***Speaker*:**Ivona Bezakova, RIT**

*Topic*:**Counting minimum (s,t)-cuts in weighted planar graphs in polynomial time**We give an O(nd+n log n) algorithm computing the number of minimum (s,t)-cuts in weighted planar graphs, where n is the number of vertices and d is the length of the shortest s-t path in the corresponding unweighted graph. Previously, Ball and Provan gave a polynomial-time algorithm for unweighted graphs with both s and t lying on the outer face. Our results hold for all locations of s and t and weighted graphs, and have direct applications in image segmentation and other computer vision problems.

This is a joint work with Adam Friedlander.

**October 4, 2010, 12:30pm***Speaker*:**Christopher Homan, RIT**

*Topic*:**Student Show-and-Tell**Christopher Homan's three masters students will discuss the problems they are working on for their masters theses. Problems include sampling on large graphs and social choice theory.

**October 18, 2010, 12:30pm**(No Meeting: National Theory Holiday: Scott Aaronson Speaks at URCS Day)**November 1, 2010, 12:30pm***Speaker*:**Andrew Lin, RIT**

*Topic*:**Solving Election Manipulation Using Integer Partitioning Problems**An interesting problem of multi-agent systems is that of voting, in which the preferences of autonomous agents are to be combined. Applications of voting include modeling social structures, search engine ranking, and choosing a leader among computational agents. In the setting of voting, it is very important that each agent presents truthful information about his or her preferences, and not manipulate. The choice of election system may encourage or discourage voters from manipulating. Because manipulation often results in undesirable consequences, making the determination of such intractable is an important goal.

An interesting metric on the robustness of an election system concerns the frequency in which opportunities of manipulations occur in a given election system. Previous work by Walsh has evaluated the frequency of manipulation in the context of very specific election systems, particularly veto, when the number of candidates is limited to at most three, by showing that manipulation problems in these systems can be viewed as (2-way) partition problems, and then using the best known heuristics of Partition. Walsh also claimed similar results hold for k-candidate veto election by way of problems involving multi-way partitions.

We show that the results for k-candidate veto elections do not follow directly from common versions of partition problems and require non-trivial modifications to Multi-Way Partition. With these modifications, we confirm Walsh's claim that these elections are also vulnerable to manipulation. Our new computational problems also allow one to evaluate manipulation in the general case of k-candidate scoring protocols. We investigate the complexity of manipulating scoring protocols using new algorithms we derive by extending the known algorithms of Multi-Way Partition.

It is our conclusion that the problems of manipulation in more general scoring protocols of four or more candidates are not vulnerable to manipulation using extensions of the current known algorithms of Multi-Way Partition. This may be due to weaknesses in these algorithms or complexity in manipulating general scoring protocols.

**November 15, 2010, 12:30pm**(No Meeting: RIT Finals)**November 29, 2010, 12:30pm***Speaker*:**Daniel Stefankovic, UR**

*Topic*:**A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions**Given $n$ elements with nonnegative integer weights $w_1, \ldots, w_n$ and an integer capacity $C$, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most the given capacity. We give a deterministic algorithm that estimates the number of solutions to within relative error $1\pm\eps$ in time polynomial in $n$ and $1/\eps$ (fully polynomial approximation scheme). More precisely, our algorithm takes time $O(n^3\eps^{-1}\log(n/\eps))$. Our algorithm is based on dynamic programming. Previously, randomized polynomial time approximation schemes were known first by Morris and Sinclair via Markov chain Monte Carlo techniques, and subsequently by Dyer via dynamic programming and rejection sampling. Joint work with Santosh Vempala and Eric Vigoda.

**December 6, 2010, 12:30pm***Speaker*:**Aaron Gorenstein, UR**

*Topic*:**Simplification of Iterative Array Algorithms with Direct Central Control**Iterative Arrays are a compelling form of parallel computation. While simple to describe, they are still strictly more powerful than a Turing Machine. For example, they are able to compute multiplication in real time, something beyond a TM.

Three core algorithms implemented for this model of computation are Fischer's real-time prime generation, Atrubin's real-time multiplication, and Kosaraju's context-free-language recognizer.

While iterative arrays are a simple model of parallel computation, algorithms developed for the model are often unclear due to their distributed nature. Professor Seiferas developed a model no-more-powerful than an iterative array which adds the functionality of a multi-head Turing Machine, complete with central control. This "direct central control" (DCC) model is a powerful tool that captures many of the simplifications used in an ad-hoc fashion by much of the literature, and allows for simpler algorithms.

This presentation will "warm up" with an implementation of a recognizer for the language ww, and then go on to present the three core algorithms mentioned above, illustrating DCC's expressiveness.

**December 20, 2010, 12:30pm**(No Meeting: Intersessions)**January 3, 2011, 12:30pm**(No Meeting: UR Intersession)**January 17, 2011, 12:30pm**(No Meeting: Martin Luther King Day)**January 31, 2011, 12:30pm this talk has been postponed until April 25***Speaker*:**Satyaki Mahalanabi, UR**

*Topic*:**Learning mixtures of Gaussians with maximum-a-posteriori oracle**We consider the problem of estimating the parameters of a mixture of distributions,where each component distribution is from a given parametric family e.g. exponential, Gaussian etc. We define a learning model in which the learner has access to a *maximum-a-posteriori* oracle which given any sample from a mixture of distributions, tells the learner which component distribution was the most likely to have generated it. We describe a learning algorithm in this setting which accurately estimates the parameters of a mixture of k spherical Gaussians in R^d assuming the component Gaussians satisfy a mild separation condition. Our algorithm uses only polynomially many (in d, k) samples and oracle calls, and our separation condition is much weaker than those required by unsupervised learning algorithms like [Arora 01, Vempala 02].

**February 7, 2011, 12:30pm***Speaker*:**Qi Ge, UR**

*Topic*:**A graph polynomial for independent sets of bipartite graphs**We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings, the number of perfect matchings, and, for bipartite graphs, the number of independent sets (#BIS).

We analyze the complexity of exact evaluation of the polynomial at rational points and show a dichotomy result---for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial.

We propose a natural Markov chain to approximately evaluate the polynomial for a range of parameters. We prove an upper bound on the mixing time of the Markov chain on trees. As a by-product we show that the ``single bond flip'' Markov chain for the random cluster model is rapidly mixing on constant tree-width graphs.

**February 21, 2011, 12:30pm**(No Meeting: RIT Finals)**March 7, 2011, 12:30pm**(No Meeting: UR Spring Break)**March 21, 2011, 12:30pm***Speaker*:**Stanislaw Radziszowski, RIT**

*Topic*:**SHA-3: Cryptographic Hash of the Future**A hash function H:{0,1}* -> {0,1}

^{m}produces an m-bit digest of an arbitrary message, file, or even an entire file system. Typically, one wants hash functions to be easy to compute, but also infeasible to invert or to find collisions (pairs of inputs which hash to the same value). Hash functions are fundamental cryptographic primitives, and they are used extensively in authentication, preserving data integrity, digital signatures, and many other security applications.Since 2007, the National Institute of Standards and Technology is running a competition to design a new hash function to be used instead of a very popular but already broken MD5 and the most used but much troubled SHA-1. Out of 64 designs submitted in October 2008, now, in the final round there are 5 hash function candidates remaining. The new emerging standard, to be dubbed SHA-3, will be chosen in late 2012 from the current set of 5 finalists: BLAKE, Groestl, JH, Keccak and Skein. This talk will contain the background of hashing, the competition, rounds completed so far, an overview of the finalists and a prediction by the speaker who will be the winner.

**April 4, 2011, 12:30pm***Speaker*:**Curtis Menton, UR**

*Topic*:**Manipulation Can Be Hard for Constant-Sized Coalitions in Tractable Voting Systems**Of the many voting systems that have been studied with regard to election manipulation, a few have been found to have an unweighted coalition manipulation problem that is NP-hard for a constant number of manipulators despite having a winner problem that is in P. That is, it is computationally very difficult for a fixed-size group of voters to select their ideal votes, despite it being easy to determine the winner in a given election. We survey this unusual class of voting systems and the work that has analyzed their complexity.

**April 18, 2011, 12:30pm**(No Meeting: Passover)**April 25, 2011, 12:30pm**(note: this talk is on a nonstandard parity Monday: an even one)*Speaker*:**Satyaki Mahalanabi, UR**

*Topic*:**Learning mixtures of Gaussians with maximum-a-posteriori oracle**We consider the problem of estimating the parameters of a mixture of distributions,where each component distribution is from a given parametric family e.g. exponential, Gaussian etc. We define a learning model in which the learner has access to a *maximum-a-posteriori* oracle which given any sample from a mixture of distributions, tells the learner which component distribution was the most likely to have generated it. We describe a learning algorithm in this setting which accurately estimates the parameters of a mixture of k spherical Gaussians in R^d assuming the component Gaussians satisfy a mild separation condition. Our algorithm uses only polynomially many (in d, k) samples and oracle calls, and our separation condition is much weaker than those required by unsupervised learning algorithms like [Arora 01, Vempala 02].

The seminar series is open to public, and is being organized this year by Edith Hemaspaandra of RIT and Lane Hemaspaandra and Qi Ge of UR. If you have any questions, please send email to ``eh'' (in the domain cs.rit.edu) or ``lane'' or ``qge'' (both in the domain cs.rochester.edu).