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**)
:
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.
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
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.
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.
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.
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.
Location: UB. More information is available at http://www.cse.buffalo.edu/events/theoryday.html (please note in particular the parking-permit info).
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.
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.)
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.
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.
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.
Speaker:
Gahyun Park, SUNY-Geneseo
 
Topic: Multiple Choice Tries and Distributed Hash Tables
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.
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.
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.
Location: University of Rochester. See the Third Western New York Theory Day home page for more information.