Contact Information

Fifth year Ph.D. candidate,

Computer Science Department,

Stanford University.

466, Gates Computer Sceince, 51 Dudley Lane, Room 422,

Stanford CA94305. Stanford CA94305.

Ph: 650-723-4102 Ph: 650-248-4047

Email: kamesh@cs.stanford.edu

URL: http://theory.stanford.edu/~kamesh

• 
  Design and analysis of approximation algorithms
  
• 
  Data Mining and Bioinformatics
  
• 
  Design of high speed switches and routers
  
• 
  Clustering techniques and their applications
  

Stanford University,

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.
  

with Abhiram Ranade.

with Ashish Goel.

with Matthew Andrews.

* 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.

with Sudipto Guha and Adam Meyerson.

* 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.

with Adam Meyerson and Serge Plotkin.

with Sudipto Guha.

with Sudipto Guha.

with Zoe Abrams, Adam Meyerson and Serge Plotkin.

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.

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.

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 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.

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.

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.

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.

• 
  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.