“Bulletin Board”

 School of Mathematics - October 30, 2014

Short Course

Discrete Probability for Analysis of Algorithms
Omid Etesami
School of Mathematics of IPM



Discrete probability is not only interesting in itself but also essential for analysis of algorithms. In this short course, you will be introduced to some probability theory topics such as tail inequalities and martingales that are useful for computer science. Our starting point is the analysis of a simple algorithm for finding the maximum among n elements. Next some entertaining counterintuitive examples are mentioned like non-transitive dice, and games that if played longer do not favor the stronger. Several inequalities, including a recent one by Ross that is stronger than the second moment method, are stated. Finally, it is shown that one can apply martingale tail inequalities to Doob martingales to analyze problems like bin-packing.


Date and Time: Wednesday, October 22 at 9:00-10:30 and 15:30-17:00
Thursday, October 23 at 13:30-15:00
Wednesday, October 29 at 9:00-10:30 and 14:00-115:00
Thursday, October 30 at 13:30-15:00
Place: Niavaran Bldg., Niavaran Square, Tehran, Iran
back to top
scroll left or right