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.
Archives
Spring 2007 Fall 2007 Spring 2008 Summer 2008 Fall 2008 Spring 2009 Fall 2009 Spring 2010 Fall 2010 Spring 2011 Fall 2011 Spring 2012 Fall 2012 Spring 2013 Fall 2013 Fall 2014 Spring 2015 Fall 2015 Spring 2016 Fall 2016
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.
Recent Comments