Qian Zhang: Graph matching (survey and implementation)

Bochao Shen: Multicommodity facility location under Group Steiner
costs

Saber ShokatFadaee: Interacting networks

Hamid Jahanjou: Embedding graphs into trees

Zahra: Embedding graphs into trees

Ravishankar Rajagopal: Embedding graphs into trees

Travis Mayberry: Biclique Cryptanalysis of the Full AES 

Galen Wilkerson: 

Scott Roche: Branching-coalescing random walks

1. Algorithms for local clustering in massive graphs.

This project will survey recently proposed algorithms for local
clustering in large networks and experimentally evaluate one or more
of the proposed algorithms.  These algorithms all build on the
Lovasz-Simonovits theorem.  The goal of the project is to understand
the effectiveness of the proposed techniques and highlight the
implementation challenges.

References:

Spielman-Teng
Andersen et al

2. The structure of multiple interacting networks

Social networks are usually composed of multiple independent networks
that interact with one another through the nodes.  How these
interactions go between networks and how they affect the flow of
information among the networks is important to understand.  This
project will survey recent papers in this area, identify a research
problem and try to make progress on it.

Arora et al

Li Tang et al

3. Higher Eigenvalues and multi-way partitioning.

Recently, there has been a burst of results on what higher eigenvalues
of (say the Laplacian) tell about the sparsity of k-way cuts, in the
same sense as what the dimension of the null space tells about
connectivity and the second smallest eigenvalue says about sparsest
cut.  This project would be a survey of recent results in this space,
identify a problem in this space, and report attempts to solve it.

Lee, Trevisan

Tetali, Vempala

4. Embedding graphs into trees

Consider the problem of embedding an arbitrary "guest" graph into a
"host" graph.  Such a problem arises in diverse settings, the most
common one being of implementing a long-running distributed program
(collection of communicating processes) in a physical network.  The
guest graph represents the program and the host graph represents the
physical network.  This is a well-studied problem for special classes
of (mostly regularly structured) graphs.  I believe the problem of
embedding an arbitrary graph into trees is still open, and would be of
interest.  



5. Branching-coalescing random walks.

A branching-coalescing random walk starts at an arbitrary vertex, then
continually branches from each currently visited vertex to a subset of
its neighbors and coalesces (walks from multiple neighbors arriving at
a node coalesce).  Branching-coalescing random walks (BCRWs) are
related to the SIS epidemic model and the associated contact process.
The goal of this project is to analyze the cover time of BCRWs on
general and special classes of graphs.

Dutta et al.

6. Multicommodity Facility Location in Network Design.

This project concerns a multicommodity facility problem in which we
have a set of clients wanting access to a service that can be
multicast to them from a set of facilities/servers.  The goal of the
problem is to determine the location of the facilities and design the
multicast network so as to minimize cost.  This is an NP-hard problem
for which there is a big gap between the best upper and lower bounds
on the approximation ratio.  The aim of the project is to develop
improved algorithms for the problem and try to close the gap.

Poplawski and Rajaraman,