All talks will be at 3:15 pm on Mondays in IST 333 (unless they are part of the departmental colloquium).

If you would like to speak,
please email: theory at cse psu dot edu.

If you want to receive announcements of upcoming talks join the **theory ** mailing list.

### A Theoretician's Perspective of 12 Years in Industrial Research

In this talk, I will describe my trajectory from a freshly graduated Ph.D. in descriptional complexity in the mid-1990s to the present days in industrial research in enterprise communications. I will outline the credibility and skills challenges that I had to overcome at first in an industrial research environment and how I moved on to contribute to cutting edge projects in enterprise communications. Along the way, I will illustrate some of the fundamental changes that have affected the enterprise communications industry and its research divisions. The purpose of this talk is to provide some feedback from the front lines of industrial research back to an academic environment, to describe some projects and trends that the audience may be interested in, and to entertain. "Dedicated to Jonathan Goldstine's retirement".

### Various Aspects of Descriptional Complexity of Grammars and Machines

The great Greek philosopher Socrates once stated that all he knows is that he knows nothing. As true as this might be - after all, what do we really know -, it might be just as impractical, especially in a knowledge-based world and environment. Just imagine that we get up to give a lecture and all we say is that we know nothing.

Virtually unthinkable!

But if we do get up and explain something, then we don't want the audience to react: "If you can't explain it in a way that I understand it, then I don't want to hear it." By the same token, we don't want the audience to say: "This sounds so simple that there really cannot be anything to it. Don't waste my time with trivia. "This brings us to the area of descriptional complexity, i.e., the science (sometimes the art) of making the description of things or objects as simple as possible and only as complex as necessary. In modification of Socrates' statement we would probably say:

I don't know

what I really know.

But, whatever I know,

I only know at all

what simple I can call.

This presentation will try to give a survey of how this very general principle has been applied to grammars and machines. It will purposely be quite non-technical and will thus allow non-experts as well to grasp al least the ideas of this line of research. It will also mention a few open - though difficult - problems to be solved by the next generation of computer scientists.

Dedicated to Jonathan Goldstine’s retirement.

### Transitive-closure Spanners

We define the notion of a transitive-closure spanner of a directed
graph. A transitive-closure spanner of a given directed graph is a
graph of small diameter that preserves connectivity of the original
graph. Formally, given a directed graph G = (V,E) and an integer k>=1,
a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph
H = (V, E_H) that has (1) the same transitive-closure as G and (2)
diameter at most k. These spanners were studied implicitly in
sublinear algorithms, access control, and data structures, and
properties of these spanners have been rediscovered over the span of
20 years. We bring these areas under the unifying framework of
TC-spanners. We abstract the common task implicitly tackled in these
diverse applications as the problem of constructing sparse
TC-spanners.

### Generalized Steiner Tree Problem with distances 1 and 2

Generalized Steiner Tree problem has the input in the form of a graph
with edge lengths and a list of node sets; a valid solution is a forest
(acyclic subset of edges) in which every required set is contained in one
of the trees (connected components). The goal is to minimize the cost.
A special case is when every distance between two nodes is either 1 or 2.
We show how to find solutions with cost no more than 1.5 times optimum (in
the general case, no ratio better than 2 is known).

Joint work with Marek Karpinski and Alex Zelikovsky.