FOCS 2007
From ResearchWiki
Location: http://focs2007.org/
Contents |
Tutorials
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.
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.
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.
