3 papers
cs.DS2024
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
Amit Chakrabarti, Andrew McGregor, Anthony Wirth
The maximum coverage problem is to select sets from a collection of sets such that the cardinality of the union of the selected sets is maximized. We consider -appro…
cs.DS2023
Finding missing items requires strong forms of randomness
Amit Chakrabarti, Manuel Stoeckl
Adversarially robust streaming algorithms are required to process a stream of elements and produce correct outputs, even when each stream element can be chosen as a function of ear…
cs.CC2010
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally +1
This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-…