Amit Chakrabarti

107 papers A* 22A 15B 3Journal 56Unranked 10

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