title: Algorithm to generate a (pseudo-) random high-dimensional function
body: <p><strong>I don't mean a function that generates random numbers, but an algorithm to generate a <a href="http://en.wikipedia.org/wiki/Random_function" rel="nofollow">random function</a></strong></p>
  
  <p>"High dimension" means the function is multi-variable, e.g. a 100-dim function has 100 different variables.</p>
  
  <p>Let's say the domain is [0,1], we need to generate a function f:[0,1]^n->[0,1]. This function is chosen from a certain class of functions, so that the probability of choosing any of these functions is the same. 
  (This class of functions can be either all continuous, or K-order derivative, whichever is convenient for the algorithm.)</p>
  
  <p>Since the functions on a closed interval domain are uncountable infinite, we only require the algorithm to be pseudo-random.</p>
  
  <p>Is there a polynomial time algorithm to solve this problem?</p>
  
  <hr>
  
  <p>I just want to add a possible algorithm to the question(but not feasible due to its exponential time complexity). The algorithm was proposed by the friend who actually brought up this question in the first place:</p>
  
  <p>The algorithm can be simply described as following. First, we assume the dimension d = 1 for example. Consider smooth functions on the interval I = [a; b]. First, we split the domain [a; b] into N small intervals. For each interval Ii, we generate a random number fi living in some specific distributions (Gaussian or uniform distribution). Finally, we do the interpolation of
  series (ai; fi), where ai is a characteristic point of Ii (eg, we can choose ai as the middle point of Ii). After interpolation, we gain a smooth curve, which can be regarded as a one dimensional random function construction living in the function space Cm[a; b] (where m depends on the interpolation algorithm we choose).</p>
  
  <p>This is just to say that the algorithm does not need to be that formal and rigorous, but simply to provide something that works.</p>