Amit Chakrabarti

According to our database, Amit Chakrabarti authored at least 65 papers between 1999 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams.

Amit Chakrabarti, Andrew McGregor, Anthony Wirth

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Finding Missing Items Requires Strong Forms of Randomness.

Amit Chakrabarti, Manuel Stoeckl

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.

Harshvardhan Gazula, Kelly Rootes-Murdy, Bharath Holla, Sunitha Basodi, Zuo Zhang, Eric Verner, Ross Kelly, Pratima Murthy, Amit Chakrabarti, Debasish Basu, Subodh Bhagyalakshmi Nanjayya, Rajkumar Lenin Singh, Roshan Lourembam Singh, Kartik Kalyanram, Kamakshi Kartik, Kalyanaraman Kumaran, Krishnaveni Ghattu, Rebecca Kuriyan, Sunita Simon Kurpad, Gareth J. Barker, Rose Dawn Bharath, Sylvane Desrivières, Meera Purushottam, Dimitri Papadopoulos-Orfanos, Eesha Sharma, Matthew Hickman, Mireille Toledano, Nilakshi Vaidya, Tobias Banaschewski, Arun L. W. Bokde, Herta Flor, Antoine Grigis, Hugh Garavan, Penny A. Gowland, Andreas Heinz, Rüdiger Brühl, Jean-Luc Martinot, Marie-Laure Paillère-Martinot, Eric Artiges, Frauke Nees, Tomás Paus, Luise Poustka, Juliane H. Fröhner, Lauren Robinson, Michael N. Smolka, Henrik Walter, Jeanne Winterer, Robert Whelan, Jessica A. Turner, Anand D. Sarwate, Sergey M. Plis, Vivek Benegal, Gunter Schumann, Vince D. Calhoun

Neuroinformatics, April, 2023

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

Amit Chakrabarti, Manuel Stoeckl

CoRR, 2023

Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms.

Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl

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

2022

Adversarially Robust Coloring for Graph Streams.

Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl

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

Counting Simplices in Hypergraph Streams.

Amit Chakrabarti, Themistoklis K. Haris

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.

Harshvardhan Gazula, Bharath Holla, Zuo Zhang, Jiayuan Xu, Eric Verner, Ross Kelly, Sanjeev Jain, Rose Dawn Bharath, Gareth J. Barker, Debasish Basu, Amit Chakrabarti, Kartik Kalyanram, Kalyanaraman Kumaran, Rajkumar Lenin Singh, Rebecca Kuriyan, Pratima Murthy, Vivek Benega, Sergey M. Plis, Anand D. Sarwate, Jessica A. Turner, Gunter Schumann, Vince D. Calhoun

Neuroinformatics, 2021

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

Amit Chakrabarti, Manuel Stoeckl

CoRR, 2021

2020

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

Amit Chakrabarti, Prantar Ghosh, Justin Thaler

Electron. Colloquium Comput. Complex., 2020

Vertex Ordering Problems in Directed Graph Streams.

Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova

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

Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models.

Suman K. Bera, Amit Chakrabarti, Prantar Ghosh

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

2019

Verifiable Stream Computation and Arthur-Merlin Communication.

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

SIAM J. Comput., 2019

Streaming Verification of Graph Computations via Graph Structure.

Amit Chakrabarti, Prantar Ghosh

Electron. Colloquium Comput. Complex., 2019

2017

Time-Space Tradeoffs for the Memory Game.

Amit Chakrabarti, Yining Chen

CoRR, 2017

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

Suman K. Bera, Amit Chakrabarti

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

2016

Communication Complexity.

Amit Chakrabarti

Encyclopedia of Algorithms, 2016

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

Amit Chakrabarti, Sagar Kale

Electron. Colloquium Comput. Complex., 2016

Certifying Equality With Limited Interaction.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Algorithmica, 2016

2015

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

Amit Chakrabarti, Sagar Kale

Math. Program., 2015

A fast online spanner for roadmap construction.

Weifu Wang, Devin J. Balkcom, Amit Chakrabarti

Int. J. Robotics Res., 2015

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

Amit Chakrabarti, Anthony Wirth

Electron. Colloquium Comput. Complex., 2015

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

Arijit Bishnu, Amit Chakrabarti, Subhas C. Nandy, Sandeep Sen

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

A Depth-Five Lower Bound for Iterated Matrix Multiplication.

Suman K. Bera, Amit Chakrabarti

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Annotations for Sparse Data Streams.

Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler

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

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

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

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

2013

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

SIAM J. Comput., 2013

On Interactivity in Arthur-Merlin Communication and Stream Computation.

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

Electron. Colloquium Comput. Complex., 2013

A fast streaming spanner algorithm for incrementally constructing sparse roadmaps.

Weifu Wang, Devin J. Balkcom, Amit Chakrabarti

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.

Amit Chakrabarti, Oded Regev

SIAM J. Comput., 2012

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

Amit Chakrabarti

Inf. Process. Lett., 2012

Annotations in Data Streams.

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler

Electron. Colloquium Comput. Complex., 2012

Certifying Equality With Limited Interaction.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

Electron. Colloquium Comput. Complex., 2012

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

Amit Chakrabarti, Lisa Fleischer, Christophe Weibel

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

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

Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang

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

2011

An improved approximation algorithm for resource allocation.

Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani

ACM Trans. Algorithms, 2011

Combinatorial theorems about embedding trees on the real line.

Amit Chakrabarti, Subhash Khot

J. Graph Theory, 2011

Robust Lower Bounds for Communication and Stream Computation.

Amit Chakrabarti, Graham Cormode, Andrew McGregor

Electron. Colloquium Comput. Complex., 2011

The query complexity of estimating weighted averages.

Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth

Acta Informatica, 2011

Everywhere-Tight Information Cost Tradeoffs for Augmented Index.

Amit Chakrabarti, Ranganath Kondapally

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

2010

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

Amit Chakrabarti, Graham Cormode, Andrew McGregor

ACM Trans. Algorithms, 2010

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

Amit Chakrabarti, Oded Regev

SIAM J. Comput., 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf

Proceedings of the Approximation, 2010

2009

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

Joshua Brody, Amit Chakrabarti

Electron. Colloquium Comput. Complex., 2009

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

Paul Beame, Amit Chakrabarti

Comput. Complex., 2009

Annotations in Data Streams.

Amit Chakrabarti, Graham Cormode, Andrew McGregor

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

Functional Monitoring without Monotonicity.

Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti

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.

Joshua Brody, Amit Chakrabarti

Proceedings of the STACS 2008, 2008

Tight lower bounds for selection in randomly ordered streams.

Amit Chakrabarti, T. S. Jayram, Mihai Patrascu

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

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

Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent

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

2007

Improved lower bounds on the randomized complexity of graph properties.

Amit Chakrabarti, Subhash Khot

Random Struct. Algorithms, 2007

Lower Bounds for Multi-Player Pointer Jumping.

Amit Chakrabarti

Electron. Colloquium Comput. Complex., 2007

Approximation Algorithms for the Unsplittable Flow Problem.

Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar

Algorithmica, 2007

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

Amit Chakrabarti, Graham Cormode, Andrew McGregor

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

Nearly Private Information Retrieval.

Amit Chakrabarti, Anna Shubina

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006

Estimating Entropy and Entropy Norm on Data Streams.

Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan

Internet Math., 2006

A quasi-PTAS for unsplittable flow on line graphs.

Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber

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

Attack detection in time series for recommender systems.

Sheng Zhang, Amit Chakrabarti, James Ford, Fillia Makedon

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.

Yuhang Wang, Fillia Makedon, Amit Chakrabarti

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

2003

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

Amit Chakrabarti, Oded Regev

Electron. Colloquium Comput. Complex., 2003

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

Amit Chakrabarti, Subhash Khot, Xiaodong Sun

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

2002

Improved Approximation Algorithms for Resource Allocation.

Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

2001

Evasiveness of Subgraph Containment and Related Properties.

Amit Chakrabarti, Subhash Khot, Yaoyun Shi

SIAM J. Comput., 2001

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

Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao

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.

Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov

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