Davidson Fellows - 2012 Fellow Sitan Chen


         

Sitan Chen

$10,000 Scholarship Recipient

Age: 17
Suwanee, GA
Category: Mathematics
Project Title: “On the Rank Number of Grid Graphs.”________ ________ _________ ________

 
 


Sitan’s project, “On the Rank Number of Grid Graphs,” studies the “k-ranking” problem, a problem in graph theory with applications in parallel scheduling, search, and processing as well as in VLSI circuit design. The problem asks to assign integer labels to the vertices of a graph so that any path between two vertices of the same label passes through a vertex of a greater label. The least number of labels with which one can do this is called the rank number, and for grid graphs, a class of graphs of special interest in circuit design, this rank number is unknown if the number of rows exceeds three. In Sitan’s work, he determined the rank number for grids of width four using methods that could be generalized to greater dimensions, found improved upper bounds for the rank number of general grids, and tightened lower bounds on the rank number for square grids from logarithmic to linear. In particular, this last result has in some sense been the missing piece in the process of completely determining the rank number of all grids, and the novel methods he used to find new lower bounds have implications on minimal separators, a property of graphs closely tied to circuit design and parallel algorithm optimization.

K-ranking is closely tied to optimizing a multitude of parallel algorithms, ranging from manufacturing products using machines that work in conjunction, to searching for corruptions in data structures, to executing computationally difficult tasks by simultaneously carrying out the associated sub-tasks. The rank number can be interpreted to be a “magic number” that describes the most efficient procedure and least number of steps needed to build automobiles in a factory, pinpoint errors in computer data, and solve problems like climate analysis, medical imaging, and oil exploration using parallel computing. Moreover, the insights Sitan’s work shed light on minimal separators, which is the most efficient ways to cut a graph into pieces, may also lead to more area-efficient circuit design. Sitan’s project may lead to methods for designing more cost-effective electronic devices, streamlining computing, computer error detection, and manufacturing.

Sitan participated in the Research Science Institute (RSI) at the Massachusetts Institute of Technology (MIT) and is a freshman at Harvard College, and hopes to concentrate in some combination of mathematics and economics.



Photos:
Click the links below to view hi-res photos of Sitan:
 
 
     

View Photo 1 > 

View Photo 2 > 

View Photo 3 > 

View Photo 4 > 

 

NEXT >

Click here to view the full listing of the 2012 Davidson Fellows. 
Click here to view Sitan's press release.

For all media inquiries, please contact DavidsonFellowsMedia@davidsongifted.org


Email this Page Email this Page