# Differences

This shows you the differences between two versions of the page.

 en:projects:details:ola1 [2011/09/26 12:54]osven created en:projects:details:ola1 [2016/06/23 11:26] Line 1: Line 1: - /* 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 - "​status"​ 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 - status : available - 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. Based on - the student'​s interests this can be both a theoretical and practical study. - A theoretical study would aim towards understanding recent developments - where - better (theoretical) algorithms have been given for fundamental problems - by the use of spectral methods. A more practical study would instead aim - towards implementing some of the algorithms (e.g., clustering) - and analyze their performance. - - The prerequisite is being comfortable with the basics of graph theory and - discrete mathematics;​ and programming if the practical direction is chosen.