You may be using a Web browser that does not support standards for accessibility and user interaction. Find out why you should upgrade your browser for a better experience of this and other standards-based sites...
B.Tech. Indian Institute of Technology (IIT); M.A. Princeton University; Ph.D. Princeton University
Areas of Expertise
Discrete mathematics; algorithms and data structures, complexity theory, with an emphasis on lower bounds in non-uniform models of computation, approximation algorithms especially for combinatorial optimization problems
Selected Works
Chakrabarti, A, K Do Ba, and S Muthukrishnan, "Estimating Entropy and Entropy Norm on Data Streams," STACS 2006, the 23rd Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 3884, (2006) 196-205.
Chakrabarti, A and O Regev, "An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbor Searching," FOCS 2004, the 45th Annual Symposium on Foundations of Computer Science, (2004) 473-482. Invited to FOCS 2004 special issue by SIAM Journal on Computing.
Chakrabarti, A, Y Wang and F Makedon, "R-Histograms: Efficient Representation of Spatial Relations between Objects of Arbitrary Topology," in Proceedings of the 12th Annual ACM International Conference on Multimedia, (2004) 356-359.
Chakrabarti, A, B Chazelle, B Gum, and A Lvov, "A Lower Bound on the Complexity of Approximate Nearest Neighbor Searching on the Hamming Cube," Discrete and Computational Geometry: The Goodman-Pollack Festschrift, (2003) 313-328.
Chakrabarti, A, S Khot and Y Shi, "Evasiveness of Subgraph Containment and Related Properties," Journal on Computing, 31:3 (2002) 866-875.
Current Projects
"Improved Lower Bounds on the Randomized Complexity of Graph Properties;" "Estimating Entropy and Entropy Norm on Data Streams;" "Approximation Algorithms for the Unsplittable Flow Problem"
