elyot talk
authorEdgar Bering <ebering@csclub.uwaterloo.ca>
Mon, 25 Oct 2010 17:21:43 +0000 (13:21 -0400)
committerEdgar Bering <ebering@csclub.uwaterloo.ca>
Mon, 25 Oct 2010 17:21:43 +0000 (13:21 -0400)
events.xml

index 69f7c5f..8e9e0f6 100644 (file)
@@ -4,6 +4,42 @@
 <eventdefs>
 
 <!-- Fall 2010 -->
 <eventdefs>
 
 <!-- Fall 2010 -->
+<eventitem date="2010-10-26" time="04:30 PM" room="MC4040" title="Analysis of randomized algorithms via the probabilistic method">
+  
+    <short><p>In this talk, we will give a few examples that illustrate the basic method and show  how it can be used to prove the existence of objects with desirable combinatorial  properties as well as produce them in expected polynomial time via randomized  algorithms.  Our main goal will be to present a very slick proof from 1995 due to  Spencer on the performance of a randomized greedy algorithm for a set-packing  problem.  Spencer, for seemingly no reason, introduces a time variable into his  greedy algorithm and treats set-packing as a Poisson process.  Then, like magic,  he is able to show that his greedy algorithm is very likely to produce a good  result using basic properties of expected value.
+</p></short>
+  
+  
+    <abstract><p>The probabilistic method is an extremely powerful tool in combinatorics that can be 
+used to prove many surprising results.  The idea is the following: to prove that an 
+object with a certain property exists, we define a distribution of possible objects 
+and use show that, among objects in the distribution, the property holds with 
+non-zero probability.  The key is that by using the tools and techniques of 
+probability theory, we can vastly simplify proofs that would otherwise require very 
+complicated combinatorial arguments.
+</p><p>As a technique, the probabilistic method developed rapidly during the latter half of 
+the 20th century due to the efforts of mathematicians like Paul ErdÅ‘s and increasing 
+interest in the role of randomness in theoretical computer science.  In essence, the 
+probabilistic method allows us to determine how good a randomized algorithm's output 
+is likely to be.  Possibly applications range from graph property testing to 
+computational geometry, circuit complexity theory, game theory, and even statistical 
+physics.
+</p><p>In this talk, we will give a few examples that illustrate the basic method and show 
+how it can be used to prove the existence of objects with desirable combinatorial 
+properties as well as produce them in expected polynomial time via randomized 
+algorithms.  Our main goal will be to present a very slick proof from 1995 due to 
+Spencer on the performance of a randomized greedy algorithm for a set-packing 
+problem.  Spencer, for seemingly no reason, introduces a time variable into his 
+greedy algorithm and treats set-packing as a Poisson process.  Then, like magic, 
+he is able to show that his greedy algorithm is very likely to produce a good 
+result using basic properties of expected value.
+</p><p>Properties of Poisson and Binomial distributions will be applied, but I'll remind 
+everyone of the needed background for the benefit of those who might be a bit rusty.
+Stat 230 will be more than enough. Big O notation will be used, but not excessively.
+</p></abstract>
+  
+</eventitem>
+
 <eventitem date="2010-10-19" time="04:30 PM" room="RCH 306" title="Machine learning vs human learning - will scientists become obsolete?">
   
     <short><p><i>by Dr. Shai Ben-David</i>.
 <eventitem date="2010-10-19" time="04:30 PM" room="RCH 306" title="Machine learning vs human learning - will scientists become obsolete?">
   
     <short><p><i>by Dr. Shai Ben-David</i>.