16 Result(s)
within
S. Muthukrishnan
Computer Science
Computation by Abstract Devices
-
Chapter and Conference Paper
Budget Feasible Mechanisms for Experimental Design
We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant (≈ 12.98) factor approximation for the Experimental Design Problem (EDP). By app...
-
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...
-
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...
-
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...
-
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...
-
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...
-
Chapter and Conference Paper
Stochastic Data Streams
The classical data stream problems are now greatly understood [1]. This talk will focus on problems with stochastic (rather than deterministic) streams where the underlying physical phenomenon generates probab...
-
Chapter and Conference Paper
Estimating Entropy and Entropy Norm on Data Streams
We consider the problem of computing information theoretic functions such as entropy on a data stream, using sublinear space.
-
Chapter and Conference Paper
Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses
Given a signal A of N dimensions, the problem is to obtain a representation R for it that is a linear combination of vectors in the dictionary H of Haar wavelets. The quality of the representation R is determined...
-
Chapter and Conference Paper
Sublinear Methods for Detecting Periodic Trends in Data Streams
We present sublinear algorithms — algorithms that use significantly less resources than needed to store or process the entire input stream – for discovering representative trends in data streams in the form of...
-
Chapter and Conference Paper
An Improved Data Stream Summary: The Count-Min Sketch and Its Applications
We introduce a new sublinear space data structure—the Count-Min Sketch— for summarizing data streams. Our sketch allows fundamental queries in data stream summarization such as point, range, and inner product que...
-
Chapter and Conference Paper
Maintenance of Multidimensional Histograms
We present a space- and time- efficient algorithm for maintaining multidimensional histograms for data that is dynamic, i.e., subject to updates that may be increments or decrements. Both space used as well as...
-
Chapter and Conference Paper
Comparing Sequences with Segment Rearrangements
Computational genomics involves comparing sequences based on “similarity” for detecting evolutionary and functional relationships. Until very recently, available portions of the human genome sequence (and that...
-
Chapter and Conference Paper
On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity and Applications
Partitioning a multi-dimensional data set into rectangular partitions subject to certain constraints is an important problem that arises in many database applications, including histogram-based selectivity est...
-
Chapter and Conference Paper
Optimal parallel algorithms for Prefix Matching
The Prefix Matching Problem is to determine, for each location in the text t, the longest prefix of a given pattern p which occurs beginning at that location. We present two work-optimal parallel algorithms for t...
-
Chapter and Conference Paper
String matching under a general matching relation
In standard string matching, each symbol matches only itself. In other string matching problems, e.g., the string matching with “don't-cares” problem, a symbol may match several symbols. In general, an arbitra...
