Contact Information

Download 24.89 Kb.
Size24.89 Kb.
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: 650-723-4102 Ph: 650-248-4047



Research Interests:

  • Design and analysis of approximation algorithms

  • Data Mining and Bioinformatics

  • Design of high speed switches and routers

  • Clustering techniques and their applications


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. (1994-98)

Advisor: Abhiram G. Ranade

Thesis: External Memory Graph Algorithms
Academic Honors:

  • First in IIT-JEE-1994, 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 ACM-SIAM 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 ACM-SIAM Symposium on Discrete Algorithms, 2000.
* Online Algorithms for Caching Multimedia Streams.

with Matthew Andrews.

Proceedings of 8th European Symposium on Algorithms, 2000.

* Cost-Distance: 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 ACM-SIAM Symposium on Discrete Algorithms , 2001.
* Improved Algorithms for Fault Tolerant Facility Location.

with Sudipto Guha and Adam Meyerson.

Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms, 2001.

* Constant-factor Approximation for the Single-sink Edge Installation Problem.

with Sudipto Guha and Adam Meyerson.

Proceedings of 33rd ACM Symposium on Theory of Computing, 2001.
* Local Search Heuristics for k-medians 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 ACM-SIAM Symposium on Discrete Algorithms, 2002.
* Generalized Clustering Problems.

with Sudipto Guha.

Proceedings of 13th ACM-SIAM Symposium on Discrete Algorithms, 2002.
* On the Integrality Gap of Capacitated Facility Location.

with Zoe Abrams, Adam Meyerson and Serge Plotkin.

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.

* January-May 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 time-series and microarray image data, and clustering of molecular structure data in a drug database.

* January-April 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 NP-Hard 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
* 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.

* 1997-98:

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 8-bit multiplier using VHDL, implementation on an FPGA, and interfacing with an 8085.

  • Game of anti chess in Pascal, using techniques from A.I.

C, C++, Perl, SQL, Verilog, VHDL.

Other Interests:
Reading, Crosswords, Hiking, Tennis, Travel.

Serge Plotkin

Associate Professor

Computer Science Department,

Gates 4B, Stanford CA 94305.


Ramesh Hariharan

CTO, Strand Genomics and

Associate Professor, CSA Department,

Indian Institute of Science, Bangalore - 560012


Matthew Andrews

Math of Network and Systems Group

Bell Laboratories,

Murray Hill NJ 07974.


Baruch Schieber

Manager, Mathematical Sciences Group,

IBM TJ Watson Research Center

Yorktown Heights NY 10598


S. Seshadri

CEO, Strand Genomics

# 237, Sir C.V. Raman Avenue,

Rajmahal, Bangalore-560080


Abhiram Ranade

Professor, CSE Department,

Indian Institute of Technology Bombay

Powai, Mumbai - 400076


Download 24.89 Kb.

Share with your friends:

The database is protected by copyright © 2020
send message

    Main page