Possible Topics for Talks

Each topic has provisoriacally assigned a supervisor, (EA) for Ernst Althaus, (PS) for Peter Sanders.

Skip List:
Randomized data structure for sorted sequences. For its simplicity and efficiency, Skip-Lists are used in LEDA [1, Section 8.3,] (EA).
Convex Hull:
The convex hull of a set of points is the smallest convex set that contains all the points. The algorithm is a randomized incremental algorithm, i.e. the points were added one by one in a random order and the convex hull of the current set is maintained [1, Section 9.2,] (EA). Assigned to Wei Ding.
Satisfiability:
A (relatively) fast randomized algorithm for finding satisfying assignments of satisfiable formulae in concunctive normal form [2] (EA). Assigned to Hans Raj Tiwary
Maximum Satisfiability:
given a set of clauses in conjunctive normal form over n variables, find the truth assignment for the variables that satisfy the maximum number of clauses. You should present an algorithm based on randomized rounding [1, Section 5.2,] (EA). Assigned to Paul McCabe.
s-t cuts
There is a simple proof via randomized rounding that the LP relaxation of integer linear program for s-t cuts is integral [Srinivasan: Approximation algorithms via randomized rounding: a survey] (ask citeseer) (EA).
Primality Testing:
Given a k bit integer find out in time polynomial in k whether it is a prime number. Although recently a deterministic polynomial time algorithm for primality testing has finally been found. Randomized Algorithms remain the only practical choice. [1, Section 14.6,] (EA). Assigned to Mehmet Kiraz.
Multiple Choice Allocation:
Explain the analysis of the shortest queue algorithm. http://ls2-www.cs.uni-dortmund.de/ voecking/aracne.ps
Two-Point Sampling:
A way to make more out of your random bits [1, Section 3.4,]. (EA)
Expander Graphs:
Graphs with very nice properties. For example arbitrary subsets of nodes can communicate with arbitrary other subsets at high bandwidth [1, Section 5.3,] (EA).
Routing:
Communication in Parallel Computers can suffer freom severe contention. It turns out that choosing random intermediate destinations resoleves this contention in many cases [1, Section 4.2,] http://ls2-www.cs.uni-dortmund.de/ voecking/papers/STOC01.ps.gz (PS). Assigned to Eske Vladimir.
Random Number Generators:
[3, Section 7.1,][4, 5] (PS). Assigned to Kara, Abdul Qadar
Random Bit Generators:
[3, Section 7.4,] (PS). Assigned to Waqar Saleem.
Generating Nonuniform Random Variables:
For example how to generate RVs that are binomially distributed, normally distributed, exponentially distributed,...[3, Section 7.2-7.3,] (PS).
Random Sampling:
How to pick a random sample from an array correctly and efficiently -- by coin tosses, with replacement, without replacement [5] (PS). Assigned to Dimitris Michail.
Numerical Integration:
It turns that randomization is important for fast numerical integration of functions that depend on a large number of variables [3, Section 7.6-7.8,] (PS). Assigned to Ruzica Riskac.
Simulated Annealing:
A randomized optimiztion strategy based on local search with a nice analogy to the behavior of some physical systems [6] (PS).
Paging:
How randomization can fool an otherwise all too powerful adversary in virtual memory management [1, Section 13.1-13.3,]. (EA) Assigned to Kanela Kaligossi.
MST in sublinear time?
One can find the approximate weight of a minimum spanning tree very quickly for integer edge weights.
http://www.cs.princeton.edu/~chazelle/pubs/MstApprox.ps. (PS)
Graphics:

http://www.gris.uni-tuebingen.de/publics/staff/Michael_Wand_abs.html
The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes. (PS)

References

1
J. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

2
Uwe Schöning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In 40th IEEE Symposium on Foundations of Computer Science, pages 410-414, 1999.

3
W. H. Press, S.A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes in C. Cambridge University Press, 2. edition, 1992.

4
P. L'Ecuyer. Random numbers for simulation. Communications of the ACM, 33(10):85-97, 1990.

5
D. E. Knuth. The Art of Computer Programming -- Seminumerical Algorithms, volume 2. Addison Wesley, 2nd edition, 1981.

6
E. H. L. Aarts and J. H. M Korst. Simulated Annealing and Boltzmann Machines. John Wiley & Sons, Chichester, U.K., 1989.


Peter Sanders
Fri Dec 13 17:00:35 MET 2002