Amit Chakrabarti

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

Coauthor Index

1	Chrisil Arackaparambil	[32]
2	Khanh Do Ba	[12] [14]
3	Nikhil Bansal	[13]
4	Paul Beame	[28]
5	Joshua Brody	[22] [24] [27] [29] [30] [31] [32] [42]
6	Gruia Calinescu	[6] [46]
7	Bernard Chazelle	[1]
8	Chandra Chekuri	[7] [18]
9	Graham Cormode	[19] [23] [33] [35] [39] [40] [41] [44] [50]
10	Amir Epstein	[13]
11	Lisa Fleischer	[51] [52]
12	James Ford	[15]
13	Benjamin Gum	[1]
14	Anupam Gupta	[7] [18]
15	Venkatesan Guruswami	[45]
16	Alexander Jaffe	[26]
17	T. S. Jayram (Jayram S. Thathachar)	[25]
18	Howard J. Karloff	[6] [46]
19	Subhash Khot	[2] [3] [4] [9] [16] [43]
20	Ranganath Kondapally	[35] [39] [41] [48]
21	Amit Kumar	[7] [18]
22	James R. Lee	[26]
23	Alexey Lvov	[1]
24	Fillia Makedon	[11] [15]
25	Andrew McGregor	[19] [23] [33] [35] [39] [40] [41] [44] [50]
26	S. Muthukrishnan (S. Muthu Muthukrishnan)	[12] [14]
27	Mihai Patrascu	[25]
28	Yuval Rabani	[6] [46]
29	Oded Regev	[8] [10] [29] [34] [36] [38] [42] [47]
30	Baruch Schieber	[13]
31	Yaoyun Shi	[2] [3] [5]
32	Anna Shubina	[20]
33	Xiaodong Sun	[9]
34	Justin Thaler	[50]
35	Thomas Vidick	[29] [42]
36	Justin Vincent	[26]
37	Yuhang Wang	[11]
38	Christophe Weibel	[51] [52]
39	Andrew Wirth	[45]
40	Anthony Wirth (Anthony Ian Wirth)	[5] [45]
41	Ronald de Wolf	[29] [42]
42	Andrew Chi-Chih Yao (Andrew C. Yao)	[5]
43	Sheng Zhang	[15]

Colors in the list of coauthors

Last update Sun May 27 04:04:01 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page