2 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.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-…