Theoretical Results
NFL results apply to discrete functions, in which the expected description length is exponentially large with respect to the number of variables.
Does NFL apply to problems with polynomial description lengths?
New proofs:
The expected number of minima for local search over N points using a neighborhood of size K over all possible functions is N/k+1.
In expectation, randomly changing the representation of the search space is useful only if a search algorithm is inferior to random enumeration.