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.

### 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.