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

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 (and sometimes, when a fifth exists, 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 are 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
2007-2008 academic year
(**currently, all these are somewhat tentative and in some cases a surprise to the speaker, but within a few days they'll be carved in semi-stone**)
:**

**August 22, 2007, 4:00pm**(****NOTE: THIS SUMMER TALK WILL BE GIVEN AT A NONSTANDARD DAY AND TIME****)*Speaker*:**Jin-Yi Cai, UW-Madison**

*Topic*:**Developments in Holographic Algorithms**Valiant's new theory of holographic algorithms is one of the most beautiful ideas in algorithm design in recent memory. It represents a totally original attack on the P and NP question. Information is represented in a superposition of linear vectors in a holographic mix. The underlying computation is done by invoking the Fisher-Kasteleyn-Temperley method for counting perfect matchings for planar graphs, which uses Pfaffians and runs in polynomial time.

In this talk we will survey some new developments in holographic algorithms.

**August 29, 2007, 4:00pm**(****NOTE: THIS SUMMER TALK WILL BE GIVEN AT A NONSTANDARD DAY AND TIME****)*Speaker*:**Akinori Kawachi, Tokyo Institute of Technology**

*Topic*:**Computational Indistinguishability between Quantum States and Its Cryptographic Application**We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is ``secure'' against any polynomial-time quantum adversary. Our problem QSCDff is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show three cryptographic properties: (i) QSCDff has the trapdoor property; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff is computationally at least as hard in the worst case as the graph automorphism problem. These cryptographic properties enable us to construct a quantum public-key cryptosystem, which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCDff, called QSCDcyc, and introduce a multi-bit encryption scheme relying on the cryptographic properties of QSCDcyc.

This is joint work with Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami

**September 3, 2007, 12:30pm**(No Meeting: Labor Day)**September 17, 2007, 12:30pm***Speaker*:**Joerg Rothe, University of Duesseldorf**

*Topic*:**The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions**Holzer and Holzer proved the Tantrix(TM) rotation puzzle problem with four colors NP-complete. In this talk, results on the three-color and the two-color version of this problem are presented. Restricting the number of allowed colors to three (respectively, to two) reduces the set of available Tantrix(TM) tiles from 56 to 14 (respectively, to 8). It will be shown that both the three-color and the two-color Tantrix(TM) rotation puzzle problem is NP-complete, which answers a question raised by Holzer and Holzer in the affirmative. Since both these reductions from SAT are parsimonious (i.e., they preserve the number of solutions), it follows that both the unique three-color and the unique two-color Tantrix(TM) rotation puzzle problem is DP-complete under randomized reductions.

Joint work with Dorothea Baumeister.

**October 1, 2007, 12:30pm***Speaker*:**Piotr Faliszewski, University of Rochester**

*Topic*:**The Complexity of Llull Elections**We discuss the computational complexity of control and bribery within Llull and Copeland elections. Llull and Copeland elections are run as follows: For each two candidates we ask all the voters as to which one they prefer. The winner of such a head-to-head contest receives one point and the loser receives none. Ties are handled specially (and that's where the difference between various flavors of the election systems studied come into play). We show a fairly general technique that can be used to show that some of the control/bribery problems are NP-complete. We also show how network flows can be used to find optimal briberies in certain settings.

Joint work with Edith Hemaspaandra, Lane Hemaspaandra, and Joerg Rothe.

**October 15, 2007, 12:30pm***Speaker*:**Joan Lucas, SUNY-Brockport**

*Topic*:**Tango Trees: a O( lg lg n)-competitive binary search tree**In 1985, Sleator and Tarjan introduced the splay tree algorithm for maintaining a binary search tree. The splay tree is a self-adjusting data structure whose amortized performance matches any of the many forms of balanced binary search trees. Sleator and Tarjan conjectured that splay trees are dynamically optimal, i.e., that they are as efficient as any other possible binary search tree algorithm. This conjecture effectively claims that splay trees are O(1)-competitive. Although optimality results for splay trees have been obtained for several special cases, the general conjecture remains unresolved. The best known general bound for splay trees is the trivial one that splay trees are O(log n)-competitive. Demaine, et. al., in 2004, presented the first data structure to have a competitive ratio better than O(log n). Their Tango Tree is a O( log log n )-competitive online binary search tree algorithm. In this talk we will describe this data structure and illustrate their proof of this bound.

**October 29, 2007, 12:30pm***Speaker*:**Ilka Schnoor, University of Hannover**

*Topic*:**Complexity of Default Logic**Reiter's default logic formalizes nonmonotonic reasoning using default assumptions. The semantics of a given instance of default logic is based on a fixpoint equation defining an extension. Three different reasoning problems arise in the context of default logic, namely the existence of an extension, the presence of a given formula in an extension, and the occurrence of a formula in all extensions.

In this talk I'll give an introduction to Reiter's default logic and present a complete complexity classification of default logic reasoning problems by means of universal algebra tools using Post's clone lattice.

**Special Announcement: *Friday* November 2, 2007 (Second Western New York Theory Day)**Location: UB. More information is available at http://www.cse.buffalo.edu/events/theoryday.html (please note in particular the parking-permit info).

**November 5, 2007, 12:30pm***Speaker*:**Rahul Santhanam, University of Toronto**

*Topic*:**Infeasibility of Instance Compression and Succinct PCPs for NP**We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there is a polynomial-time computable function $f$ and a set $A$ such that for each instance $x$ of $L$, $f(x)$ is of size polynomial in the {it witness size} of $x$, and $f$ reduces $L$ to $A$.

We prove that SAT is not instance compressible unless NP is contained in coNP/poly, and the Polynomial Hierarchy collapses. This result settles an open problem posed by [Harnik-Naor06] and [Downey07], and has a number of implications: (1) A number of parametric NP problems, including SAT, Clique, DominatingSet and IntegerProgramming, are not polynomially kernelizable unless NP is contained in coNP/poly. (2) SAT does not have "succinct PCPs", i.e., PCPs of size polynomial in the number of variables, unless NP is contained in coNP/poly. (3) An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is inviable in its present form. (4) (Buhrman) There are no sub-exponential size complete sets for NP or coNP unless NP is contained in coNP/poly.

**November 19, 2007, 12:30pm**(No Meeting: RIT Fall Break)**December 10, 2007, 12:30pm***Speaker*:**Bin Wei, University of Rochester**

*Topic*:**Learning Structure of Bayesian Networks Through Decomposition**

Structure learning of Bayesian network is generally regarded as a difficult problem. There are two basic types of algorithms in the area: conditional independence (CI) test based and scoring metric based. However, most algorithms face the same bottleneck of scalability. We propose a CI test based approach to decompose the learning task to smaller pieces. (And on the basis of this, a top-down decomposition algorithm for learning structure.)

**January 7, 2008, 12:30pm**(No Meeting: Intersession)**January 21, 2008, 12:30pm**(No Meeting: Martin Luther King Day)**January 28, 2008, 12:30pm***Speaker*:**Satyaki Mahalanabis, University of Rochester**

*Topic*:**Density Estimation in Linear Time with Preprocessing**We consider the problem of choosing a density estimate from a set of distributions ${\cal F}$, minimizing the $L_1$-distance to an unknown distribution. Devroye and Lugosi analyze two algorithms for the problem: Scheff\'e tournament winner and minimum distance estimate. The Scheff\'e tournament estimate requires fewer computations than the minimum distance estimate, but has strictly weaker guarantees than the latter. We focus on the computational aspect of density estimation. We present two algorithms, both with the same guarantee as the minimum distance estimate. The first one, a modification of the minimum distance estimate, uses the same number (quadratic in $|{\cal F}|$) of computations as the Scheff\'e tournament. The second one, called ``efficient minimum loss-weight estimate'', uses only a linear number of computations, assuming that ${\cal F}$ is preprocessed. We also give examples showing that the guarantees of the algorithms cannot be improved and explore randomized algorithms for density estimation.

This is joint work with Daniel Stefankovic.

**February 4, 2008, 12:30pm***Speaker*:**Ashwin Lall, University of Rochester**

*Topic*:**My Job Talk: Streaming Algorithms for Estimating Entropy of Network Traffic**Measuring the entropy of traffic distributions has been shown to be useful in a wide variety of network monitoring applications such as anomaly detection, clustering to reveal interesting patterns, and traffic classification. However, realizing this potential benefit in practice requires data streaming algorithms that can operate on high-speed links, with low CPU and memory requirements.

In the first part of this talk I will present an algorithm to estimate the entropy of network data efficiently. I will show the efficacy of this algorithm through both theoretical analysis and simulation. In the second part of my talk I will present another algorithm that can be used to compute the entropy of traffic distributions across an entire network. My goal will be to show how elegant theoretical results can have very practically-motivated applicability.

**February 18, 2007, 12:30pm***Speaker*:**Henning Schnoor, University of Hannover**

*Topic*:**Generalized Modal Satisfiability**It is well-known that modal satisfiability is PSPACE-complete. However, the complexity may decrease if we restrict the set of propositional operators used. We completely classify the complexity of modal satisfiability for every finite set of propositional operators, i.e., in contrast to previous work, we classify an infinite number of problems. We show that, depending on the set of propositional operators, modal satisfiability is PSPACE-complete, coNP-complete, or in P. We obtain this trichotomy not only for modal formulas, but also for their more succinct representation using modal circuits. We consider both the unimodal and the multi-modal case, and study the dual problem of validity as well.

**March 3, 2008, 12:30pm**(No Meeting: RIT Spring Break)**March 17, 2007, 12:30pm***Speaker*:**Gahyun Park, SUNY-Geneseo**

*Topic*:**Multiple Choice Tries and Distributed Hash Tables****March 31, 2008, 12:30pm***Speaker*:**Qi Ge, University of Rochester**

*Topic*:**The Complexity of Counting the Number of Eulerian Tours in Restricted Eulerian Graphs**The problem of counting the number of Eulerian tours in Eulerian graphs is \#P-complete and whether there is an efficient sampling/ approximately counting algorithm is still open. In this paper, we show that an efficient sampling/approximately counting algorithm for some restricted Eulerian graphs is sufficient to derive an efficient algorithm for general Eulerian graphs. Here, the restrictions are in both the degree of vertices and the connection of edges which share the same vertices.

**April 7, 2008, 12:30pm***Speaker*:**Ivona Bezakova, Rochester Institute of Technology**

*Topic*:**Graph Model Selection using Maximum Likelihood**In recent years, there has been a proliferation of theoretical graph models, e.g., preferential attachment and small-world models, motivated by real-world graphs such as the Internet topology. To address the natural question of which model is best for a particular data set, we propose a model selection criterion for graph models. Since each model is in fact a probability distribution over graphs, we suggest using Maximum Likelihood to compare graph models and select their parameters. Interestingly, for the case of graph models, computing likelihoods is a difficult algorithmic task. However, we design and implement MCMC algorithms for computing the maximum likelihood for four popular models: a power-law random graph model, a preferential attachment model, a small-world model, and a uniform random graph model. We hope that this novel use of ML will objectify comparisons between graph models.

This is joint work with Adam Kalai and Rahul Santhanam.

**April 21, 2008, 12:30pm****(Last Meeting of the Semester)***Speaker*:**Dan Gildea, University of Rochester**

*Topic*:**Complexity Results for Synchronous Parsing**We relate the problem of finding the best application of a Synchronous Context-Free Grammar (SCFG) rule during parsing to a Markov Random Field. This representation allows us to use the theory of expander graphs to show that the complexity of SCFG parsing input sentence of length N is Omega(N^{cn}), for a grammar with maximum rule length n and some constant c. This improves on the previous best result of Omega(N^{c\sqrt{n}})

Joint work with Daniel Stefankovic.

**Special Announcement: *Friday* May 2, 2007 (Third Western New York Theory Day)**Location: University of Rochester. See the Third Western New York Theory Day home page for more information.

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