(Universidad de Chile & Universitat Pompeu Fabra), Algorithmic Challenges in Web Search Engine.|
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.
Anne Condon ,
(RNA molecules: glimpses through an algorithmic lens), U. British Columbia.
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
(Universitat Politècnica de Catalunya), Squares.
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
(Matching Based Augmentations for Approximating Connectivity Problems), Carnegie Mellon University.
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.
(Modelling Errors and Recovery for Communication), MIT.
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.
(Lossless Data Compression via Error Correction), Princeton.
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
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.
(The power and weakness of randomness in computation), IAS.
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.