

NEW: If you would like to
purchase the proceedings, you can shop online by going
to the IEEE home page http://www.ieee.org, and clicking the
shop link at the top
of the page. Or you can contact
Customer Service at 18007014333 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 2023, 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. Combinatorics, like computer
science, often has to deal
1.303.30: A Brief Look at PairingsBased
Cryptographywith 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. Dan Boneh (Stanford) Over the past few years a new
tool from algebraic geometry, called
4.006.00: Theory and Applications of Graph Spectrabilinear 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. 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. IEEE CS  ACM  SIGACT
 SODA '08
 STOC '08
 SODA '07  STOC '07  FOCS '06
