Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Amit Chakrabarti
2010 – today
- 2013
[j13]Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor: Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. SIAM J. Comput. 42(1): 61-83 (2013)- [i17]Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler: Annotations for Sparse Data Streams. CoRR abs/1304.3816 (2013)
- 2012
- [j12]Amit Chakrabarti: A note on randomized streaming space bounds for the longest increasing subsequence problem. Inf. Process. Lett. 112(7): 261-263 (2012)
- [j11]Amit Chakrabarti, Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM J. Comput. 41(5): 1299-1317 (2012)
- [c28]Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang: Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. APPROX-RANDOM 2012: 483-494
- [c27]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
- [i16]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)
- [i15]Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang: Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. CoRR abs/1205.0968 (2012)
- [i14]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler: Annotations in Data Streams. Electronic Colloquium on Computational Complexity (ECCC) 19: 22 (2012)
- [i13]Joshua Brody, Amit Chakrabarti, Ranganath Kondapally: Certifying Equality With Limited Interaction. Electronic Colloquium on Computational Complexity (ECCC) 19: 153 (2012)
- 2011
- [j10]Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth: The query complexity of estimating weighted averages. Acta Inf. 48(7-8): 417-426 (2011)
- [j9]Amit Chakrabarti, Subhash Khot: Combinatorial theorems about embedding trees on the real line. Journal of Graph Theory 67(2): 153-168 (2011)
- [j8]Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani: An improved approximation algorithm for resource allocation. ACM Transactions on Algorithms 7(4): 48 (2011)
- [c26]Amit Chakrabarti, Ranganath Kondapally: Everywhere-Tight Information Cost Tradeoffs for Augmented Index. APPROX-RANDOM 2011: 448-459
- [c25]Amit Chakrabarti, Oded Regev: An optimal lower bound on the communication complexity of gap-hamming-distance. STOC 2011: 51-60
- [i12]Amit Chakrabarti, Graham Cormode, Andrew McGregor: Robust Lower Bounds for Communication and Stream Computation. Electronic Colloquium on Computational Complexity (ECCC) 18: 62 (2011)
- 2010
- [j7]Amit Chakrabarti, Oded Regev: An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. SIAM J. Comput. 39(5): 1919-1940 (2010)
- [j6]Amit Chakrabarti, Graham Cormode, Andrew McGregor: A near-optimal algorithm for estimating the entropy of a stream. ACM Transactions on Algorithms 6(3) (2010)
- [c24]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
- [c23]Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor: Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. FOCS 2010: 387-396
- [i11]Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor: Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. CoRR abs/1004.3304 (2010)
- [i10]Amit Chakrabarti, Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. CoRR abs/1009.3460 (2010)
- [i9]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)
- [i8]Amit Chakrabarti: A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. Electronic Colloquium on Computational Complexity (ECCC) 17: 100 (2010)
- [i7]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)
2000 – 2009
- 2009
- [j5]Paul Beame, Amit Chakrabarti: Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. Computational Complexity 18(2): 169-170 (2009)
- [c22]Joshua Brody, Amit Chakrabarti: A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. IEEE Conference on Computational Complexity 2009: 358-368
- [c21]Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti: Functional Monitoring without Monotonicity. ICALP (1) 2009: 95-106
- [c20]Amit Chakrabarti, Graham Cormode, Andrew McGregor: Annotations in Data Streams. ICALP (1) 2009: 222-234
- [i6]Joshua Brody, Amit Chakrabarti: A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. CoRR abs/0902.2399 (2009)
- [i5]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)
- [i4]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
- [c19]Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent: Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. FOCS 2008: 761-770
- [c18]Amit Chakrabarti, T. S. Jayram, Mihai Patrascu: Tight lower bounds for selection in randomly ordered streams. SODA 2008: 720-729
- [c17]Joshua Brody, Amit Chakrabarti: Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. STACS 2008: 145-156
- [c16]Amit Chakrabarti, Graham Cormode, Andrew McGregor: Robust lower bounds for communication and stream computation. STOC 2008: 641-650
- [i3]Joshua Brody, Amit Chakrabarti: Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. CoRR abs/0802.2843 (2008)
- 2007
- [j4]Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar: Approximation Algorithms for the Unsplittable Flow Problem. Algorithmica 47(1): 53-78 (2007)
- [j3]Amit Chakrabarti, Subhash Khot: Improved lower bounds on the randomized complexity of graph properties. Random Struct. Algorithms 30(3): 427-440 (2007)
- [c15]Amit Chakrabarti: Lower Bounds for Multi-Player Pointer Jumping. IEEE Conference on Computational Complexity 2007: 33-45
- [c14]
- [c13]Amit Chakrabarti, Graham Cormode, Andrew McGregor: A near-optimal algorithm for computing the entropy of a stream. SODA 2007: 328-335
- [i2]Amit Chakrabarti: Lower Bounds for Multi-Player Pointer Jumping. Electronic Colloquium on Computational Complexity (ECCC) 14(014) (2007)
- 2006
- [j2]Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan: Estimating Entropy and Entropy Norm on Data Streams. Internet Mathematics 3(1): 63-78 (2006)
- [c12]Sheng Zhang, Amit Chakrabarti, James Ford, Fillia Makedon: Attack detection in time series for recommender systems. KDD 2006: 809-814
- [c11]Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan: Estimating Entropy and Entropy Norm on Data Streams. STACS 2006: 196-205
- [c10]Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber: A quasi-PTAS for unsplittable flow on line graphs. STOC 2006: 721-729
- 2004
- [c9]Amit Chakrabarti, Oded Regev: An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. FOCS 2004: 473-482
- [c8]Yuhang Wang, Fillia Makedon, Amit Chakrabarti: R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology. ACM Multimedia 2004: 356-359
- 2003
- [c7]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
- [i1]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
- [c6]Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar: Approximation Algorithms for the Unsplittable Flow Problem. APPROX 2002: 51-66
- [c5]Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani: Improved Approximation Algorithms for Resource Allocation. IPCO 2002: 401-414
- 2001
- [j1]Amit Chakrabarti, Subhash Khot, Yaoyun Shi: Evasiveness of Subgraph Containment and Related Properties. SIAM J. Comput. 31(3): 866-875 (2001)
- [c4]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
- [c3]Amit Chakrabarti, Subhash Khot: Improved Lower Bounds on the Randomized Complexity of Graph Properties. ICALP 2001: 285-296
- [c2]Amit Chakrabarti, Subhash Khot, Yaoyun Shi: Evasiveness of Subgraph Containment and Related Properties. STACS 2001: 110-120
1990 – 1999
- 1999
- [c1]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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-05-03 21:39 CEST by the dblp team