Theoretical Computer Science Group

Theory Seminar Schedule - Fall 2008

Date Speaker Title
Aug 26, 2008 Sofya Raskhodnikova Transitive-closure Spanners
Sep 02, 2008 Sofya Raskhodnikova Transitive-closure Spanners (Continuned)
Sep 09, 2008 Shiva Kasiviswanathan Differential Privacy - Some Upper and Lower Bounds
Sep 16, 2008 Piotr Berman Generalized Steiner Tree Problem with distances 1 and 2
Sep 25, 2008 David Liben-Nowell Tracing Global-Scale Information Flow Using Internet Chain-Letter Data
Sep 29, 2008 Adam Smith Pinning Down "Privacy" in Statistical Databases
Oct 13, 2008 Cynthia Dwork Privacy: A Natural Resource to Be Conserved
Oct 21, 2008 Abhradeep Guha Thakurta Set Cover problem and its application to Shortest Superstring problem
Oct 28, 2008 Cancelled due to FOCS 2008
Nov 4, 2008 Huiwen Hu Hamiltonian path in a Random Graph
Nov 10, 2008 Scott Aaronson The Limits of Quantum Computers
Nov 11, 2008 Fang Song Shortest Vector Problem in Lattices - version and applications
Nov 19, 2008 Avi Wigderson The Art of Reduction
Dec 2, 2008 Fang Song Shortest Vector Problem in Lattices - version and applications [continued]
Dec 9, 2008 Piotr Berman Some sample Randomized Algorithms ( Minimum satisfiability of Linear Equations, Min cut in a graph, nearest pair in k-dimensions)

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.


Spring 2007     Fall 2007     Spring 2008    Summer 2008     Fall 2008     Spring 2009

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.