/* This is the template for project details pages */

/* 
  The database entry:
  "type" is one of the following: phd theses, phd semester, master thesis, master semester, bachelor semester
  "state" is one of the following: available, taken, completed (please upgrade accordingly!!!!!!!!!!) 
  "by" should be filled as soon as the project is taken/completed
  "completed_dt" is the date when the project was completed (YYYY-MM-DD). 
  "output_media" is the link to the pdf of the project (wiki syntax)
  "table" must be "projects" => don't touch it!
*/
---- dataentry project ----
title : Spectral graph theory and its applications in algorithms
contactname: Ola Svensson
contactmail_mail: ola.svensson@epfl.ch
contacttel: 31204
contactroom: BC128
type : master semester
state : unavailable
created_dt : 2011-09-26
taken_dt : YYYY-MM-DD
completed_dt : YYYY-MM-DD
by : the full name of the student
output_media : en:projects:mahdi_thesis.pdf|Download Mahdi's Thesis
table : projects
======
template:datatemplates:project
----

/* Description of the project */
Spectral graph theory is a rich and powerful theory that relates
various graph properties with the eigenvalues and eigenvectors of matrices
associated to the graph, such as its adjacency matrix.

One of the most famous results is Cheeger's inequality that relates the
expansion of a graph with the second largest eigenvalue of its adjacency
matrix. In addition to being an interesting theoretical result, Cheeger's
inequality has found numerous algorithmic applications in clustering, image
analysis, etc..

After reviewing the basics of spectral graph theory, the aim of this
project is to understand its various algorithmic applications in theory. The study would aim towards understanding recent developments
where
better (theoretical) algorithms have been given for fundamental problems
by the use of spectral methods (often combined with the use of semidefinite programs). 

The prerequisite is being comfortable with the basics of graph theory and
discrete mathematics.