Amit Chakrabarti

Orcid: 0000-0003-3633-9180

According to our database1, Amit Chakrabarti authored at least 63 papers between 1999 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

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

Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms.
Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

2022
Adversarially Robust Coloring for Graph Streams.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Counting Simplices in Hypergraph Streams.
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

Vertex Ordering Problems in Directed Graph Streams.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019
Streaming Verification of Graph Computations via Graph Structure.
Electron. Colloquium Comput. Complex., 2019

2017
Time-Space Tradeoffs for the Memory Game.
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
Communication Complexity.
Encyclopedia of Algorithms, 2016

Robust Lower Bounds for Communication and Stream Computation.
Theory Comput., 2016

Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics.
Electron. Colloquium Comput. Complex., 2016

Certifying Equality With Limited Interaction.
Algorithmica, 2016

2015
Submodular maximization meets streaming: matchings, matroids, and more.
Math. Program., 2015

A fast online spanner for roadmap construction.
Int. J. Robotics Res., 2015

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover.
Electron. Colloquium Comput. Complex., 2015

On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model.
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.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
Annotations in Data Streams.
ACM Trans. Algorithms, 2014

Verifiable Stream Computation and Arthur-Merlin Communication.
Electron. Colloquium Comput. Complex., 2014

Annotations for Sparse Data Streams.
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
On Interactivity in Arthur-Merlin Communication and Stream Computation.
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
A note on randomized streaming space bounds for the longest increasing subsequence problem.
Inf. Process. Lett., 2012

Certifying Equality With Limited Interaction.
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
An improved approximation algorithm for resource allocation.
ACM Trans. Algorithms, 2011

Combinatorial theorems about embedding trees on the real line.
J. Graph Theory, 2011

The query complexity of estimating weighted averages.
Acta Informatica, 2011

Everywhere-Tight Information Cost Tradeoffs for Augmented Index.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
A near-optimal algorithm for estimating the entropy of a stream.
ACM Trans. Algorithms, 2010

An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching.
SIAM J. Comput., 2010

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance.
Electron. Colloquium Comput. Complex., 2010

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.
Electron. Colloquium Comput. Complex., 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.
Proceedings of the Approximation, 2010

2009
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences.
Electron. Colloquium Comput. Complex., 2009

Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword.
Comput. Complex., 2009

Annotations in Data Streams.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Functional Monitoring without Monotonicity.
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

Tight lower bounds for selection in randomly ordered streams.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Improved lower bounds on the randomized complexity of graph properties.
Random Struct. Algorithms, 2007

Lower Bounds for Multi-Player Pointer Jumping.
Electron. Colloquium Comput. Complex., 2007

Approximation Algorithms for the Unsplittable Flow Problem.
Algorithmica, 2007

A near-optimal algorithm for computing the entropy of a stream.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Nearly Private Information Retrieval.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

2006
Estimating Entropy and Entropy Norm on Data Streams.
Internet Math., 2006

A quasi-PTAS for unsplittable flow on line graphs.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Attack detection in time series for recommender systems.
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
Improved Approximation Algorithms for Resource Allocation.
Proceedings of the Integer Programming and Combinatorial Optimization, 2002

2001
Evasiveness of Subgraph Containment and Related Properties.
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


  Loading...