Skip to main content

19 Result(s)

within S. Muthukrishnan Remove this filter Computer Science Remove this filter Computer Communication Networks 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

    Scienceography: The Study of How Science Is Written

    Scientific literature has itself been the subject of much scientific study, for a variety of reasons: understanding how results are communicated, how ideas spread, and assessing the influence of areas or indiv...

    Graham Cormode, S. Muthukrishnan, **yun Yan in Fun with Algorithms (2012)

  4. No Access

    Chapter and Conference Paper

    Budget Optimization for Online Campaigns with Positive Carryover Effects

    While it is relatively easy to start an online advertising campaign, proper allocation of the marketing budget is far from trivial. A major challenge faced by the marketers attempting to optimize their campaig...

    Nikolay Archak, Vahab Mirrokni, S. Muthukrishnan in Internet and Network Economics (2012)

  5. No Access

    Chapter and Conference Paper

    Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions

    Zero Knowledge Proofs (ZKPs) are one of the most striking innovations in theoretical computer science. In practice, the prevalent ZKP methods are, at times, too complicated to be useful for real-life applicati...

    Michael O. Rabin, Yishay Mansour, S. Muthukrishnan… in Automata, Languages, and Programming (2012)

  6. No Access

    Chapter and Conference Paper

    Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization

    Inspired by Internet ad auction applications, we study the problem of allocating a single item via an auction when bidders place very different values on the item. We formulate this as the problem of prior-free a...

    Vahab Mirrokni, S. Muthukrishnan, Uri Nadav in LATIN 2010: Theoretical Informatics (2010)

  7. No Access

    Chapter and Conference Paper

    Approximation Schemes for Sequential Posted Pricing in Multi-unit Auctions

    We design algorithms for computing approximately revenue-maximizing sequential posted-pricing mechanisms (SPM) in K-unit auctions, in a standard Bayesian model. A seller has K copies of an item to sell, and there...

    Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha… in Internet and Network Economics (2010)

  8. No Access

    Chapter and Conference Paper

    Selective Call Out and Real Time Bidding

    Ads on the Internet are increasingly sold via ad exchanges such as RightMedia, AdECN and Doubleclick Ad Exchange. These exchanges allow real-time bidding, that is, each time the publisher contacts the exchange...

    Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha… in Internet and Network Economics (2010)

  9. No Access

    Chapter and Conference Paper

    Bidding on Configurations in Internet Ad Auctions

    In Internet advertising, a configuration of ads is determined by the seller, and advertisers buy spaces in the configuration. In this paper, motivated by sponsored search ads, we propose an auction where adver...

    S. Muthukrishnan in Computing and Combinatorics (2009)

  10. 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)

  11. No Access

    Chapter and Conference Paper

    Stochastic Models for Budget Optimization in Search-Based Advertising

    Internet search companies sell advertisement slots based on users’ search queries via an auction. Advertisers have to determine how to place bids on the keywords of their interest in order to maximize their re...

    S. Muthukrishnan, Martin Pál, Zoya Svitkina in Internet and Network Economics (2007)

  12. 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)

  13. 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)

  14. No Access

    Chapter and Conference Paper

    Combinatorial Algorithms for Compressed Sensing

    In sparse approximation theory, the fundamental problem is to reconstruct a signal A ∈ ℝ n from linear measurements 〈A ψ i

    Graham Cormode, S. Muthukrishnan in Structural Information and Communication Complexity (2006)

  15. Chapter and Conference Paper

    Streams, Security and Scalability

    Network-based attacks, such as DDoS attacks and worms, are threatening the continued utility of the Internet. As the variety and the sophistication of attacks grow, early detection of potential attacks will be...

    Theodore Johnson, S. Muthukrishnan, Oliver Spatscheck… in Data and Applications Security XIX (2005)

    Download PDF (214 KB)

  16. 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)

  17. No Access

    Chapter and Conference Paper

    Permutation Editing and Matching via Embeddings

    If the genetic maps of two species are modelled as permutations of (homologous) genes, the number of chromosomal rearrangements in the form of deletions, block moves, inversions etc. to transform one such perm...

    Graham Cormode, S. Muthukrishnan… in Automata, Languages and Programming (2001)

  18. No Access

    Chapter and Conference Paper

    Augmenting Suffix Trees, with Applications

    Information retrieval and data compression are the two main application areas where the rich theory of string algorithmics plays a fundamental role. In this paper, we consider one algorithmic problem from each...

    Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp, Jacob Ziv in Algorithms — ESA’ 98 (1998)

  19. No Access

    Chapter and Conference Paper

    Efficient array partitioning

    We consider the problem of partitioning an array of n items into p intervals so that the maximum weight of the intervals is minimized. The currently best known bound for this problem is O(n+p 1+ε ) [HNC92] for an...

    Sanjeev Khanna, S. Muthukrishnan, Steven Skiena in Automata, Languages and Programming (1997)