Amit Chakrabarti

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.


Engineer and Comp Science Ctr, Room 111
HB 6211


Computer Science


  • 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