15th Asian School on Computer Science

Date : December 11-15, 2004
Venue : Chiang Mai, Thailand (Post- Asian Computing Science Conference 2004)
Organized and Supported By : Asian Institute of Technology (Thailand) and INRIA (France)

TOPIC : PROBABILISTIC ALGORITHMS with APPLICATIONS to MASSIVE DATA SETS

Probabilistic algorithms lie at the heart of many essential data processing tasks, where they often lead to spectacular gains. The goal of this course is to present a general framework for probabilistic algorithms. At the same time, we shall develop a few specific applications in the area (close to data-mining) of extracting quantitative information from large data sets. The course will cover the following areas:

1. Deterministic versus randomized algorithms: algorithms that "bet" on the likely shape of data versus algorithms that purposely resort to coin-flippings. Some introductory examples. Different classes of probabilistic algorithms: Monte-Carlo, Las Vegas.
2. Random number generators. Pseudo-random sequences. Transforming pseudo-randomness and similation of various probability distributions (e.g., inversion method). Some of the major distributions, like binomial, negative binomial, Poisson, exponential, normal will be examined in this perspective.
3. Applications to cryptography: elements of primality testing and factorization by Monte-Carlo methods. The RSA public key cryptosystem. Applications to symbolic computation: Identity testing (polynomial identities, identities in matrix computations).
4. Random allocations, hashing and signature tables. The birthday paradox and coupon collector problems. Analysis and applications to "hit counting" for large data bases. Random sampling strategies (by positions or domain values).
5. Random words and pattern matching. The loglog-counting algorithm for estimating cardinalities of large data streams; applications to traffic monitoring in routers. Algorithms for frequency moments based on stable laws.

See the reference link by Philippe FLAJOLET

Prerequisites:
A general awareness to the theory of algorithms as wellas fluency with the practice of computing. The course will be essentially self-contained as regards probability theory but willingness on the part of the audience to follow basic calculus arguments will be assumed.

Course Lecturers:
Professor Philippe FLAJOLET (Research Dir. INRIA,France)

Course Director:
Kanchana Kanchanasut (Asian Institute of Technology, Thailand)

Registration:
Please go to www.asian04.org/school/schoolform.asp to proceed your registration.

Venue:
Baan Klang Doi Hotel Resort & Spa

Contact:
Wilaiwan Phanarin
Phone: +66 2 524 6613
E-mail: wilaiwan@ait.ac.th