Graph Partitioning and Expanders

Provided by:
0/10 stars
based on  0 reviews
Provided by:
Cost FREE
Start Date TBA

Course Details

Cost

FREE

Upcoming Schedule

  • TBA

Course Provider

NovoEd online courses
With NovoEd, you can learn from the world's leading institutions and collaborate with students from more than 150 countries across the globe. This online education platform connects millions of students to MOOcs, or Massive Open Online Courses, to provide them with a one-of-a-kind learning experience. Students develop an understanding of the content through worthwhile projects and collaborating with their peers. You can create a learning experience that is entirely suited to your needs and...
With NovoEd, you can learn from the world's leading institutions and collaborate with students from more than 150 countries across the globe. This online education platform connects millions of students to MOOcs, or Massive Open Online Courses, to provide them with a one-of-a-kind learning experience. Students develop an understanding of the content through worthwhile projects and collaborating with their peers. You can create a learning experience that is entirely suited to your needs and preferences by responding to student learning as it happens. You can essentially shape your instruction to make the online classes more effective and productive. Through innovative technology, in-depth academic relationships with peers around the world, and instruction from distinguished professors at top universities, you can become an expert on anything from finance to decision quality.

Provider Subject Specialization
Business & Management
18 reviews

Course Description

In this research-oriented graduate course, we will study algorithms for graph partitioning and clustering, constructions of expander graphs, and analysis of random walks. These are three topics that build on the same mathematical background and that have several important connections: for example it is possible to find graph clusters via random walks, and it is possible to use the linear programming approach to graph partitioning as a way to study random walks.

 

 

We will study spectral graph theory, which explains how certain combinatorial properties of graphs are related to the eigenvalues and eigenvectors of the adjacency matrix, and we will use it describe and analyze spectral algorithms for graph partitioning and clustering. Spectral graph theory will recur as an important tool in the rest of the course. We we will also discuss other approaches to graph partitioning via linear programming and semidefinite programming. ...

In this research-oriented graduate course, we will study algorithms for graph partitioning and clustering, constructions of expander graphs, and analysis of random walks. These are three topics that build on the same mathematical background and that have several important connections: for example it is possible to find graph clusters via random walks, and it is possible to use the linear programming approach to graph partitioning as a way to study random walks.

 

 

We will study spectral graph theory, which explains how certain combinatorial properties of graphs are related to the eigenvalues and eigenvectors of the adjacency matrix, and we will use it describe and analyze spectral algorithms for graph partitioning and clustering. Spectral graph theory will recur as an important tool in the rest of the course. We we will also discuss other approaches to graph partitioning via linear programming and semidefinite programming. Then we will study constructions of expander graphs, which are graphs with very strong pseudorandomness properties, which are useful in many applications, including in cryptography, in complexity theory, in algorithms and data structures, and in coding theory. Finally, we will study the mixing time of random walks, a problem that comes up in several applications, including the analysis of the convergence time of certain randomized algorithms, such as the Metropolis algorithm.

 

 

Workload 
about 8 hours per week

 

 

Prerequisites 
linear algebra, discrete probability, and algorithms


Graph Partitioning and Expanders course image
Reviews 0/10 stars
0 Reviews for Graph Partitioning and Expanders

Ratings details

  • 5 stars
  • 4 stars
  • 3 stars
  • 2 stars
  • 1 stars
  • 5 stars
  • 4 stars
  • 3 stars
  • 2 stars
  • 1 stars
  • 5 stars
  • 4 stars
  • 3 stars
  • 2 stars
  • 1 stars

Rankings are based on a provider's overall CourseTalk score, which takes into account both average rating and number of ratings. Stars round to the nearest half.

No reviews yet. Be the first!

Rating Details


  • 5 stars
  • 4 stars
  • 3 stars
  • 2 stars
  • 1 stars
  • 5 stars
  • 4 stars
  • 3 stars
  • 2 stars
  • 1 stars
  • 5 stars
  • 4 stars
  • 3 stars
  • 2 stars
  • 1 stars

Rankings are based on a provider's overall CourseTalk score, which takes into account both average rating and number of ratings. Stars round to the nearest half.