Algorithms Research Group (ARG)

The research group in the design and analysis of algorithms is led by Professors Sriram Pemmaraju and Kasturi Varadarajan. The group's interests are broadly in theoretical computer science, and more specifically, they include approximation algorithms, computational geometry, distributed algorithms, and randomization.

Current PhD students

Sayan Bandyapadhyay • Tanmay Inamdar • Shreyas Pai • Talal Riaz

Two Sample Problems

As an algorithmic problem in computational geometry, suppose that we are given a set X of client locations and a set Y of server locations in the plane. At each of the servers is a disk whose radius we are free to set arbitrarily. We wish to find an assignment of radii such that the clients are covered by the resulting disks, while minimizing the cost, which is the sum of the disk areas. Such problems are typically NP-hard, so we look for an algorithm that has polynomial running time and approximately minimizes the cost. We would like a provable approximation guarantee, that is, a bound (hopefully small) on the ratio of the cost of the algorithms output to the cost of the optimal solution. Such an algorithm is called an approximation algorithm.

Now consider the graph coloring problem -- we have an undirected graph with n vertices and maximum degree d, and we wish to assign a color to each vertex so that the endpoints of each edge have different colors. A simple algorithm does the job with at most d + 1 colors. Now imagine that each vertex is a processsor, and each edge represents a direct communication link between two processors. We would like the vertices/processors to arrive at a coloring using a small number of communication rounds. This is the distributed graph coloring problem. In a round, each vertex can receive a (possibly different) message from each of its neighbors, do some computation, and send a (possibly different) message to each of its neighbours. The simple algorithm mentioned above uses d + 1 colors, but requires a large number of rounds as it is very sequential in nature. What can an algorithm that is allowed a very small number of rounds (logarithmic in n, or even smaller) do to minimize the number of colors used?

Illustrative References

ARG Alumni

• Rajiv Raman (2007, IIIT Delhi), • Benton McCune (2007, University of Iowa) • Kevin Lillis (2008, St. Ambrose University), • Imran Pirwani (2008, Apple Inc. Cupertino), • Erik Krohn (2009, University of Wisconsin Oshkosh), • Saurav Pandit (2010, Intent Media NYC) • Matt Gibson (2010, University of Texas at San Antonio) • Gaurav Kanade (2011, Microsoft Redmond) • Don Curtis (2011, Google Seattle) • James Hegeman (2016, Facebook, Menlo Park, California) • Vivek Sardeshmukh (2016, Cadence Design Systems, San José, California) • Rahil Sharma (2016, Synopsys Inc, Mountain View, California) • Santanu Bhowmick (2017, Apple, Cupertino, California)

Algorithms Reading Group Meetings

  • We meet every week to discuss recent research papers in Algorithms, Computational Geometry, Distributed Algorithms, etc. Here is the meeting schedule for Spring 2018.