Gagan Aggarwal, Krishnaram Kenthapadi, Rina Panigrahy, An Zhu, Google Inc
or classroom use provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and...
Sponsored Search Auctions with Markovian Users (2009)
Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, Martin Pál
Abstract. Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. The most popular auction for sponsored...
Efficiency of (Revenue-)Optimal Mechanisms (2009)
Aggarwal, Gagan, Goel, Gagan, Mehta, Aranyak
We compare the expected efficiency of revenue maximizing (or {\em optimal}) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for...
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...
General Auction Mechanism for Search Advertising (2008)
Aggarwal, Gagan, Muthukrishnan, S., Pal, David, Pal, Martin
In sponsored search, a number of advertising slots is available on a search results page, and have to be allocated among a set of advertisers competing to display an ad on the page. This gives rise...
Sponsored Search Auctions with Markovian Users (2008)
Aggarwal, Gagan, Feldman, Jon, Muthukrishnan, S., Pal, Martin
Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. Currently, the most popular auction for sponsored...
Anonymizing Tables for Privacy Protection (2008)
Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, ...
We consider the problem of releasing tables containing personal records while ensuring individual privacy and data integrity. One of the techniques proposed in the literature is k-anonymization. A...
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...
Abstract Truthful Auctions for Pricing Search Keywords (2008)
Gagan Aggarwal, Ashish Goel, Rajeev Motwani
We present a truthful auction for pricing advertising slots on a web-page assuming that advertisements for different merchants must be ranked in decreasing order of their (weighted) bids. This...
Bidding to the Top: VCG and Equilibria of (2008)
Position-based Auctions, Gagan Aggarwal, Jon Feldman, S. Muthukrishnan
Abstract. Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount...
The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. The most important quality of a realistic...
Algorithms for the Database Layout Problem (2008)
Gagan Aggarwal, Tomás Feder, Rajeev Motwani, Rina Panigrahy, An Zhu
Abstract. We present a formal analysis of the database layout problem, i.e., the problem of determining how database objects such as tables and indexes are assigned to disk drives. Optimizing this...
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...
The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. The most important quality of a realistic...
Extending the Streaming Model: Sorting and Streaming Networks (2008)
Matthias Ruhl, Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan
The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. One such model is “streaming computations...
Extending the Streaming Model: Sorting and Streaming Networks (2008)
Matthias Ruhl, Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan
The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. One such model is “streaming computations...
Bidding to the Top: VCG and Equilibria of Position-Based Auctions (2006)
Aggarwal, Gagan, Muthukrishnan, S., Feldman, Jon
Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their...
Achieving Anonymity via Clustering (2006)
Gagan Aggarwal, Samir Khuller, Tomás Feder
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying...
Gagan Aggarwal, Google Inc, Ashish Goel, Rajeev Motwani
We present a truthful auction for pricing advertising slots on a web-page assuming that advertisements for different merchants must be ranked in decreasing order of their (weighted) bids. This...
Achieving Anonymity via Clustering (2006)
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying...
Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is...
Achieving Anonymity via Clustering (2006)
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Rina Panigrahy, Dilys Thomas, An Zhu
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying...
Privacy protection and advertising in a networked world / (2005)
Aggarwal, Gagan., Motwani, Rajeev Advisor
Submitted to the Department of Computer Science.
Journal of Privacy Technology 20051120001 Approximation Algorithms for k-Anonymity ∗ (2005)
Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, ...
We consider the problem of releasing a table containing personal records, while ensuring individual privacy and maintaining data integrity to the extent possible. One of the techniques proposed in...
Secure computation of the k th -ranked element (2004)
Gagan Aggarwal, Nina Mishra, Benny Pinkas
Abstract. Given two or more parties possessing large, confidential datasets, we consider the problem of securely computing the k th-ranked element of the union of the datasets, e.g. the median of the...
Secure computation of the k th -ranked element (2004)
Gagan Aggarwal, Nina Mishra, Benny Pinkas
Given two or more parties possessing large, confidential datasets, we consider the problem of securely computing the k th-ranked element of the union of the datasets, e.g. the median of the values in...
On identifying stable ways to configure systems (2004)
Gagan Aggarwal, Mayur Datarý, Nina Mishraþ, Rajeev Motwaniü
We consider the often error-prone process of initially building and/or reconfiguring a computer system. We formulate a new optimization framework for capturing certain aspects of this system...
Complexities for generalized models of self-assembly (2004)
Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-yang Kao, Pablo Moisset, De Espanes, ...
Abstract. In this paper, we study the complexity of self-assembly under models that are natural generalizations of the tile self-assembly model. In particular, we extend Rothemund and Winfree’s...
Algorithms for multi-product pricing (2004)
Gagan Aggarwal, Tomás Feder, Rajeev Motwani, An Zhu
Abstract. In the information age, the availability of data on consumer profiles has opened new possibilities for companies to increase their revenue via data mining techniques. One approach has been...
Vision Paper: Enabling Privacy for the Paranoids (2004)
Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-molina, Krishnaram Kenthapadi, Nina Mishra, ...
P3P [27, 32] is a set of standards that allow corporations to declare their privacy policies. Hippocratic Databases [4] have been proposed to implement such policies within a corporation’s...
Algorithms for multi-product pricing (2004)
Gagan Aggarwal, Tomás Feder, Rajeev Motwani, An Zhu
Abstract. In the information age, the availability of data on consumer profiles has opened new possibilities for companies to increase their revenue via data mining techniques. One approach has been...
Complexities for generalized models of self-assembly (2004)
Gagan Aggarwal, Michael H. Goldwasser, Ming-yang Kao, Robert T. Schweller
In this paper, we extend Rothemund and Winfree’s examination of the tile complexity of tile self-assembly [6]. log N They provided a lower bound of Ω ( log log N) on the tile complexity of...
Secure computation of the k th -ranked element (2004)
Gagan Aggarwal, Nina Mishra, Benny Pinkas
Abstract. Given two or more parties possessing large, confidential datasets, we consider the problem of securely computing the k th-ranked element of the union of the datasets, e.g. the median of the...
The Load Rebalancing Problem (2003)
Gagan Aggarwal, Rajeev Motwani, An Zhu
In the classical load balancing or multiprocessor scheduling problem, we are given a sequence of jobs of varying sizes and are asked to assign each job to one of the m empty processors. A typical...
The load rebalancing problem (2003)
Gagan Aggarwal, Rajeev Motwani
In the classical load balancing or multiprocessor scheduling problem, we are given a sequence of jobs of varying sizes and are asked to assign each job to one of the m empty processors. A typical...
The load rebalancing problem (2003)
Gagan Aggarwal, Rajeev Motwani
In the classical load balancing or multiprocessor scheduling problem, we are given a sequence of jobs of varying sizes and are asked to assign each job to one of the m empty processors. A typical...
Switch scheduling via randomized edge coloring (2003)
Gagan Aggarwal, Rajeev Motwani, Devavrat Shah, An Zhu
The essence of an Internet router is an n ¡ n switch which routes packets from input to output ports. Such a switch can be viewed as a bipartite graph with the input and output ports as the two...