I am interested in examples of constructions in the complexity theory which are better than a random constructions.
The only one example of such construction which I know is in the field of error-correcting codes. Algebraic-geometry codes are better in some range of parameters than a random codes.
One can easily to construct such artificial examples. I am interested in the examples like algebraic geometry codes, where it is easy make a random construction and it is not obvious how to do better.