Skip to main content

6 Result(s)

within S. Muthukrishnan Remove this filter Computer Communication Networks Remove this filter Numeric Computing Remove this filter

and

  1. No Access

    Chapter and Conference Paper

    Nearly Optimal Private Convolution

    We study algorithms for computing the convolution of a private input x with a public input h, while satisfying the guarantees of (ε, δ)-differential privacy. Convolution is a fundamental operation, intimately rel...

    Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov in Algorithms – ESA 2013 (2013)

  2. No Access

    Chapter

    Frugal Streaming for Estimating Quantiles

    Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. In many such applications, in fact, one needs to compute such statist...

    Qiang Ma, S. Muthukrishnan, Mark Sandler in Space-Efficient Data Structures, Streams, … (2013)

  3. No Access

    Chapter and Conference Paper

    Range Medians

    We study a generalization of the classical median finding problem to batched query case: given an array of unsorted n items and k (not necessarily disjoint) intervals in the array, the goal is to determine the me...

    Sariel Har-Peled, S. Muthukrishnan in Algorithms - ESA 2008 (2008)

  4. No Access

    Chapter and Conference Paper

    Radix Sorting with No Extra Space

    It is well known that n integers in the range [1,n c ] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,

    Gianni Franceschini, S. Muthukrishnan, Mihai Pǎtraşcu in Algorithms – ESA 2007 (2007)

  5. No Access

    Chapter and Conference Paper

    Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods

    Much recent work in the theoretical computer science, linear algebra, and machine learning has considered matrix decompositions of the following form: given an m ×n matrix A, decompose it as a product of three ma...

    Petros Drineas, Michael W. Mahoney, S. Muthukrishnan in Algorithms – ESA 2006 (2006)

  6. No Access

    Chapter and Conference Paper

    Workload-Optimal Histograms on Streams

    A histogram is a piecewise-constant approximation of an observed data distribution. A histogram is used as a small-space, approximate synopsis of the underlying data distribution, which is often too large to b...

    S. Muthukrishnan, M. Strauss, X. Zheng in Algorithms – ESA 2005 (2005)