Amit Chakrabarti

Bing Citeseer DBLP Google Google Scholar Kosmix Wikipedia Yahoo!
Loading Google Thumbnails...
2012
40A note on randomized streaming space bounds for the longest increasing subsequence problem. Amit Chakrabarti. Inf. Process. Lett. (112): 261-263 (2012). Web SearchBibTeXDownload
2011
39An improved approximation algorithm for resource allocation. Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani. ACM Transactions on Algorithms (7): 48 (2011). Web SearchBibTeXDownload
38The query complexity of estimating weighted averages. Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth. Acta Inf. (48): 417-426 (2011). Web SearchBibTeXDownload
37Everywhere-Tight Information Cost Tradeoffs for Augmented Index. Amit Chakrabarti, Ranganath Kondapally. APPROX-RANDOM 2011, 448-459. Web SearchBibTeXDownload
36Robust Lower Bounds for Communication and Stream Computation. Amit Chakrabarti, Graham Cormode, Andrew McGregor. Electronic Colloquium on Computational Complexity (ECCC) (18): 62 (2011). Web SearchBibTeXDownload
35Combinatorial theorems about embedding trees on the real line. Amit Chakrabarti, Subhash Khot. Journal of Graph Theory (67): 153-168 (2011). Web SearchBibTeXDownload
34An optimal lower bound on the communication complexity of gap-hamming-distance. Amit Chakrabarti, Oded Regev. STOC 2011, 51-60. Web SearchBibTeXDownload
2010
33A near-optimal algorithm for estimating the entropy of a stream. Amit Chakrabarti, Graham Cormode, Andrew McGregor. ACM Transactions on Algorithms (6) (2010). Web SearchBibTeXDownload
32Better Gap-Hamming Lower Bounds via Better Round Elimination. Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf. APPROX-RANDOM 2010, 476-489. Web SearchBibTeXDownload
31An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. Amit Chakrabarti, Oded Regev. CoRR (abs/1009.3460) (2010). Web SearchBibTeXDownload
30Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor. CoRR (abs/1004.3304) (2010). Web SearchBibTeXDownload
29A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. Amit Chakrabarti. Electronic Colloquium on Computational Complexity (ECCC) (17): 100 (2010). Web SearchBibTeXDownload
28An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. Amit Chakrabarti, Oded Regev. SIAM J. Comput. (39): 1919-1940 (2010). Web SearchBibTeXDownload
2009
27Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. Paul Beame, Amit Chakrabarti. Computational Complexity (18): 169-170 (2009). Web SearchBibTeXDownload
26A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. Joshua Brody, Amit Chakrabarti. CoRR (abs/0902.2399) (2009). Web SearchBibTeXDownload
25Better Gap-Hamming Lower Bounds via Better Round Elimination. Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf. CoRR (abs/0912.5276) (2009). Web SearchBibTeXDownload
24Functional Monitoring without Monotonicity. Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti. ICALP (1) 2009, 95-106. Web SearchBibTeXDownload
23Annotations in Data Streams. Amit Chakrabarti, Graham Cormode, Andrew McGregor. ICALP (1) 2009, 222-234. Web SearchBibTeXDownload
2008
22Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent. FOCS 2008, 761-770. Web SearchBibTeXDownload
21Tight lower bounds for selection in randomly ordered streams. Amit Chakrabarti, T. S. Jayram, Mihai Patrascu. SODA 2008, 720-729. Web SearchBibTeXDownload
20Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. Joshua Brody, Amit Chakrabarti. STACS (abs/0802.2843): 145-156 (2008). Web SearchBibTeXDownload
19Robust lower bounds for communication and stream computation. Amit Chakrabarti, Graham Cormode, Andrew McGregor. STOC 2008, 641-650. Cited by 16Web SearchBibTeXDownload
2007
18Approximation Algorithms for the Unsplittable Flow Problem. Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar. Algorithmica (47): 53-78 (2007). Web SearchBibTeXDownload
17Lower Bounds for Multi-Player Pointer Jumping. Amit Chakrabarti. IEEE Conference on Computational Complexity 2007, 33-45. Web SearchBibTeXDownload
16Nearly Private Information Retrieval. Amit Chakrabarti, Anna Shubina. MFCS 2007, 383-393. Web SearchBibTeXDownload
15Improved lower bounds on the randomized complexity of graph properties. Amit Chakrabarti, Subhash Khot. Random Struct. Algorithms (30): 427-440 (2007). Cited by 14Web SearchBibTeXDownload
14A near-optimal algorithm for computing the entropy of a stream. Amit Chakrabarti, Graham Cormode, Andrew McGregor. SODA 2007, 328-335. Cited by 40Web SearchBibTeXDownload
2006
13Attack detection in time series for recommender systems. Sheng Zhang, Amit Chakrabarti, James Ford, Fillia Makedon. KDD 2006, 809-814. Web SearchBibTeXDownload
12Estimating Entropy and Entropy Norm on Data Streams. Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan. STACS 2006, 196-205. Cited by 21Web SearchBibTeXDownload
11A quasi-PTAS for unsplittable flow on line graphs. Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber. STOC 2006, 721-729. Web SearchBibTeXDownload
2004
10R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology. Yuhang Wang, Fillia Makedon, Amit Chakrabarti. ACM Multimedia 2004, 356-359. Web SearchBibTeXDownload
9An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. Amit Chakrabarti, Oded Regev. FOCS 2004, 473-482. Web SearchBibTeXDownload
2003
8An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. Amit Chakrabarti, Oded Regev. Electronic Colloquium on Computational Complexity (ECCC) 2003. Web SearchBibTeXDownload
7Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. Amit Chakrabarti, Subhash Khot, Xiaodong Sun. IEEE Conference on Computational Complexity 2003, 107-117. Cited by 72Web SearchBibTeXDownload
2002
6Approximation Algorithms for the Unsplittable Flow Problem. Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar. APPROX 2002, 51-66. Web SearchBibTeXDownload
5Improved Approximation Algorithms for Resource Allocation. Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani. IPCO 2002, 401-414. Web SearchBibTeXDownload
2001
4Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao. FOCS 2001, 270-278. Web SearchBibTeXDownload
3Improved Lower Bounds on the Randomized Complexity of Graph Properties. Amit Chakrabarti, Subhash Khot. ICALP 2001, 285-296. Web SearchBibTeXDownload
2Evasiveness of Subgraph Containment and Related Properties. Amit Chakrabarti, Subhash Khot, Yaoyun Shi. STACS (31): 866-875 (2001). Cited by 11Web SearchBibTeXDownload
1999
1A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov. STOC 1999, 305-311. Web SearchBibTeXDownload
from DBLP and Google Scholar
References
1. ^ Amit Chakrabarti's Homepage - Retrieved 2010-09-12 - details
2. ^ Amit Chakrabarti's Homepage - Retrieved 2010-06-15 - details
3. ^ Data Streams, Dyck Languages, and Detecting Dubious Data Structures - Retrieved 2011-02-03 - details
Developed by the Database Group at the University of Wisconsin and Yahoo! Research