| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Amit Chakrabarti |
A note on randomized streaming space bounds for the longest increasing subsequence problem.  |
Inf. Process. Lett.  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler |
Annotations in Data Streams. |
Electronic Colloquium on Computational Complexity (ECCC) |
2012 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Lisa Fleischer, Christophe Weibel |
When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks |
CoRR |
2012 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor |
Robust Lower Bounds for Communication and Stream Computation. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth |
The query complexity of estimating weighted averages. |
Acta Inf. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani |
An improved approximation algorithm for resource allocation. |
ACM Transactions on Algorithms |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Subhash Khot |
Combinatorial theorems about embedding trees on the real line. |
Journal of Graph Theory |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Ranganath Kondapally |
Everywhere-Tight Information Cost Tradeoffs for Augmented Index. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Oded Regev |
An optimal lower bound on the communication complexity of gap-hamming-distance. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti |
A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor |
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Oded Regev |
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor |
A near-optimal algorithm for estimating the entropy of a stream. |
ACM Transactions on Algorithms |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor |
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Oded Regev |
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Oded Regev |
An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. |
SIAM J. Comput. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf |
Better Gap-Hamming Lower Bounds via Better Round Elimination. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor |
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. |
FOCS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti |
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Paul Beame, Amit Chakrabarti |
Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf |
Better Gap-Hamming Lower Bounds via Better Round Elimination |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti |
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor |
Annotations in Data Streams. |
ICALP |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti |
Functional Monitoring without Monotonicity. |
ICALP |
2009 |
DBLP DOI BibTeX RDF |
sensor networks, distributed algorithms, data streams, Communication complexity |
| 1 | Joshua Brody, Amit Chakrabarti |
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti |
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, T. S. Jayram, Mihai Patrascu |
Tight lower bounds for selection in randomly ordered streams. |
SODA |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti |
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. |
STACS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent |
Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor |
Robust lower bounds for communication and stream computation. |
STOC |
2008 |
DBLP DOI BibTeX RDF |
lower bounds, data streams, communication complexity |
| 1 | Amit Chakrabarti |
Lower Bounds for Multi-Player Pointer Jumping. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar |
Approximation Algorithms for the Unsplittable Flow Problem. |
Algorithmica |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Subhash Khot |
Improved lower bounds on the randomized complexity of graph properties. |
Random Struct. Algorithms |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Graham Cormode, Andrew McGregor |
A near-optimal algorithm for computing the entropy of a stream. |
SODA |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Anna Shubina |
Nearly Private Information Retrieval. |
MFCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti |
Lower Bounds for Multi-Player Pointer Jumping. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan |
Estimating Entropy and Entropy Norm on Data Streams. |
Internet Mathematics |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan |
Estimating Entropy and Entropy Norm on Data Streams. |
STACS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber |
A quasi-PTAS for unsplittable flow on line graphs. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
scheduling, approximation algorithms, resource allocation, approximation scheme, unsplittable flow |
| 1 | Sheng Zhang, Amit Chakrabarti, James Ford, Fillia Makedon |
Attack detection in time series for recommender systems. |
KDD |
2006 |
DBLP DOI BibTeX RDF |
shilling attacks, recommender systems, anomaly detection, time series |
| 1 | Amit Chakrabarti, Oded Regev |
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. |
FOCS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuhang Wang, Fillia Makedon, Amit Chakrabarti |
R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology. |
ACM Multimedia |
2004 |
DBLP DOI BibTeX RDF |
R*-Histogram, image retrieval, similarity search, efficient algorithms, spatial relations |
| 1 | Amit Chakrabarti, Oded Regev |
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani |
Improved Approximation Algorithms for Resource Allocation. |
IPCO |
2002 |
DBLP BibTeX RDF |
|
| 1 | Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar |
Approximation Algorithms for the Unsplittable Flow Problem. |
APPROX |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Subhash Khot, Yaoyun Shi |
Evasiveness of Subgraph Containment and Related Properties. |
SIAM J. Comput. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Subhash Khot |
Improved Lower Bounds on the Randomized Complexity of Graph Properties. |
ICALP |
2001 |
DBLP DOI BibTeX RDF |
Decision tree complexity, monotone graph properties, randomized complexity, graph packing, randomized algorithms, probabilistic method |
| 1 | Amit Chakrabarti, Subhash Khot, Yaoyun Shi |
Evasiveness of Subgraph Containment and Related Properties. |
STACS |
2001 |
DBLP DOI BibTeX RDF |
Decision Tree Complexity, Monotone Graph Properties, Graph Property Testing, Evasiveness |
| 1 | Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao |
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 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 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")