## THEORY CANAL: The Rochester Theory Seminar Series 2008-2009 |

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

The meetings this year will be held 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 12:30PM THEORY CANAL talks for the
2008-2009 academic year:**

**September 1, 2008, 12:30pm**(No Meeting: Labor Day)**September 15, 2008, 12:30pm***Speaker*:**Joel Seiferas, University of Rochester**

*Topic*:**A Proof of the Unsolvability of Hilbert's 10th Problem (Part 1)**A set is ``represented'' by an arithmetic expression if it is the set of integer values for the first variable such that the whole expression can be made 0 by some assignment of integers to the rest of the variables.

I will present a proof of the famous Davis-Putnam-Robinson result that every recursively enumerable set (or relation) has such a representation using only addition, subtraction, multiplication, and exponentiation. Since there are recursively enumerable sets with undecidable membership questions (such as the halting problem), the undecidability of whether an equation involving such expressions has an integer solution follows.

An even more famous result, the Davis-Putnam-Robinson-Matiyasevich unsolvability result for Hilbert's Tenth Problem, will follow when we eliminate the need for exponentiation, by combining the DPR result with Matiyasevich's amazing representation of exponentiation using just the other operations, which I plan to present later in the term.

There have been quite a few versions of these proofs, especially by Matiyasevich. I will try to present one that is most accessible to computer scientists (since I am one).

**September 22, 2008, 12:30pm**(****NOTE: THIS TALK IS ON A NONSTANDARD-PARITY MONDAY: AN EVEN ONE****)*Speaker*:**Qi Ge, University of Rochester**

*Topic*:**Superstring Model for Improvement of Cache Performance**We propose a new model in order to improve the cache performance from the software aspect. The model is an offline model which recieves as input a cache replacement policy $P$ and any string $s$ of cache references and outputs a superstring $s'$ of $s$ such that the number of cache misses of $s'$ with respect to $P$ is less than that of $s$ with respect to $P$. We analysis three cache replacement policies, RAND, LRU and Pseudo-LRU and give bounds on the best superstring $s'$ the model can achieve.

**September 29, 2008, 12:30pm**(No Meeting: Rosh ha-Shana)**October 6, 2008, 12:30pm**(No Meeting: UR Fall Break)**October 20, 2008, 12:30pm**(Cancelled: The speaker, Will, is sick.)**November 3, 2008, 12:30pm**(**No Meeting today!**)**November 10, 2008, 12:30pm**(****NOTE: THIS TALK IS ON A NONSTANDARD-PARITY MONDAY: AN EVEN ONE****)*Speaker*:**Joel Seiferas, University of Rochester**

*Topic*:**A Proof of the Unsolvability of Hilbert's 10th Problem (Part 2)****November 17, 2008, 12:30pm**(No Meeting: RIT Fall/Winter Break)**December 1, 2008, 12:30pm***Speaker*:**Piotr Faliszewski, University of Rochester**

*Topic*:**Approximability of Manipulating Elections**Classical result of Gibbard and Satterthwaite shows that for any reasonable election system there are scenarios where at least some voters have an incentive to vote strategically (i.e., to misrepresent their vote). Such strategic behavior can skew results of elections and, possibly, lead to outcomes that are not in the voters' best interest.

In the late 80s and early 90s, Bartholdi, Tovey, Trick, and Orlin, proposed the following computational approach to solving the problem: If the problem of deciding if strategic voting can be successful is NP-hard then, for all practical reasons, the voters are prevented from acting strategically. This line of work received a lot of attention in recent years. However, a standard complaint about the approach is that NP-hardness is a worst-case notion and thus it might not tell us much about hardness of strategic voting in typical cases.

In this talk I will present a refinement of the computational approach to studying hardness of affecting the result of an election via considering approximation algorithms.

Joint work with Eric Brelsford, Edith Hemaspaandra, Henning Schnoor, and Ilka Schnoor.

**January 1 and 15, 2009, 12:30pm**(No Meetings: Intersessions and Martin Luther King Day)**February 2, 2009, 12:30pm***Speaker*:**Shuji Kijima, Kyoto University**

*Topic*:**Perfect Sampling of Two-Rowed Contingency Tables**

A contingency table is a matrix with non-negative integral entries and satisfies prescribed marginals. Counting contingency tables for a given marginals is known to be #P-complete even if the number of rows is two. In this talk, I will show a perfect sampling algorithm for two-rowed contingency tables. The algorithm is a Markov chain Monte Carlo (MCMC), and provides contingency tables exactly uniformly at random based on the idea of the monotone coupling from the past (CFTP) proposed by Propp and Wilson,

This is a joint work with Tomomi Matsui (Chuo University).

**February 16, 2009, 12:30pm***Speaker*:**Satyaki Mahalanabis, University of Rochester**

*Topic*:**Approximating L1-Distances Between Mixture Distributions Using Random Projections**We consider the problem of computing $L_1$-distances between every pair of probability densities from a given family, a problem motivated by density estimation. We point out that the technique of Cauchy random projections (Indyk'06) in this context turns into stochastic integrals with respect to Cauchy motion.

For piecewise-linear densities these integrals can be sampled from if one can sample from the stochastic integral of the function $x\mapsto (1,x)$. We give an explicit density function for this stochastic integral and present an efficient (exact) sampling algorithm. As a consequence we obtain an efficient algorithm to approximate the $L_1$-distances with a small relative error.

For piecewise-polynomial densities we show how to approximately sample from the distributions resulting from the stochastic integrals. This also results in an efficient algorithm to approximate the $L_1$-distances, although our inability to get exact samples worsens the dependence on the parameters.

Join work with Daniel Stefankovic

**March 2, 2009, 12:30pm**(No Meeting: RIT Winter/Spring Break)**March 16, 2009, 12:30pm***Speaker*:**Mehdi Hafezi Manshadi, University of Rochester**

*Topic*:**Quantifier Scoping in Natural Language Semantics**

One of the main sources of ambiguity in representing natural language semantics is quantifier scoping. For example the sentence "All the students had a laptop" has two possible readings, one for the case where every student had his or her own laptop and one where there was a single laptop belonging to all the students. In this talk, first I introduce the problem of quantifier scoping and the concept of Underspecification in Semantic Representation, specifically addressing two main problems for an underspecified semantic representation: satisfiability and enumeration.

I formulate the two problems as a graph theory problem. Both problems have already been proven to be NP-complete in the general case. We show under some restrictions, which provably every coherent natural language sentence satisfies, the problems can be solved in polynomial time.

This is joint work with James Allen and Mary Swift.

**March 30, 2009, 12:30pm***Speaker*:**William Rummler, Rochester Institute of Technology**

*Topic*:**Counting and Sampling Edge Covers**Given a graph, an edge cover is a subset of edges such that each vertex is incident on at least one edge from the subset. Though the size of a minimum edge cover and the size of a maximum matching in a graph are known to be related, the total number of edge covers in a graph is not known (and does not appear) to be related to the total number of matchings. Thus, there seem to be no implications from the well-studied problem of counting and sampling matchings to the problem of counting and sampling edge covers.

In this talk, I present the current status of my thesis investigation into counting and sampling edge covers.

**April 6, 2009, 12:30pm***Speaker*:**Jason A. Covey, Rochester Institute of Technology**

*Topic*:**On the Approximability of Dodgson Elections**

The voting rules proposed by Dodgson and Young are both designed to find the alternative closest to being a Condorcet winner, according to two different notions of proximity; the score of a given alternative is known to be hard to compute under either rule. We demonstrate that computing any reasonable approximation of the ranking produced by Dodgson's rule is NP-hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the Social Choice Theory literature when comparing Dodgson elections with simpler voting rules.

**April 20, 2009, 12:30pm****(Last Meeting of the Semester)***Speaker*:**Christopher Homan, Rochester Institute of Technology**

*Topic*:**Dichotomy Results for Fixed Point Counting in Boolean Dynamical Systems**Dynamical systems are important models in many scientific and engineering disciplines. Often they resist direct analysis, and so one must rely on simulation to study them. Such a computer-based simulation is thus a discrete dynamical system, that is, a dynamical system with a discrete domain.

We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0,1}. For a class F of boolean functions and a class G of graphs, an (F,G)-system is a boolean dynamical system with local transitions functions lying in F and graphs in G. We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let F be a class of boolean functions closed under superposition and let G be a graph class closed under taking minors. If F contains all min-functions, all max-functions, or all self-dual and monotone functions, and G contains all planar graphs, then it is #P-complete to compute the number of fixed points in an (F,G)-system; otherwise it is computable in polynomial time. We also prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). This theorem has a significantly more complicated structure than the theorem for lookup tables. A corresponding theorem for boolean circuits coincides with the theorem for formulas.

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