Amit Chakrabarti

Professor

Appointments

Professor of Computer Science

Area of Expertise

Theory of computation including computational complexity, with an emphasis on lower bounds,

Discrete mathematics,

Algorithms and data structures, with an emphasis on algorithms for massive data streams, and for combinatorial optimization.

Biography

I am interested broadly in theoretical computer science: the study and discovery of fundamental computational principles that are mathematical truths, unaffected by changes in computing technology and hardware.

Education

B.Tech., IIT Bombay

M.A., Princeton University

Ph.D., Princeton University

Publications

A. Chakrabarti, G. Cormode, A. McGregor, J. Thaler, and S. Venkatasubramanian. “Verifiable Stream Computation and Arthur–Merlin Communication,” (with G. Cormode, A. McGregor, J. Thaler, S. Venkatasubramanian), in Proc. 30th Ann. Conf. Comput. Complexity (CCC 2015).

A. Chakrabarti, L. K. Fleischer, C. Weibel. “When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks,” in Proc. 44th Ann. ACM Symp. Theory Comput. (STOC 2012) 19-26.

A. Chakrabarti and O. Regev. “An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance”, SIAM J. Comput.41:5 (2012) 1299-1317.

A. Chakrabarti, G. Cormode and A. McGregor. “ A Near-Optimal Algorithm for Estimating the Entropy of a Stream,” ACM Trans. Alg., 6:3 (2010) Art. 51.

A. Chakrabarti and O. Regev. “An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching,” SIAM J. Comput.39:5 (2010) 1919–1940.

A. Chakrabarti, S. Khot, and Y. Shi. “Evasiveness of Subgraph Containment and Related Properties,” SIAM J. Comput.31:3 (2002) 866-875.

Works in Progress

Developing the connections between information theory and computational complexity

Algorithms for analyzing large graphs using limited memory

Algebraic techniques and problems in computational complexity

Thorough study of the complexity of fundamental communication problems

Selected Works & Activities

Organizer of workshop on Communication Complexity and Applications (Banff, Canada)

Organizer of program on Inference Problems, part of IHP thematic program on the Nexus of Information and Computation Theories (Paris, France)

Contact

Amit.Chakrabarti@dartmouth.edu
6-1710
Engineer and Comp Science Ctr, Room 111
HB 6211

Departments

Computer Science

Related Links