Many computational processes make use of randomness to run efficiently.
At the same time, computational ideas underlie our basic concepts of
randomness.
We shall study various aspects of this interrelationship.  For
example,
<ul><li>Kolmogorov randomness (a.k.a. incompressibility) with a time bound
    <li>"Probabilistic construction" of computationally useful
         structures (expander graphs, etc.)
    <li>Computationally strong pseudo-random number generators
    <li>Proving hardness of approximation problems, without all of the
        hairy algebra.
</ul>
Some sample questions/issues:
<ul><li>Suppose you have an algorithm that uses <math>k(n)</math>
        random bits and errs with probability (say) 1/4.  Re-running
	the algorithm independently uses more random bits and
	decreases the error probability.  How many random bits must
	you use to get an error probability of 1/16?  Of
	<math>2<sup>-m</sup></math>?<p>
    <li>How does the Kolmogorov complexity of a satisfiable Boolean
        formula relate to the Kolmogorov complexity of its satisfying
	assignments?  For example,
        <ul><li>If <math>&psi;</math> is satisfied only by the
                all-true assignment, can <math>&psi;</math> be
		maximally incompressible?  (And what is the maximal
		complexity of a well-formed formula, anyway?)
            <li>Can one easily test compressible formulas for
                satisfiability? 
        </ul>
    <li>Intuitively, a chaotic dynamical system is both complex and
        (quasi-)random.  Can notions from computational complexity theory
	illuminate chaos?  Can notions from chaos theory illuminate
	computational complexity?
</ul>

Two not-too-technical descriptions of some of the course content:

<ul>
<li><a href="http://portal.acm.org/citation.cfm?id=261540.261545">
R.J. Solomonoff, "The Discovery of Algorithmic Probability",
<em>J. Comput. System Sci.</em> <b>55</b> (1997) 73-88</a>.<br /><br /></li>

<li><a href="http://www.siam.org/pdf/news/26.pdf">
S. Robinson, "Computer Scientist Finds Small-Memory Algorithm for
Fundamental Graph Problem", <em>SIAM News</em> <b>38,1</b> (2005) 26-28</a>.
<br /></li>
</ul>
(If either link fails or declines to serve the paper, and you are not
on a UW computer, sign on to one and try again.  If either fails from
a UW computer, please let me know.)