<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />

  TITLE:    <em>Introduction to Convergence Laws and 0-1 </em> <p>

  SPEAKER: Kevin Compton, BRICS, Aarhus, and University of Michigan 
<p>

  DATE: Friday, 5 March 1999<p>

  PLACE and TIME: Room E3-209 at 13:00. <p>

  ABSTRACT:  <p>

Random structures have many applications in computer science.
For example, random graphs and random permutations are
useful in average case analyses of algorithms.  Over the
last 25 years, researchers have made a systematic investigation
of the properties of random structures using tools from logic,
combinatorics and probability theory.  Rather than taking the
traditional approach of computing probabilities of properties
on a case by case basis, they have asked whether all properties
expressible in a given logic have a limiting probability in
a particular class of random structures.  When this happens,
we say that a convergence law holds.  If, in addition, the limiting
probability is always 0 or 1 for all properties expressible in the
logic, we say that a 0-1 law holds.  We survey the different
directions this area of research has taken and describe applications
in the study of database query optimization and approximation
of NP optimization problems.