16 citations · 33 across the 13 of their papers we have counts for
13 papers
Finding Subcube Heavy Hitters in Analytics Data Streams
Branislav Kveton, S. Muthukrishnan, Hoa T. Vu +1
Data streams typically have items of large number of dimensions. We study the fundamental heavy-hitters problem in this setting. Formally, the data stream consists of -dimension…
The Shapley Value in Knapsack Budgeted Games
Smriti Bhagat, Anthony Kim, S. Muthukrishnan +1
We propose the study of computing the Shapley value for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a versi…
Nearly Optimal Private Convolution
Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov
We study computing the convolution of a private input with a public input , while satisfying the guarantees of -differential privacy. Convolution is a fundamental op…
Analyses of Cardinal Auctions
Mangesh Gupte, Darja Krushevskaja, S. Muthukrishnan
We study cardinal auctions for selling multiple copies of a good, in which bidders specify not only their bid or how much they are ready to pay for the good, but also a cardinality…
Optimal Private Halfspace Counting via Discrepancy
S. Muthukrishnan, Aleksandar Nikolov
A range counting problem is specified by a set of size of points in , an integer weight associated to each point , and a range space ${\c…
Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection
Gianni Franceschini, Roberto Grossi, S. Muthukrishnan
Consider an input text string T[1,N] drawn from an unbounded alphabet. We study partial computation in suffix-based problems for Data Compression and Text Indexing such as (I) retr…