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: