Theory Seminar Schedule – Summer 2008
| Date | Speaker | Title |
|---|---|---|
| July 25, 2008 | Shiva Kasiviswanthan | Approximation Algorithms For Graph Problems (Shiva’s PhD Defense) |
| Aug 08, 2008 | Reinhard Klemm | A Theoretician’s Perspective of 12 Years in Industrial Research (in Honor of Jonathan Goldstine’s retirement) |
| Aug 08, 2008 | Detlef Wotschke | Various Aspects of Descriptional Complexity of Grammars and Machines (in Honor of Jonathan Goldstine’s retirement) |
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
Approximation Algorithms for Graph Problems
The talk will be divided into three parts:
1) Approximation Algorithms for Counting Problems: I will introduce and motivate approximate counting. I will focus on counting occurrences of a fixed subgraph in a given input graph and will present a randomized scheme for this problem which works for a large class of subgraphs (RANDOM 2008, joint work with Martin Furer).
2) Approximation Algorithms for Geometric Problems: I will present fast approximation algorithms for some geometric distance problems arising in the context of wireless and cellular networks (WADS 2007, joint work with Martin Furer).
3) Database Privacy: I will present a definition of privacy and discuss what classes of (machine) learning problems can be solved in a private manner (FOCS 2008, joint work with Homin Lee, Kobbi Nissim, Sofya Raskhodnikova and Adam Smith).
The talk will be self-contained.
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.
Recent Comments