Manager Computer Science

Amit Chakrabarti

abqp49@r.postjobfree.com

Objective: Seeking permanent or postdoc research position

beginning Fall 2002.

Interests: Algorithms and Complexity (incl. approximation

algorithms and lower bounds), Combinatorics, Geometry.

35 Olden Street, Princeton, NJ 08544, USA.

Phone: 609-***-****

Fax: 609-***-****

URL:

http://www.cs.princeton.edu/~amitc

Education

1997:

B.Tech. in,

.

GPA: 9.77/10 (Highest in the Class of '97)

1999:

M.A. in,

.

1997-present:

Computer Science Ph.D. candidate, Princeton University.

Advisor: Professor Bernard

Chazelle.

Academic Honors

Summer Research Fellow,

Summer 1998.

President of India

Gold Medallist of IIT Bombay's Class of 1997.

Silver Medallist at the International Mathematical Olympiad, 1993.

Ranked 69th amongst about 100,000 students nationwide in the

entrance examination for admission to the IITs, 1993.

National Talent Search Scholar, 1991 (about 750 awards per year,

countrywide).

Publications

A Lower Bound on the Complexity

of Approximate Nearest Neighbor Searching on the Hamming Cube.

Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov.

(To appear in Discrete and Computational Geometry, preliminary version

in STOC 1999)

Evasiveness of Subgraph Containment

and Related Properties. Amit Chakrabarti, Subhash Khot,

Yaoyun Shi. (To appear in SIAM Journal on Computing, preliminary version

in STACS 2001)

Improved Lower Bounds on the

Randomized Complexity of Graph Properties. Amit Chakrabarti,

Subhash Khot. (ICALP 2001)

Informational Complexity and the

Direct Sum Problem for Simultaneous Message Complexity.

Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Yao. (FOCS 2001)

Improved approximation algorithms for

resource allocation. Gruia Calinescu, Amit Chakrabarti, Howard

Karloff, Yuval Rabani. (IPCO 2002)

Approximation algorithms for the

unsplittable flow problem. Amit Chakrabarti, Chandra

Chekuri, Anupam Gupta, Amit Kumar. (Submitted)

Other Technical Writings

Amit Chakrabarti,

Ketan Mulmuley. Junior Thesis, IIT Bombay, 1996.

Randomized Graph Partitioning

Algorithms. Amit Chakrabarti,

.

Senior Thesis, IIT Bombay, 1997.

Work Experience

Summer 1996: Summer intern at

(formerly TISL), Bangalore, India. Designed programming exercises with

solutions to be used in teaching architecture

and assembly language to students and professionals.

Summer 2000:

Summer manager at AT&T Labs

research, Florham Park, New Jersey. Designed approximation

algorithms for combinatorial optimization problems in resource

constrained scheduling.

Summer 2001:

Summer intern at Bell

Laboratories, Murray Hill, New Jersey. Designed approximation

algorithms for the unsplittable flow problem in various types of

networks.

Programming Projects

Networks: Designed and implemented a node-fault tolerant

protocol for a multi-person game (Duplicate Scrabble).

Compilers: Wrote an optimizing compiler for a subset of pascal.

Numerical Computation: Implemented the QR method for determining

eigenvalues of matrices together with shifting and double-stepping.

Graphics: Wrote a

Java Rubik's cube applet

with GUI for viewing and manipulating the cube.

Database Management Systems: Implemented hybrid hash joins

for a mini database system ToyDB being developed at IIT Bombay.

Contact this candidate