Amit Chakrabarti

|Professor
Academic Appointments

Professor of Computer Science

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.

Personal Website

Contact

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

Education

  • B.Tech., IIT Bombay
  • M.A., Princeton University
  • Ph.D., Princeton University

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

+ View more

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

Courses