jf@RESEARCH.ATT.COM (11/28/89)
Enclosed please find a final schedule for the December 11
DIMACS Seminar at Princeton. There has been a slight change:
the lunch break has been extended by 1/2-hour (and all afternoon
events pushed 1/2-hour later) in order to give people time to
go out to eat. Unfortunately, we won't be able to serve lunch
(as we did in the past and will in the future).
**************************************************************************
DIMACS Seminar at Princeton, Monday, December 11, 1989.
10-10:30 Coffee
10:30-11:30 The Second Eigenvalue of Hypergraphs
Joel Friedman (Princeton)
Abstract:
We define a notion of second eigenvalue for regular hypergraphs.
It turns out that a random hypergraph has a very small second
eigenvalue. A class of applications of graphs with small second
eigenvalue would be greatly improved if we could explicity
construct hypergraphs with as small a second eigenvalue as random
ones have. Unfortunately we have no such constructions as yet.
In this talk we define the second eigenvalue, discuss the second
eigenvalue of random hypergraphs, discuss some constructions and
applications.
Joint work with Avi Wigderson.
12-2 Lunch
2-3 Performance Guarantees for the Independent Set Problem
Ravi Boppana (NYU)
Abstract:
Suppose someone tells you that a graph on n vertices has a
large independent set (a constant fraction of all the vertices), but
does not tell you where it is. How large an independent set can you
find? This talk will show how to find in polynomial time an
independent set of size some root of n. The idea is to connect this
problem with some results from graph Ramsey theory. We will also see
that the Ramsey-theory approach cannot be pushed much farther. The
talk will include some connections between this work and approximation
algorithms for the vertex cover problem and the graph coloring
problem.
Joint work with Magnus Halldorsson.
3-3:30 Coffee break
3:30-4:30 A Markovian Extension of Valiant's Learning Model
Umesh Vazirani (Berkeley)
Directions:
Park in Lot 21, which you reach as follows: Assume you start
on Nassau Street (a.k.a. Rt. 27) going southwest (i.e., away from
New Brunswick, towards Trenton). Turn left on Washington Road
(at a light). Drive on Washington past Fine Hall and Palmer
Stadium. Turn left onto Faculty Road (at a light). If you
get to a bridge, you have gone too far. The first real street
onto which you can turn left off Faculty is Fitzrandolf. (There
is a previous left, but it is into an alley as opposed to a real
street.) Take that left, and Lot 21 is on your left.
The talks will take place in the new Computer Science Building, on the
corner of William and Olden Streets. To get there
from Lot 21, go back to Fitzrandolf and walk in the same direction
in which you were driving before you entered the lot. Go left
on Prospect and take your next right, which is Olden. The Computer
Science building is the large new building on the left side of the street.
It takes 10 to 15 minutes to walk from Lot 21 to the Computer Science
Building. So allow enough time!