Resume of Kamesh Munagala
Fifth year Ph.D. candidate,
Computer Science Department,
Stanford University.
Contact Information:
Office: Residence:
466, Gates Computer Sceince, 51 Dudley Lane, Room 422,
Stanford CA94305. Stanford CA94305.
Ph: 6507234102 Ph: 6502484047
Email: kamesh@cs.stanford.edu
URL: http://theory.stanford.edu/~kamesh
Research Interests:

Design and analysis of approximation algorithms

Data Mining and Bioinformatics

Design of high speed switches and routers

Clustering techniques and their applications
Education:
Stanford University,
Ph.D. in Computer Science (Sept 1998 present)
Advisor: Serge A. Plotkin
Thesis: Facility Location Variants and their Applications to Network Design
Indian Institute of Technology Bombay,
B.Tech. in Computer Science and Engg. (199498)
Advisor: Abhiram G. Ranade
Thesis: External Memory Graph Algorithms
Academic Honors:

First in IITJEE1994, the Joint Entrance Examination for admission to the Indian Institutes of Technology(IITs).

Second in the CSE department in my undergraduate studies at IIT Bombay. GPA: 9.71 on a scale of 10.

First in the IIT Bombay Mathematics Olympiad, 1995 conducted by the Department of Mathematics, IIT Bombay.

National Talent Search Scholarship, 1992. The Govt of India awards this scholarship.
Publications (in chronological order):
* I/O Complexity of Graph Algorithms.
with Abhiram Ranade.
Proceedings of 10th ACMSIAM Symposium on Discrete Algorithms, 1999.
* Extending Greedy Multicast Routing to Delay Sensitive Applications.
with Ashish Goel.
Algorithmica special issue on Internet Algorithms (to appear)
Short version in Proc. 11th ACMSIAM Symposium on Discrete Algorithms, 2000.
* Online Algorithms for Caching Multimedia Streams.
with Matthew Andrews.
Proceedings of 8th European Symposium on Algorithms, 2000.
* CostDistance: Two Metric Network Design.
with Adam Meyerson and Serge Plotkin.
Proceedings of 41st IEEE Symposium on Foundations of Computer Science , 2000.
* Hierarchical Placement and Network Design Problems.
with Sudipto Guha and Adam Meyerson.
Proceedings of 41st IEEE Symposium on Foundations of Computer Science , 2000.
* Web Caching using Access Statistics.
with Adam Meyerson and Serge Plotkin.
Proceedings of 12th ACMSIAM Symposium on Discrete Algorithms , 2001.
* Improved Algorithms for Fault Tolerant Facility Location.
with Sudipto Guha and Adam Meyerson.
Proceedings of 12th ACMSIAM Symposium on Discrete Algorithms, 2001.
* Constantfactor Approximation for the Singlesink Edge Installation Problem.
with Sudipto Guha and Adam Meyerson.
Proceedings of 33rd ACM Symposium on Theory of Computing, 2001.
* Local Search Heuristics for kmedians and Facility Location Problems.
with Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson and Vinayaka Pandit.
Proceedings of 33rd ACM Symposium on Theory of Computing, 2001.
* Designing Networks Incrementally.
with Adam Meyerson and Serge Plotkin.
Proceedings of 42nd IEEE Symposium on Foundations of Computer Science , 2001.
* Improved Algorithms for the Data Placement Problem.
with Sudipto Guha.
Proceedings of 13th ACMSIAM Symposium on Discrete Algorithms, 2002.
* Generalized Clustering Problems.
with Sudipto Guha.
Proceedings of 13th ACMSIAM Symposium on Discrete Algorithms, 2002.
* On the Integrality Gap of Capacitated Facility Location.
with Zoe Abrams, Adam Meyerson and Serge Plotkin.
Submitted.
Work Experience:
* Sept 1998  Present:
Research Assistant, CSD, Stanford.
Advisor: Serge Plotkin.
The main focus of my work has been the design of approximation and online algorithms for problems arising in data networks and in clustering. The publications are listed above.
* JanuaryMay 2002:
Consultant, Strand Genomics, Bangalore, India.
Manager: Dr. Ramesh Hariharan.
Developed general purpose clustering and statistical relevance tools for large scale medical informatics applications. In particular, performed statistical analysis of timeseries and microarray image data, and clustering of molecular structure data in a drug database.
* JanuaryApril 2002:
Instructor, Dept. of Computer Science and Automation, Indian Institute of Science, Bangalore
Taught a complete graduate level course titled EO325: "Topics in Algorithms" to a class of 16 students. The focus of the course was Approximation Algorithms for NPHard problems and algorithms with low space complexity. It involved 3 hours of lecturing a week for a whole semester. The Indian Institute of Science is a premier research institute. The course web page is at http://theory.stanford.edu/~kamesh/iisc.html
* Summer 2001:
Intern, Mathematical Sciences Division, IBM Thomas J Watson Research Center.
Mentor: Baruch Schieber.
Analysis of a simple greedy scheme for online buffer management in a shared memory output queued switch. Improved the existing upper and lower bounds for special cases of this problem.
* Summer 2000:
Intern, Math of Networks and Systems group, Bell Labs, Murray Hill, NJ.
Mentor: Matthew Andrews.
Designed a fast and scalable packet switch scheduling algorithm for a new type of scheduling problem. Instead of scheduling packet by packet, the scheduler collects packets in an "envelope" and schedules them at once. Did extensive simulations of the algorithm as well as an implementation in Verilog HDL. It was shown by simulation that the algorithm is very good in terms of stability and delays, and that the algorithm can be implemented to work very fast in hardware.
* Summer 1999:
Intern, Math of Networks and Systems group, Bell Labs, Murray Hill.
Mentor: Matthew Andrews.
Worked on two separate problems related to computer networks. In the first problem, we designed a new algorithm for caching when the data to be cached is a multimedia clip requested by many users. The requests made by the users are temporally different, but the content to be served is the same. We show near optimal competitiveness. Work appeared in ESA '00. In the second problem, we designed placement and load balancing algorithms for the Lucent IPWorX web caching system.
* 199798:
Senior Thesis, IIT Bombay.
Advisor: Abhiram Ranade.
Worked on external memory graph algorithms. Showed improved upper bounds for graph connectivity, and came up with a simple implementation of BFS in external memory. We also presented the first known lower bounds in a slightly restricted model of computation. Work appeared in SODA '99.
* Spring 1997:
Junior Term Paper, IIT Bombay.
Advisors: Ketan Mulmuley and Sundar Vishwanathan.
Presented a home paper titled McMullen's Conditions for Simple Polytopes, which starts with a study of the basic combinatorial properties of polytopes, and then goes into McMullen's Conditions, the proof of their sufficiency, and the Polytope Algebra.
Programming Projects:

Design and Implementation of a switch scheduler for an input queued switch in Verilog HDL, with simulation and timing analysis (joint work with Matthew Andrews)

Application layer implementation of the greedy algorithm for constructing multicast trees for the Stanford WebBase. (Joint work with Ashish Goel)

Compiler for a subset of Pascal using C, Lex and Yacc. The output was SPARC assembly code.

Design and implementation of a RS232 serial receiver in hardware.

Interpreter for a subset of VHDL using compiler generation tools.

Design of a signed 8bit multiplier using VHDL, implementation on an FPGA, and interfacing with an 8085.

Game of anti chess in Pascal, using techniques from A.I.
Languages:
C, C++, Perl, SQL, Verilog, VHDL.
Other Interests:
Reading, Crosswords, Hiking, Tennis, Travel.
References:
Serge Plotkin
Associate Professor
Computer Science Department,
Gates 4B, Stanford CA 94305.
Email: plotkin@cs.stanford.edu

Ramesh Hariharan
CTO, Strand Genomics and
Associate Professor, CSA Department,
Indian Institute of Science, Bangalore  560012
Email: ramesh@strandgenomics.com

Matthew Andrews
Math of Network and Systems Group
Bell Laboratories,
Murray Hill NJ 07974.
Email: andrews@research.belllabs.com

Baruch Schieber
Manager, Mathematical Sciences Group,
IBM TJ Watson Research Center
Yorktown Heights NY 10598
Email: sbar@us.ibm.com

S. Seshadri
CEO, Strand Genomics
# 237, Sir C.V. Raman Avenue,
Rajmahal, Bangalore560080
Email: seshadri@strandgenomics.com

Abhiram Ranade
Professor, CSE Department,
Indian Institute of Technology Bombay
Powai, Mumbai  400076
Email: ranade@cse.iitb.ernet.in
 