Participation to the tutorials is free of additional charge for FOCS participants, but prior registration is required (see FOCS registration form).

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