Amit Chakrabarti

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 36

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

APPROX-RANDOM

SODA

Publications

Amit Chakrabarti, Manuel Stoeckl
Finding Missing Items Requires Strong Forms of Randomness. CCC (2024)
Amit Chakrabarti, Andrew McGregor, Anthony Wirth
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams. CoRR (2024)
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms. PODS (2023)
Amit Chakrabarti, Manuel Stoeckl
When a random tape is not enough: lower bounds for a problem in adversarially robust streaming. CoRR (2023)
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 Desrivieres, 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 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
Federated Analysis in COINSTAC Reveals Functional Network Connectivity and Spectral Links to Smoking and Alcohol Consumption in Nearly 2,000 Adolescent Brains. Neuroinformatics 21 (2) (2023)
Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
Adversarially Robust Coloring for Graph Streams. ITCS (2022)
Amit Chakrabarti, Themistoklis K. Haris
Counting Simplices in Hypergraph Streams. ESA (2022)
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms. CoRR (2022)
Amit Chakrabarti, Themistoklis K. Haris
Counting Simplices in Hypergraph Streams. CoRR (2021)
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, Lenin Singh, Rebecca Kuriyan, Pratima Murthy, Vivek Benega, Sergey M. Plis, Anand D. Sarwate, Jessica A. Turner, Gunter Schumann, Vince D. Calhoun
Decentralized Multisite VBM Analysis During Adolescence Shows Structural Changes Linked to Age, Body Mass Index, and Smoking: a COINSTAC Analysis. Neuroinformatics 19 (4) (2021)
Amit Chakrabarti, Manuel Stoeckl
The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries. CoRR (2021)
Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
Adversarially Robust Coloring for Graph Streams. CoRR (2021)
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
Vertex Ordering Problems in Directed Graph Streams. CoRR (2021)
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. CoRR (2020)
Suman K. Bera, Amit Chakrabarti, Prantar Ghosh
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. ICALP (2020)
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. Electron. Colloquium Comput. Complex. 27 (2020)
Amit Chakrabarti, Prantar Ghosh, Justin Thaler
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. APPROX-RANDOM (2020)
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
Vertex Ordering Problems in Directed Graph Streams. SODA (2020)
Suman K. Bera, Amit Chakrabarti, Prantar Ghosh
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. CoRR (2019)
Amit Chakrabarti, Prantar Ghosh
Streaming Verification of Graph Computations via Graph Structure. Electron. Colloquium Comput. Complex. 26 (2019)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
Verifiable Stream Computation and Arthur-Merlin Communication. SIAM J. Comput. 48 (4) (2019)
Amit Chakrabarti, Prantar Ghosh
Streaming Verification of Graph Computations via Graph Structure. APPROX-RANDOM (2019)
Amit Chakrabarti, Yining Chen
Time-Space Tradeoffs for the Memory Game. CoRR (2017)
Suman K. Bera, Amit Chakrabarti
Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. STACS (2017)
Amit Chakrabarti, Anthony Wirth
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. SODA (2016)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
Certifying Equality With Limited Interaction. Algorithmica 76 (3) (2016)
Amit Chakrabarti, Sagar Kale
Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics. FOCS (2016)
Amit Chakrabarti, Graham Cormode, Andrew McGregor
Robust Lower Bounds for Communication and Stream Computation. Theory Comput. 12 (1) (2016)
Amit Chakrabarti, Sagar Kale
Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics. Electron. Colloquium Comput. Complex. 23 (2016)
Amit Chakrabarti, Anthony Wirth
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. CoRR (2015)
Arijit Bishnu, Amit Chakrabarti, Subhas C. Nandy, Sandeep Sen
On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model. FSTTCS (2015)
Amit Chakrabarti, Sagar Kale
Submodular maximization meets streaming: matchings, matroids, and more. Math. Program. 154 (1-2) (2015)
Amit Chakrabarti, Anthony Wirth
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. Electron. Colloquium Comput. Complex. 22 (2015)
Suman K. Bera, Amit Chakrabarti
A Depth-Five Lower Bound for Iterated Matrix Multiplication. Computational Complexity Conference (2015)
Weifu Wang, Devin J. Balkcom, Amit Chakrabarti
A fast online spanner for roadmap construction. Int. J. Robotics Res. 34 (11) (2015)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
Verifiable Stream Computation and Arthur-Merlin Communication. Computational Complexity Conference (2015)
Amit Chakrabarti, Sagar Kale
Submodular Maximization Meets Streaming: Matchings, Matroids, and More. IPCO (2014)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
Beyond set disjointness: the communication complexity of finding the intersection. PODC (2014)
Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler
Annotations for Sparse Data Streams. SODA (2014)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler
Annotations in Data Streams. ACM Trans. Algorithms 11 (1) (2014)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
Verifiable Stream Computation and Arthur-Merlin Communication. Electron. Colloquium Comput. Complex. 21 (2014)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev
Certifying Equality With Limited Interaction. APPROX-RANDOM (2014)
Amit Chakrabarti, Sagar Kale
Submodular Maximization Meets Streaming: Matchings, Matroids, and More. CoRR (2013)
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. SIAM J. Comput. 42 (1) (2013)
Weifu Wang, Devin J. Balkcom, Amit Chakrabarti
A fast streaming spanner algorithm for incrementally constructing sparse roadmaps. IROS (2013)
Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler
Annotations for Sparse Data Streams CoRR (2013)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
On Interactivity in Arthur-Merlin Communication and Stream Computation. Electron. Colloquium Comput. Complex. 20 (2013)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally
Certifying Equality With Limited Interaction. Electron. Colloquium Comput. Complex. 19 (2012)
Amit Chakrabarti, Lisa Fleischer, Christophe Weibel
When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks CoRR (2012)
Amit Chakrabarti, Lisa Fleischer, Christophe Weibel
When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks. STOC (2012)
Amit Chakrabarti
A note on randomized streaming space bounds for the longest increasing subsequence problem. Inf. Process. Lett. 112 (7) (2012)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler
Annotations in Data Streams. Electron. Colloquium Comput. Complex. 19 (2012)
Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. APPROX-RANDOM (2012)
Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming CoRR (2012)
Amit Chakrabarti, Oded Regev
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM J. Comput. 41 (5) (2012)
Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth
The query complexity of estimating weighted averages. Acta Informatica 48 (7-8) (2011)
Amit Chakrabarti, Subhash Khot
Combinatorial theorems about embedding trees on the real line. J. Graph Theory 67 (2) (2011)
Amit Chakrabarti, Ranganath Kondapally
Everywhere-Tight Information Cost Tradeoffs for Augmented Index. APPROX-RANDOM (2011)
Amit Chakrabarti, Oded Regev
An optimal lower bound on the communication complexity of gap-hamming-distance. STOC (2011)
Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani
An improved approximation algorithm for resource allocation. ACM Trans. Algorithms 7 (4) (2011)
Amit Chakrabarti, Graham Cormode, Andrew McGregor
Robust Lower Bounds for Communication and Stream Computation. Electron. Colloquium Comput. Complex. 18 (2011)
Amit Chakrabarti
A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. Electron. Colloquium Comput. Complex. 17 (2010)
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition CoRR (2010)
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. FOCS (2010)
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. Electron. Colloquium Comput. Complex. 17 (2010)
Amit Chakrabarti, Oded Regev
An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. SIAM J. Comput. 39 (5) (2010)
Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
Better Gap-Hamming Lower Bounds via Better Round Elimination. APPROX-RANDOM (2010)
Amit Chakrabarti, Oded Regev
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. Electron. Colloquium Comput. Complex. 17 (2010)
Amit Chakrabarti, Oded Regev
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance CoRR (2010)
Amit Chakrabarti, Graham Cormode, Andrew McGregor
A near-optimal algorithm for estimating the entropy of a stream. ACM Trans. Algorithms 6 (3) (2010)
Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
Better Gap-Hamming Lower Bounds via Better Round Elimination CoRR (2009)
Joshua Brody, Amit Chakrabarti
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. Computational Complexity Conference (2009)
Amit Chakrabarti, Graham Cormode, Andrew McGregor
Annotations in Data Streams. ICALP (1) (2009)
Paul Beame, Amit Chakrabarti
Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. Comput. Complex. 18 (2) (2009)
Joshua Brody, Amit Chakrabarti
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences CoRR (2009)
Joshua Brody, Amit Chakrabarti
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. Electron. Colloquium Comput. Complex. 16 (2009)
Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti
Functional Monitoring without Monotonicity. ICALP (1) (2009)
Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent
Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. FOCS (2008)
Amit Chakrabarti, T. S. Jayram, Mihai Patrascu
Tight lower bounds for selection in randomly ordered streams. SODA (2008)
Joshua Brody, Amit Chakrabarti
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. STACS (2008)
Joshua Brody, Amit Chakrabarti
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound CoRR (2008)
Amit Chakrabarti, Graham Cormode, Andrew McGregor
Robust lower bounds for communication and stream computation. STOC (2008)
Amit Chakrabarti, Graham Cormode, Andrew McGregor
A near-optimal algorithm for computing the entropy of a stream. SODA (2007)
Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar
Approximation Algorithms for the Unsplittable Flow Problem. Algorithmica 47 (1) (2007)
Amit Chakrabarti, Anna Shubina
Nearly Private Information Retrieval. MFCS (2007)
Amit Chakrabarti, Subhash Khot
Improved lower bounds on the randomized complexity of graph properties. Random Struct. Algorithms 30 (3) (2007)
Amit Chakrabarti
Lower Bounds for Multi-Player Pointer Jumping. Computational Complexity Conference (2007)
Amit Chakrabarti
Lower Bounds for Multi-Player Pointer Jumping. Electron. Colloquium Comput. Complex. 14 (014) (2007)
Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber
A quasi-PTAS for unsplittable flow on line graphs. STOC (2006)
Sheng Zhang, Amit Chakrabarti, James Ford, Fillia Makedon
Attack detection in time series for recommender systems. KDD (2006)
Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan
Estimating Entropy and Entropy Norm on Data Streams. STACS (2006)
Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan
Estimating Entropy and Entropy Norm on Data Streams. Internet Math. 3 (1) (2006)
Amit Chakrabarti, Oded Regev
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. FOCS (2004)
Yuhang Wang, Fillia Makedon, Amit Chakrabarti
R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology. ACM Multimedia (2004)
Amit Chakrabarti, Oded Regev
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching Electron. Colloquium Comput. Complex. (070) (2003)
Amit Chakrabarti, Subhash Khot, Xiaodong Sun
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. Computational Complexity Conference (2003)
Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani
Improved Approximation Algorithms for Resource Allocation. IPCO (2002)
Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar
Approximation Algorithms for the Unsplittable Flow Problem. APPROX (2002)
Amit Chakrabarti, Subhash Khot
Improved Lower Bounds on the Randomized Complexity of Graph Properties. ICALP (2001)
Amit Chakrabarti, Subhash Khot, Yaoyun Shi
Evasiveness of Subgraph Containment and Related Properties. SIAM J. Comput. 31 (3) (2001)

Amit Chakrabarti.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Amit Chakrabarti