7 citations · 14 across the 11 of their papers we have counts for
9 papers · 1 filter
The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries
Amit Chakrabarti, Manuel Stoeckl
Two widely-used computational paradigms for sublinear algorithms are using linear measurements to perform computations on a high dimensional input and using structured queries to a…
Time-Space Tradeoffs for the Memory Game
Amit Chakrabarti, Yining Chen
A single-player game of Memory is played with distinct pairs of cards, with the cards in each pair bearing identical pictures. The cards are laid face-down. A move consists of…
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover
Amit Chakrabarti, Anthony Wirth
Set cover, over a universe of size , may be modelled as a data-streaming problem, where the sets that comprise the instance are to be read one by one. A semi-streaming algor…
Annotations for Sparse Data Streams
Amit Chakrabarti, Graham Cormode, Navin Goyal +1
Motivated by cloud computing, a number of recent works have studied annotated data streams and variants thereof. In this setting, a computationally weak verifier (cloud user), lack…
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
Amit Chakrabarti, Ranganath Kondapally, Zhenghui Wang
Three decades of research in communication complexity have led to the invention of a number of techniques to lower bound randomized communication complexity. The majority of these…
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
Amit Chakrabarti, Oded Regev
We prove an optimal lower bound on the randomized communication complexity of the much-studied Gap-Hamming-Distance problem. As a consequence, we obtain essentially optimal…
Better Gap-Hamming Lower Bounds via Better Round Elimination
Joshua Brody, Amit Chakrabarti, Oded Regev +2
Gap Hamming Distance is a well-studied problem in communication complexity, in which Alice and Bob have to decide whether the Hamming distance between their respective n-bit inputs…
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences
Joshua Brody, Amit Chakrabarti
The Gap-Hamming-Distance problem arose in the context of proving space lower bounds for a number of key problems in the data stream model. In this problem, Alice and Bob have to de…
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound
Joshua Brody, Amit Chakrabarti
We study the one-way number-on-the-forehead (NOF) communication complexity of the -layer pointer jumping problem with vertices per layer. This classic problem, which has con…