Speaker: Christopher Homan
Topic: Routing in a Small World
"Six degrees of separation... it's a small world after all..." You've heard the cliches, heard the hype. Over the past ten years, research into small world phenomena has become a cottage industry. Surprising, very little of this research addresses the algorithmic aspects of small world phenomena; that is, how easy (or hard) it is to convey information in a small world has not been widely studied. This talk will show how to use principles culled from the study of small worlds to design networks that allow for efficient, decentralized routing of information. The basic result is that (in terms of the expected arrival time of packets) almost any small world network will do as long as one chooses the right distribution of the lengths (that is, the physical distances between the nodes) of the edges in the network.
Speaker: Harald Hempel
Topic: Functions in Complexity Theory.
There is a very tight connection between functions and complexity theory, a connection that has many different facets. In this (overview) talk we will look at some of them. In particular, we will investigate the complexity of functions computable with the help of their own graphs, we will look at the inclusion structure of optimization functions, study algebraic properties of selector functions and the impact that those algebraic properties have on the advice complexity of sets being selected by selector functions having such algebraic properties, and last but not least show how to compute particular functions of high complexity efficiently on restricted instances.
Speaker/Topic: No meeting---UR Fall Break and Yom Kippur.
Topic: TBA.
Speaker: Rani Siromoney
Topic: Circular-DNA-Based Algorithms to Solve NP-hard Problems.
DNA-based algorithms have been found useful in solving computationally hard problems. Tom Head has given recently, circular DNA based algorithms to solve NP hard problems. We show that this can be adapted to break a propositional logic based cryptosystem introduced by J.Kari. This result is interesting in view of the fact that Kari has shown that problem faced by the cryptanalyst is in NP intersection CoNP. Also that it is optimal in the sense that any cryptanalysis of this system can be used to break any other system as well.
Speaker: Samik Sengupta
Topic: Properties of NP-Complete Sets.
We will discuss fragments of work in progress by C. Glasser, A. Pavan, A. Selman, and S. Sengupta. This work addresses several open questions about NP-complete sets and about Turing-complete sets for NP. For example, if L is an NP-complete set and S is a sparse set, is L-S still NP complete? If A and B are disjoint NP-complete sets, is the union NP-complete? Can an NP-complete set be poly-close to P? (A set L is poly-close to P if the symmetric difference between L and a set in P is sparse.)
Speaker: Yinhe Cheng
Topic: Algorithms for Sequence Alignment Problems: Part
I.
In these two consecutive talks, I am going to present the biological background related to Sequence alignment, the algorithms to solve this problem and existing Bioinformatics databases and tools.
Speaker: Yinhe Cheng
Topic: Algorithms for Sequence Alignment Problems: Part II.
In these two consecutive talks, I am going to present the biological background related to Sequence alignment, the algorithms to solve this problem and existing Bioinformatics databases and tools.
Speaker: Mayur Thakur
Topic: My Job Talk: Broad-Brush Theorems for Determining Problem Complexity.
Programmers, computer science researchers, and engineers need to
determine the computational complexity of problems on a near-daily
basis, and they typically ask the following questions: Is there an
efficient algorithm for the problem? Is the problem hard? If so, how
hard is the problem? It is desirable to have easily applied tools
(theorems, classification tests, complete characterizations, etc.)
that in one fell swoop classify a large class of problems in the
domain of interest. Rice's Theorem is one such classic and powerful
tool from recursive function theory. It classifies (as either
decidable or undecidable) each language property of the recursively
enumerable sets.
This talk will survey results on complexity-theoretic Rice-style theorems. We obtain the strongest known Rice-style theorem for a broad class of properties of Boolean circuits, and show that this result cannot be much improved using relativizable techniques. We also establish a generalized complexity-theoretic Rice-style theorem that holds for language properties of many central classes such as nondeterministic polynomial time (NP) and probabilistic polynomial time (PP).
Speaker: Edith Hemaspaandra
Topic: The Complexity of Poor Man's Logic.
Motivated by description logics, this talk investigates what happens to the complexity of modal satisfiability problems if we only allow formulas built from literals, $\wedge$, $\Diamond$, and $\Box$. Previously, the only known result was that the complexity of the satisfiability problem for K dropped from PSPACE-complete to coNP-complete (Schmidt-Schauss and Smolka, 1991 and Donini et al., 1992). In this talk I will show that not all modal logics behave like K. In particular, I will show that the complexity of the satisfiability problem with respect to the class of models in which each world has at least one success or drops from PSPACE-complete to P, but that in contrast the satisfiability problem with respect to the class of models in which each world has at most two successors remains PSPACE-complete. As a corollary of the latter result, this also solves the open problem from Donini et al.'s complexity classification of description logics (Donini et al., 1997).
Speaker/Topic: No meeting---Martin Luther King Day
Topic: TBA.
Speaker: Michael Bauland.
Topic: NTRU encryption system
NTRU is a relatively new cryptosystem based on truncated polynomial rings, where the hard problem is the Shortest Vector Problem from lattice theory. I will shortly introduce NTRU, show how it works, give some strengths and some weaknesses.
Speaker: Tao Li
Topic: Two Techniques for Data Mining.
In the first part of my talk, I will we present a simple and efficient solution for multi-class classification. Unlike most of previous approaches which typically decompose a multi-class problem into multiple independent binary classification tasks, a direct method based on Generalized Singular Value Decomposition (GSVD) are developed. In the second part, I will address the problem of discovering temporal patterns from events data. The problem is formulated as comparing two probability distributions of inter-arrival times. A theoretically sound technique, which enabling the discovery of significant, but infrequent patterns, is proposed.
Speaker: John Kramer.
Topic: The Missing Link -A Probabilistic Model of Document
Content and Hypertext Connectivity. David Cohn and Thomas Hofmann.
We describe a joint probabilistic model for modeling the contents and inter-connectivity of document collections such as sets of web pages or research paper archives. The model is based on a probabilistic factor decomposition and allows identifying principal topics of the collection as well as authoritative documents within those topics. Furthermore, the relationships between topics is mapped out in order to build a predictive model of link content. Among the many applications of this approach are information retrieval and search, topic identification, query disambigua-tion, focused web crawling, web authoring, and bibliometric analysis.
Speaker: Ming Zhong
Topic: The Web Graph: Models, Properties, Algorithms and
Web Mining.
The World Wide Web can be modelized as a huge directed graph, in which nodes represent webpages and edges stand for hyperlinks. The graph model could be used to predict and explore the properties of the Web (degrees, diameters). Some graph model-based algorithms (e.g., HITS, Trawling) are proposed to solve the essential Web problems such as: 1. Finding authoritative and hub webpages for certain topics. 2. Finding hidden Web communities. Also, we will discuss the Web structure mining, which is done by analyzing the link structure of the Web graph.
Speaker: Joan Lucas
Topic: Combinatorial Properties of Rotations in Binary
Trees
The binary tree is a fundamental data structure in computer science. The most common operation for restructuring a binary tree is the rotation. The combinatorial properties of binary trees under the rotation operation have been studied using the Rotation Graph, or RG(n). RG(n) contains one node for each binary tree with n nodes, and two nodes of RG(n) are connected if a single rotation transforms one tree into the other. RG(n) is exponentially large with respect to n.
We will summarize the known properties of RG(n), such as connectivity, Hamiltonicity, and diameter. We will discuss the shortest path problem in RG(n). This asks "what is the minimum number of rotations needed to transform any given binary tree T1 into another binary tree T2"? Several approximation algorithms have been proposed. We describe an algorithm to find the exact rotation distance between any two binary trees when both trees are of a restricted form. This is the only known non-trivial, polynomial time algorithm for exact rotation distance between special cases of binary trees.
Speaker: Rahul Tripathi
Topic: Degree Bounds on Polynomials and Relativization Theory.
In this talk, I will demonstrate the applicability of the polynomial degree bound technique to notions such as the nonexistence of Turing-hard sets in some relativized world, (non)uniform gap-definability, and relativized separations. This way, we will settle certain open questions from Hemaspaandra, Ramachandran & Zimand [HRZ95] and Fenner, Fortnow & Kurtz [FFK94], extend results of Hemaspaandra, Jain & Vereshchagin [HJV93] and construct oracles achieving desired results.
This talk is based on a joint work with Holger Spakowski, Institut fur Informatik, Heinrich-Heine-Universitat Dusseldorf, Germany.
Speaker: Mitsunori Ogihara
Topic: Enumerative Approximations of the Rank and the Determinant
Let k be a positive integer and let E and f be functions. The function E is said to be a k-enumerator for f if, for all x, E(x) is a k-element list containing f(x). The notion of enumerators as an alternative to the traditional approximation was proposed by Cai and Hemachandra in the 80s. We study the complexity of two elementary problems in linear algebra, the matrix rank and the determinant, with respect to their approximability using enumerators. We show that, for all finite fields F and for all constants k, if there is a k-enumerator for the matrix rank over F, then the matrix rank over F is AC^0-computable with oracle access to the enumerator. For the determinant we show the following two results: (1) If the determinant of integer matrices is poly-enumerable in logspace, then the determinant is logspace computable. (2) For all primes p, if the determinant over Z_p is (p-1)-enumerable in logspace, then the determinant over Z_p is logspace computable. These results shed some light on the complexity of elementary linear algebra problems that are equivalent to either the rank or the determinant. Because of the close connection between the determinant and #L, and between the matrix rank and C=L, these results may also offer a better understanding of the power of counting logspace classes, and the relationships among the complexity classes that reside between NL and logspace-uniform TC^1. This is a joint work with Alina Beygelzimer.
Speaker: Alexander Yakhnis
Topic:
Infinite Win-Lose Games and their Applications in Logic and Computer Science
I will define these games and the determinacy problem for them. After describing a solution of this problem for a class of games, I will reduce the Rabin's result on decidability of S2S to the problem solved for games. Then I will demonstrate that a computer program correctness is equivalent to demonstrating that a certain strategy wins a game that represents a program specification. This holds true for concurrent programs as well. I will give also examples of games that allow us to reason about devices that are boundedly faulty in specific ways. This talk is based on the results that I found with my brother Vladimir Yakhnis, Anil Nerode, and others, since 1989, and my current work at SUNY College at Brockport.
Speaker: Mayur Thakur
Topic: A Sequential Dynamical Systems Research
Tutorial.
Computer simulations play an important role in the understanding of many real-world systems such as transportation networks, internet, power grid and markets, and ad-hoc networks. Sequential Dynamical Systems (SDS) are formal models for simulations. In this talk, we will define the basic SDS model. We will then discuss computational problems that arise in the study of simulations. In particular, we will discuss the complexity of the following fundamental problems related to simulations: the reachability problem, the predecessor existence problem, the permutation existence problem, the fixed point existence problem, and the Garden-of-Eden existence problem. We will identify cases for which these problems are easy and those for which these problems are hard.