In this paper we present the main algorithmic challenges that large Web search engines face today. These challenges are present in all the modules of a Web retrieval system, ranging from the gathering of the data to be indexed (crawling) to the selection and ordering of the answers to a query (searching and ranking). Most of the challenges are ultimately related to the quality of the answer or the efficiency in obtaining it, although some are relevant even to the existence of search engines: context based advertising.

Dubbed the “architects of eukaryotic complexity”, RNA molecules are increasingly in the spotlight, in recognition of the important catalytic and regulatory roles they play in our cells and their promise in therapeutics. Our goal is to describe the ways in which algorithms can help shape our understanding of RNA structure and function.

In this talk we present several results and open problems having squares, the basic geometric entity, as a common thread. These results have been gathered from various papers; coauthors and precise references are given in the descriptions that follow.

We describe a very simple idea for designing approximation algorithms for connectivity problems: For a spanning tree problem, the idea is to start with the empty set of edges, and add matching paths between pairs of components in the current graph that have desirable properties in terms of the objective function of the spanning tree problem being solved. Such matching augment the solution by reducing the number of connected components to roughly half their original number, resulting in a logarithmic number of such matching iterations. A logarithmic performance ratio results for the problem by appropriately bounding the contribution of each matching to the objective function by that of an optimal solution.

In this survey, we trace the initial application of these ideas to traveling salesperson problems through a simple tree pairing observation down to more sophisticated applications for buy-at-bulk type network design problems.

The theory of error-correction has had two divergent schools of thought, going back to the works of Shannon and Hamming. In the Shannon school, error is presumed to have been effected probabilistically. In the Hamming school, the error is modeled as effected by an all-powerful adversary. The two schools lead to drastically different limits. In the Shannon model, a binary channel with error-rate close to, but less than, \(50\%\) is useable for effective communication. In the Hamming model, a binary channel with an error-rate of more than \(25\%\) prohibits unique recovery of the message.

In this talk, we describe the notion of list-decoding, as a bridge between the Hamming and Shannon models. This model relaxes the notion of recovery to allow for a “list of candidates”. We describe results in this model, and then show how these results can be applied to get unique recovery under “computational restrictions” on the channel's ability, a model initiated by R. Lipton in 1994.

Based on joint works with Venkatesan Guruswami (U. Washington), and with Silvio Micali (MIT), Chris Peikert (MIT) and David Wilson (MIT).

This plenary talk gives an overview of recent joint work with G. Caire and S. Shamai on the use of linear error correcting codes for lossless data compression, joint source/channel coding and interactive data exchange.

Humanity has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. We describe two main aspects of this research on randomness, demonstrating its power and weakness respectively.

Situated at the confluence of two navigable rivers, Valdivia is one of the south's most charismatic cities. Nearby Spanish forts at Corral and Niebla are reminders of the city's importance during the colonial era, when it was one of few fortified cities maintained by the Spanish in Mapuche Indian territory; subtle German architecture dates from the late 19th-century influx of European immigrants. The Rio Cruces Nature Sanctuary, a protected wetlands north of the city, is home to a variety of aquatic birds and is a favorite destination for boat trips.

^*  Authors with n affiliations contributes 1/n to each affiliation.
^** Papers with n authors contribute 1/n to each affiliation.

^*  Authors with n affiliations contributes 1/n to each affiliation.
^** Papers with n authors contribute 1/n to each affiliation.

Africa

Australia & Asia

Europe

Latin-America

Middle East

USA & Canada