# Amit Chakrabarti

Orcid: 0000-0003-3633-9180
According to our database

Collaborative distances:

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

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Dataset Other## Links

#### On csauthors.net:

## Bibliography

2024

CoRR, 2024

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Federated Analysis in COINSTAC Reveals Functional Network Connectivity and Spectral Links to Smoking and Alcohol Consumption in Nearly 2,000 Adolescent Brains.

Neuroinformatics, April, 2023

When a random tape is not enough: lower bounds for a problem in adversarially robust streaming.

CoRR, 2023

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

2022

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Decentralized Multisite VBM Analysis During Adolescence Shows Structural Changes Linked to Age, Body Mass Index, and Smoking: a COINSTAC Analysis.

Neuroinformatics, 2021

The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries.

CoRR, 2021

2020

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

Electron. Colloquium Comput. Complex., 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

SIAM J. Comput., 2019

Electron. Colloquium Comput. Complex., 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

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

Electron. Colloquium Comput. Complex., 2016

Algorithmica, 2016

2015

Math. Program., 2015

Int. J. Robotics Res., 2015

Electron. Colloquium Comput. Complex., 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

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

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.

SIAM J. Comput., 2013

Electron. Colloquium Comput. Complex., 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

SIAM J. Comput., 2012

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

Inf. Process. Lett., 2012

Electron. Colloquium Comput. Complex., 2012

Electron. Colloquium Comput. Complex., 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

J. Graph Theory, 2011

Electron. Colloquium Comput. Complex., 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

Proceedings of the Approximation, 2010

2009

Electron. Colloquium Comput. Complex., 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

Electron. Colloquium Comput. Complex., 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

Electron. Colloquium Comput. Complex., 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