| The phenomenal growth of networking infrastructure over the past couple of decades has led to the emergence of the Internet as the ubiquitous channel for information sharing and dissemination. This has created a whole new set of research challenges, while giving a new spin to some existing ones. In this thesis, we address problems from two areas: (a) protection of data privacy, and (b) sale of advertisement space on Internet web sites.; The first part of the thesis deals with privacy issues involved in the exchange of information between non-trusting entities. We first consider the problem of anonymizing databases before dissemination, in order to safeguard the privacy of the individuals described by the databases. For the privacy framework of k-Anonymity, we present approximation algorithms that anonymize databases while maximizing the utility of the anonymized database. Then, we study the problem of enabling two or more parties to securely and efficiently compute the kth-ranked element of a set split between them, without revealing any information not implied by the value of the output. We present protocols with polylogarithmic overhead for this purpose, improving upon the linear overhead of earlier solutions.; In the second part of the thesis, we consider the problem of selling advertisement space on the Internet. We observe that the use of a truthful selling mechanism would considerably simplify the task of bidding, potentially attracting more advertisers to the online advertising market. We first consider the problem of selling a single advertisement slot on a web page over the course of a day. We present a truthful auction that is competitive with respect to an optimal omniscient pricing scheme that obeys a natural monotonicity property. The second problem we study is that of selling multiple advertisement slots on a web page. This problem is more closely aligned with the problem faced by search engines. We present an auction that is truthful when the advertisers are not budget-constrained. Moreover, under some reasonable assumptions, we show that its revenue is equivalent to the non-truthful auctions currently being used by search engines. |
