-------------------------------------------------------------------------------
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			 P H D   D E F E N S E
                                       
		      Wednesday December 13, 1995
                                       
				 3:00pm
                                       
			        MCS 135

-------------------------------------------------------------------------------

	     HARD ON AVERAGE PROBLEMS AND THEIR APPLICATION

		      Sivaramakrishnan Rajagopalan

   This thesis is in two parts.  In the first part, the average case
   completeness of a randomized version of Hilbert's Tenth Problem based
   on a simple assumption is proved.  Hilbert's Tenth Problem is the tenth
   in a famous list of problems presented by David Hilbert in 1900
   ([Hilbert 1900]) which were presented as a challenge to mathematicians
   of the twentieth century.  The problem is to find the integer roots of
   a multivariate polynomial with integer coefficients.  This problem was
   shown to be undecidable in the famous work of [Davis Putnam Robinson
   61] and [Matijasevic 70].  A randomized version of this problem is
   considered where the coefficients of the polynomial are chosen at
   random and the task is to find an integer root which is less than a
   randomly chosen bound.  First, it is shown that, given a simple number
   theoretic assumption, this problem is complete on average using
   randomizing reductions of [Venkatesan Levin 88].  Next, based on the
   same assumption, and a more complicated proof, it is shown that $D=NP$
   \ie Adleman's conjecture holds if the assumption is true.
   
   In the second part of this thesis, a scheme for general purpose
   pseudorandom generators is presented which is useful for randomized
   algorithms, simulations and cryptography.  The starting point is a
   slow but high quality generator which is used in a preprocessing step.
   This slow generator could be, for instance, the cryptographically
   strong ([Blum Micali 82], [Yao 82]) generator or one based on a weakly
   random sources ([Vazirani Vazirani 87], [Zuckerman 90]).  Using the
   bits of the slow generator as if they are truly random, a method is
   presented for stretching these bits to obtain a generator which has a
   provable security which can be changed by changing the parameter
   settings up to the security of the underlying generator, is fast in
   practice, and has many distributional and unpredictability properties
   that are desirable in pseudorandom generators, because of which this
   generator seems suitable for application in randomized algorithms.
   Moreover, this generator provides a smooth tradeoff of security
   vs. running time which can be tuned for any particular application.
   An implementation which was based on the block cipher DES was found to
   be faster than popular generators.
   
   The first part of the thesis is joint work with R.~Venkatesan and a
   preliminary version of this work appeared in [Venkatesan, Rajagopalan
   92].  The second part is joint work with W.~Aiello and R.~Venkatesan
   and a preliminary version of this work appeared in [Aiello,
   Rajagopalan, Venkatesan 95].

Advisor: Prof. Leonid Levin
-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------