Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!snorkelwacker!apple!agate!ucbvax!RESEARCH.ATT.COM!jf From: jf@RESEARCH.ATT.COM Newsgroups: comp.theory Subject: Dec. 11, DIMACS Message-ID: Date: 28 Nov 89 14:26:09 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Theory-B - TheoryNet Ongoing Seminars and Lectures , jf@research.att.com Lines: 74 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! Brought to you by Super Global Mega Corp .com