# Amit Chakrabarti

According to our database

Collaborative distances:

^{1}, Amit Chakrabarti authored at least 56 papers between 1999 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2020

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches.

Electronic Colloquium on Computational Complexity (ECCC), 2020

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Electronic Colloquium on Computational Complexity (ECCC), 2019

2017

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

Encyclopedia of Algorithms, 2016

Theory Comput., 2016

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

Electronic Colloquium on Computational Complexity (ECCC), 2016

Algorithmica, 2016

2015

Math. Program., 2015

I. J. Robotics Res., 2015

Electronic Colloquium on Computational Complexity (ECCC), 2015

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

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

ACM Trans. Algorithms, 2014

Electronic Colloquium on Computational Complexity (ECCC), 2014

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

2013

Electronic Colloquium on Computational Complexity (ECCC), 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

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

Inf. Process. Lett., 2012

Electronic Colloquium on Computational Complexity (ECCC), 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

ACM Trans. Algorithms, 2011

Journal of Graph Theory, 2011

Acta Informatica, 2011

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

2010

ACM Trans. Algorithms, 2010

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

SIAM J. Comput., 2010

Electronic Colloquium on Computational Complexity (ECCC), 2010

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Proceedings of the Approximation, 2010

2009

Electronic Colloquium on Computational Complexity (ECCC), 2009

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

Comput. Complex., 2009

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

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

2008

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

Proceedings of the STACS 2008, 2008

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

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

2007

Random Struct. Algorithms, 2007

Electronic Colloquium on Computational Complexity (ECCC), 2007

Algorithmica, 2007

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

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006

Internet Math., 2006

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

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

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

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

2001

SIAM J. Comput., 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