# Amit Chakrabarti

According to our database

^{1}, Amit Chakrabarti## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2017

Time-Space Tradeoffs for the Memory Game.

CoRR, 2017

Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams.

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016

Communication Complexity.

Encyclopedia of Algorithms, 2016

Robust Lower Bounds for Communication and Stream Computation.

Theory of Computing, 2016

Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Certifying Equality With Limited Interaction.

Algorithmica, 2016

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover.

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics.

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Submodular maximization meets streaming: matchings, matroids, and more.

Math. Program., 2015

A fast online spanner for roadmap construction.

I. J. Robotics Res., 2015

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover.

CoRR, 2015

On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model.

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Verifiable Stream Computation and Arthur-Merlin Communication.

Proceedings of the 30th Conference on Computational Complexity, 2015

A Depth-Five Lower Bound for Iterated Matrix Multiplication.

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Annotations in Data Streams.

ACM Trans. Algorithms, 2014

Verifiable Stream Computation and Arthur-Merlin Communication.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Annotations for Sparse Data Streams.

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Beyond set disjointness: the communication complexity of finding the intersection.

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Submodular Maximization Meets Streaming: Matchings, Matroids, and More.

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Certifying Equality With Limited Interaction.

Proceedings of the Approximation, 2014

2013

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.

SIAM J. Comput., 2013

On Interactivity in Arthur-Merlin Communication and Stream Computation.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Annotations for Sparse Data Streams

CoRR, 2013

Submodular Maximization Meets Streaming: Matchings, Matroids, and More.

CoRR, 2013

A fast streaming spanner algorithm for incrementally constructing sparse roadmaps.

Proceedings of the 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013

2012

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance.

SIAM J. Comput., 2012

A note on randomized streaming space bounds for the longest increasing subsequence problem.

Inf. Process. Lett., 2012

Annotations in Data Streams.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Certifying Equality With Limited Interaction.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming

CoRR, 2012

When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks

CoRR, 2012

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks.

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

An improved approximation algorithm for resource allocation.

ACM Trans. Algorithms, 2011

Combinatorial theorems about embedding trees on the real line.

Journal of Graph Theory, 2011

Robust Lower Bounds for Communication and Stream Computation.

Electronic Colloquium on Computational Complexity (ECCC), 2011

The query complexity of estimating weighted averages.

Acta Inf., 2011

An optimal lower bound on the communication complexity of gap-hamming-distance.

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Everywhere-Tight Information Cost Tradeoffs for Augmented Index.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

A near-optimal algorithm for estimating the entropy of a stream.

ACM Trans. Algorithms, 2010

An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching.

SIAM J. Comput., 2010

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.

Electronic Colloquium on Computational Complexity (ECCC), 2010

A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem.

Electronic Colloquium on Computational Complexity (ECCC), 2010

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

CoRR, 2010

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

CoRR, 2010

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.

Proceedings of the Approximation, 2010

2009

A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences.

Electronic Colloquium on Computational Complexity (ECCC), 2009

Better Gap-Hamming Lower Bounds via Better Round Elimination

CoRR, 2009

A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

CoRR, 2009

Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword.

Computational Complexity, 2009

Annotations in Data Streams.

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Functional Monitoring without Monotonicity.

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences.

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound

CoRR, 2008

Robust lower bounds for communication and stream computation.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound.

Proceedings of the STACS 2008, 2008

Tight lower bounds for selection in randomly ordered streams.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Improved lower bounds on the randomized complexity of graph properties.

Random Struct. Algorithms, 2007

Lower Bounds for Multi-Player Pointer Jumping.

Electronic Colloquium on Computational Complexity (ECCC), 2007

Approximation Algorithms for the Unsplittable Flow Problem.

Algorithmica, 2007

A near-optimal algorithm for computing the entropy of a stream.

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Nearly Private Information Retrieval.

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Lower Bounds for Multi-Player Pointer Jumping.

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Estimating Entropy and Entropy Norm on Data Streams.

Internet Mathematics, 2006

A quasi-PTAS for unsplittable flow on line graphs.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Estimating Entropy and Entropy Norm on Data Streams.

Proceedings of the STACS 2006, 2006

Attack detection in time series for recommender systems.

Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006

2004

R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology.

Proceedings of the 12th ACM International Conference on Multimedia, 2004

An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching.

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

Electronic Colloquium on Computational Complexity (ECCC), 2003

Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness.

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Improved Approximation Algorithms for Resource Allocation.

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

Approximation Algorithms for the Unsplittable Flow Problem.

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001

Evasiveness of Subgraph Containment and Related Properties.

SIAM J. Comput., 2001

Evasiveness of Subgraph Containment and Related Properties.

Proceedings of the STACS 2001, 2001

Improved Lower Bounds on the Randomized Complexity of Graph Properties.

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

1999

A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube.

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999