default search action
Amit Chakrabarti
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2023
- [j21]Harshvardhan Gazula
, Kelly Rootes-Murdy, Bharath Holla, Sunitha Basodi, Zuo Zhang
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): 287-301 (2023) - 2021
- [j20]Harshvardhan Gazula, Bharath Holla
Decentralized Multisite VBM Analysis During Adolescence Shows Structural Changes Linked to Age, Body Mass Index, and Smoking: a COINSTAC Analysis. Neuroinformatics 19(4): 553-566 (2021) - 2019
- [j19]Amit Chakrabarti
Verifiable Stream Computation and Arthur-Merlin Communication. SIAM J. Comput. 48(4): 1265-1299 (2019) - 2016
- [j18]Joshua Brody, Amit Chakrabarti
Certifying Equality With Limited Interaction. Algorithmica 76(3): 796-845 (2016) - [j17]Amit Chakrabarti, Graham Cormode
Robust Lower Bounds for Communication and Stream Computation. Theory Comput. 12(1): 1-35 (2016) - 2015
- [j16]Weifu Wang, Devin J. Balkcom, Amit Chakrabarti
A fast online spanner for roadmap construction. Int. J. Robotics Res. 34(11): 1418-1432 (2015) - [j15]Amit Chakrabarti
Submodular maximization meets streaming: matchings, matroids, and more. Math. Program. 154(1-2): 225-247 (2015) - 2014
- [j14]Amit Chakrabarti
Annotations in Data Streams. ACM Trans. Algorithms 11(1): 7:1-7:30 (2014) - 2013
- [j13]Amit Chakrabarti
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. SIAM J. Comput. 42(1): 61-83 (2013) - 2012
- [j12]Amit Chakrabarti
A note on randomized streaming space bounds for the longest increasing subsequence problem. Inf. Process. Lett. 112(7): 261-263 (2012) - [j11]Amit Chakrabarti
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM J. Comput. 41(5): 1299-1317 (2012) - 2011
- [j10]Amit Chakrabarti
The query complexity of estimating weighted averages. Acta Informatica 48(7-8): 417-426 (2011) - [j9]Amit Chakrabarti
Combinatorial theorems about embedding trees on the real line. J. Graph Theory 67(2): 153-168 (2011) - [j8]Gruia Calinescu
An improved approximation algorithm for resource allocation. ACM Trans. Algorithms 7(4): 48:1-48:7 (2011) - 2010
- [j7]Amit Chakrabarti, Oded Regev:
An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. SIAM J. Comput. 39(5): 1919-1940 (2010) - [j6]Amit Chakrabarti
A near-optimal algorithm for estimating the entropy of a stream. ACM Trans. Algorithms 6(3): 51:1-51:21 (2010) - 2009
- [j5]Paul Beame
Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. Comput. Complex. 18(2): 169-170 (2009) - 2007
- [j4]Amit Chakrabarti
Approximation Algorithms for the Unsplittable Flow Problem. Algorithmica 47(1): 53-78 (2007) - [j3]Amit Chakrabarti
Improved lower bounds on the randomized complexity of graph properties. Random Struct. Algorithms 30(3): 427-440 (2007) - 2006
- [j2]Amit Chakrabarti
Estimating Entropy and Entropy Norm on Data Streams. Internet Math. 3(1): 63-78 (2006) - 2001
- [j1]Amit Chakrabarti
Evasiveness of Subgraph Containment and Related Properties. SIAM J. Comput. 31(3): 866-875 (2001)
Conference and Workshop Papers
- 2024
- [c48]Amit Chakrabarti, Manuel Stoeckl:
Finding Missing Items Requires Strong Forms of Randomness. CCC 2024: 28:1-28:20 - [c47]Amit Chakrabarti, Andrew McGregor, Anthony Wirth:
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams. ESA 2024: 40:1-40:15 - 2023
- [c46]Sepehr Assadi
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms. PODS 2023: 141-153 - 2022
- [c45]Amit Chakrabarti, Themistoklis K. Haris:
Counting Simplices in Hypergraph Streams. ESA 2022: 32:1-32:19 - [c44]Amit Chakrabarti, Prantar Ghosh
Adversarially Robust Coloring for Graph Streams. ITCS 2022: 37:1-37:23 - 2020
- [c43]Amit Chakrabarti
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. APPROX-RANDOM 2020: 22:1-22:23 - [c42]Suman K. Bera, Amit Chakrabarti
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. ICALP 2020: 11:1-11:21 - [c41]Amit Chakrabarti, Prantar Ghosh
Vertex Ordering Problems in Directed Graph Streams. SODA 2020: 1786-1802 - 2019
- [c40]Amit Chakrabarti
Streaming Verification of Graph Computations via Graph Structure. APPROX-RANDOM 2019: 70:1-70:20 - 2017
- [c39]Suman K. Bera, Amit Chakrabarti:
Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. STACS 2017: 11:1-11:14 - 2016
- [c38]Amit Chakrabarti, Sagar Kale
Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics. FOCS 2016: 41-50 - [c37]Amit Chakrabarti, Anthony Wirth:
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. SODA 2016: 1365-1373 - 2015
- [c36]Suman K. Bera, Amit Chakrabarti
A Depth-Five Lower Bound for Iterated Matrix Multiplication. CCC 2015: 183-197 - [c35]Amit Chakrabarti
Verifiable Stream Computation and Arthur-Merlin Communication. CCC 2015: 217-243 - [c34]Arijit Bishnu, Amit Chakrabarti
On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model. FSTTCS 2015: 336-349 - 2014
- [c33]Joshua Brody, Amit Chakrabarti
Certifying Equality With Limited Interaction. APPROX-RANDOM 2014: 545-581 - [c32]Amit Chakrabarti
Submodular Maximization Meets Streaming: Matchings, Matroids, and More. IPCO 2014: 210-221 - [c31]Joshua Brody, Amit Chakrabarti
Beyond set disjointness: the communication complexity of finding the intersection. PODC 2014: 106-113 - [c30]Amit Chakrabarti, Graham Cormode
Annotations for Sparse Data Streams. SODA 2014: 687-706 - 2013
- [c29]Weifu Wang, Devin J. Balkcom, Amit Chakrabarti
A fast streaming spanner algorithm for incrementally constructing sparse roadmaps. IROS 2013: 1257-1263 - 2012
- [c28]Amit Chakrabarti
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. APPROX-RANDOM 2012: 483-494 - [c27]Amit Chakrabarti
When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks. STOC 2012: 19-26 - 2011
- [c26]Amit Chakrabarti
Everywhere-Tight Information Cost Tradeoffs for Augmented Index. APPROX-RANDOM 2011: 448-459 - [c25]Amit Chakrabarti
An optimal lower bound on the communication complexity of gap-hamming-distance. STOC 2011: 51-60 - 2010
- [c24]Joshua Brody, Amit Chakrabarti
Better Gap-Hamming Lower Bounds via Better Round Elimination. APPROX-RANDOM 2010: 476-489 - [c23]Amit Chakrabarti
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. FOCS 2010: 387-396 - 2009
- [c22]Joshua Brody, Amit Chakrabarti
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. CCC 2009: 358-368 - [c21]Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti
Functional Monitoring without Monotonicity. ICALP (1) 2009: 95-106 - [c20]Amit Chakrabarti
Annotations in Data Streams. ICALP (1) 2009: 222-234 - 2008
- [c19]Amit Chakrabarti
Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. FOCS 2008: 761-770 - [c18]Amit Chakrabarti, T. S. Jayram, Mihai Patrascu:
Tight lower bounds for selection in randomly ordered streams. SODA 2008: 720-729 - [c17]Joshua Brody, Amit Chakrabarti:
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. STACS 2008: 145-156 - [c16]Amit Chakrabarti, Graham Cormode
Robust lower bounds for communication and stream computation. STOC 2008: 641-650 - 2007
- [c15]Amit Chakrabarti
Lower Bounds for Multi-Player Pointer Jumping. CCC 2007: 33-45 - [c14]Amit Chakrabarti, Anna Shubina:
Nearly Private Information Retrieval. MFCS 2007: 383-393 - [c13]Amit Chakrabarti, Graham Cormode, Andrew McGregor:
A near-optimal algorithm for computing the entropy of a stream. SODA 2007: 328-335 - 2006
- [c12]Sheng Zhang, Amit Chakrabarti, James Ford, Fillia Makedon:
Attack detection in time series for recommender systems. KDD 2006: 809-814 - [c11]Amit Chakrabarti
Estimating Entropy and Entropy Norm on Data Streams. STACS 2006: 196-205 - [c10]Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber:
A quasi-PTAS for unsplittable flow on line graphs. STOC 2006: 721-729 - 2004
- [c9]Amit Chakrabarti, Oded Regev:
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. FOCS 2004: 473-482 - [c8]Yuhang Wang, Fillia Makedon, Amit Chakrabarti:
R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology. ACM Multimedia 2004: 356-359 - 2003
- [c7]Amit Chakrabarti, Subhash Khot, Xiaodong Sun:
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. CCC 2003: 107-117 - 2002
- [c6]Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar
Approximation Algorithms for the Unsplittable Flow Problem. APPROX 2002: 51-66 - [c5]Gruia Calinescu
Improved Approximation Algorithms for Resource Allocation. IPCO 2002: 401-414 - 2001
- [c4]Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao:
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. FOCS 2001: 270-278 - [c3]Amit Chakrabarti, Subhash Khot:
Improved Lower Bounds on the Randomized Complexity of Graph Properties. ICALP 2001: 285-296 - [c2]Amit Chakrabarti, Subhash Khot, Yaoyun Shi:
Evasiveness of Subgraph Containment and Related Properties. STACS 2001: 110-120 - 1999
- [c1]Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov:
A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. STOC 1999: 305-311
Editorship
- 2022
- [e1]Amit Chakrabarti
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference). LIPIcs 245, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-249-5 [contents]
Reference Works
- 2016
- [r1]Amit Chakrabarti:
Communication Complexity. Encyclopedia of Algorithms 2016: 349-357
Informal and Other Publications
- 2024
- [i35]Amit Chakrabarti, Andrew McGregor, Anthony Wirth:
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams. CoRR abs/2403.14087 (2024) - 2023
- [i34]Amit Chakrabarti, Manuel Stoeckl:
When a random tape is not enough: lower bounds for a problem in adversarially robust streaming. CoRR abs/2310.03634 (2023) - 2022
- [i33]Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl:
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms. CoRR abs/2212.10641 (2022) - 2021
- [i32]Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova:
Vertex Ordering Problems in Directed Graph Streams. CoRR abs/2105.08215 (2021) - [i31]Amit Chakrabarti, Manuel Stoeckl:
The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries. CoRR abs/2107.05810 (2021) - [i30]Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl:
Adversarially Robust Coloring for Graph Streams. CoRR abs/2109.11130 (2021) - [i29]Amit Chakrabarti, Themistoklis K. Haris:
Counting Simplices in Hypergraph Streams. CoRR abs/2112.11016 (2021) - 2020
- [i28]Amit Chakrabarti, Prantar Ghosh, Justin Thaler:
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. CoRR abs/2007.03039 (2020) - [i27]Amit Chakrabarti, Prantar Ghosh, Justin Thaler:
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i26]Suman K. Bera, Amit Chakrabarti, Prantar Ghosh:
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. CoRR abs/1905.00566 (2019) - [i25]Amit Chakrabarti, Prantar Ghosh:
Streaming Verification of Graph Computations via Graph Structure. Electron. Colloquium Comput. Complex. TR19 (2019) - 2017
- [i24]Amit Chakrabarti, Yining Chen:
Time-Space Tradeoffs for the Memory Game. CoRR abs/1712.01330 (2017) - 2016
- [i23]Amit Chakrabarti, Sagar Kale:
Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i22]Amit Chakrabarti, Anthony Wirth:
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. CoRR abs/1507.04645 (2015) - [i21]Amit Chakrabarti, Anthony Wirth:
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i20]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
Verifiable Stream Computation and Arthur-Merlin Communication. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i19]Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler:
Annotations for Sparse Data Streams. CoRR abs/1304.3816 (2013) - [i18]Amit Chakrabarti, Sagar Kale:
Submodular Maximization Meets Streaming: Matchings, Matroids, and More. CoRR abs/1309.2038 (2013) - [i17]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
On Interactivity in Arthur-Merlin Communication and Stream Computation. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i16]Amit Chakrabarti, Lisa Fleischer, Christophe Weibel:
When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks. CoRR abs/1203.4041 (2012) - [i15]Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang:
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming. CoRR abs/1205.0968 (2012) - [i14]Joshua Brody, Amit Chakrabarti, Ranganath Kondapally:
Certifying Equality With Limited Interaction. Electron. Colloquium Comput. Complex. TR12 (2012) - [i13]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler:
Annotations in Data Streams. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i12]Amit Chakrabarti, Graham Cormode, Andrew McGregor:
Robust Lower Bounds for Communication and Stream Computation. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i11]Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor:
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. CoRR abs/1004.3304 (2010) - [i10]Amit Chakrabarti, Oded Regev:
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. CoRR abs/1009.3460 (2010) - [i9]Amit Chakrabarti:
A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem. Electron. Colloquium Comput. Complex. TR10 (2010) - [i8]Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor:
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. Electron. Colloquium Comput. Complex. TR10 (2010) - [i7]Amit Chakrabarti, Oded Regev:
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i6]Joshua Brody, Amit Chakrabarti:
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. CoRR abs/0902.2399 (2009) - [i5]Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf:
Better Gap-Hamming Lower Bounds via Better Round Elimination. CoRR abs/0912.5276 (2009) - [i4]Joshua Brody, Amit Chakrabarti:
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i3]Joshua Brody, Amit Chakrabarti:
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. CoRR abs/0802.2843 (2008) - 2007
- [i2]Amit Chakrabarti:
Lower Bounds for Multi-Player Pointer Jumping. Electron. Colloquium Comput. Complex. TR07 (2007) - 2003
- [i1]Amit Chakrabarti, Oded Regev:
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. Electron. Colloquium Comput. Complex. TR03 (2003)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 21:23 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: