

IEEE CS
 ACM
 SIGACT
 ASQA
 SODA 08
 STOC 08
 SODA 07
 STOC 07
 FOCS 06
Corporate Endowment 
Practical information Participation to the tutorials is free of additional charge for FOCS participants, but prior registration is required. Tutorials will take place on the Brown University Campus in Room 129 in Metcalf Laboratory, at the corner of Waterman Street and Thayer street (see the local map). This is very close to the Brown Computer Science department (at the corner of Waterman Street and Brook Street). Participants will be on their own for lunch, with many possibilities available on Thayer street. A reception will follow from 79PM at the conference hotel. Tutorial schedule Saturday, October 20, 2007 9:30  10:00 Coffee and Snacks 10:00  12:00 Tutorial 1 (Chair: Luca Trevisan) Terence Tao (UCLA)
Structure and Randomness in Combinatorics Combinatorics, like computer science, often has to deal with large objects of unspecified (or unusable) structure. One powerful way to deal with such an arbitrary object is to decompose it into more usable components. In particular, it has proven profitable to decompose such objects into a structured component, a pseudorandom component, and a small component (i.e. an error term); in many cases it is the structured component which then dominates. We illustrate this philosophy in a number of model cases. Slides Notes Movies 1:30  3:30 Tutorial 2 (Chair: Daniele Micciancio) Dan Boneh (Stanford)
A Brief Look at PairingsBased Cryptography Over the past few years a new tool from algebraic geometry, called bilinear groups, has transformed publickey cryptography. Bilinear groups enable the development of a new generation of cryptosystems that solve long standing open problems in cryptography and provide brand new functionality. A few examples include, short digital signatures, perfect noninteractive zeroknowledge, and efficient identitybased encryption. In this tutorial we will discuss some of the mathematical tools underlying bilinear groups, including the Weil pairing and Miller's algorithm. Our focus, however, will be on a few key examples that illustrate how bilinear groups are used to construct cryptosystems. Slides Movies 4:00  6:00 Tutorial 3 (Chair: Chris Umans) Daniel Spielman (Yale)
Theory and Applications of Graph Spectra In this lecture, we will study the eigenvalues and eigenvectors of the Laplacian and normalized Laplacian matrices of graphs. Our first goal will be to provide intution as to why these eigenvectors and eigenvalues should reveal combinatorial structure. We will examine applications of eigenvectors and eigenvalues to drawing, ranking, partitioning, clustering and coloring problems in graphs. We will also discuss connections to random walks in graphs, and how they inspire applications of graph spectra in machine learning and image segmentation. We will conclude with a discussion of the theory and practice of computing eigenvalues and eigenvectors, and how results from spectral graph theory may be applied to accelerate those computations. We will supply examples you can try at home using either Matlab or Python. Slides Movies
