NEW:
If you would like to
purchase the 2007 proceedings, you can shop online by going
of the page.Or you can contact
Customer Service at 1-800-701-4333 or at
The 48th Annual Symposium on Foundations
of Computer Science (FOCS 2007), sponsored by the IEEE Computer Society
Technical Committee on Mathematical Foundations of Computing, was held
on October 20-23, 2007, in Providence, Rhode Island. A tutorial program
took place on October 20, and the regular program began on October
21. The Knuth Prize lecture was be given by Nancy Lynch
on October 21.
Local Arrangements report at
business meeting
The conference venue is the Renaissance Hotel Providence: MAP
If you need a VISA to attend, please fill out the VISA application.
Read about FOCS by Nicole
Immorlica (guest blogging for Bill Gasarch),
Luca Trevisan, and Scott Aaronson!
The tutorials on Saturday, October
20 were held in Room 129 in Metcalf Laboratory (directions):
9.30-10.00: Coffee
and Snacks
10.00-12.00: Structure
and Randomness in Combinatorics
Terence Tao
(UCLA)
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.
1.30-3.30: A Brief Look at Pairings-Based
Cryptography
Dan Boneh (Stanford)
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.
4.00-6.00: Theory and Applications of Graph Spectra
Daniel
Spielman (Yale)
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.