|
|
FOCS 2007
48th Annual IEEE Symposium on Foundations of Computer Science October 20-23, 2007 Providence, RI |
|
 LOCAL
MAP |
| Call for Papers |
| Accepted Papers |
| Program |
| Tutorials |
| Registration |
| Hotel
Reservations |
| Travel info |
| Roommate matching |
| Travel
Support |
| Visa Requests |
| Organizing team |
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 7-9PM 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)
1:30 - 3:30 Tutorial 2 (Chair: Daniele Micciancio)
4:00 - 6:00 Tutorial 3 (Chair: Chris Umans)
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 7-9PM 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 pseudo-random
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
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 pseudo-random
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 Pairings-Based Cryptography
Over the past few years a new tool from algebraic geometry, called
bilinear groups, has transformed public-key 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 non-interactive zero-knowledge, and efficient
identity-based 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
A Brief Look at Pairings-Based Cryptography
Over the past few years a new tool from algebraic geometry, called
bilinear groups, has transformed public-key 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 non-interactive zero-knowledge, and efficient
identity-based 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
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