Approximating Random MAX-k-SAT
Their result is not optimal. First, it was improved upon by Yannet Interian. She obtained a 20/19 approximation (if I recall correctly). See the reference:


  Y. Interian. Approximation algorithm for Random MAX-kSAT. Theory and Applications of Satisfiability Testing (SAT 2004), Revised Selected Papers. LNCS 3542, 2005.


Her result has apparently been improved further by Fernandez de la Vega and Karpinski to 1.0957, but I cannot find an online preprint of this paper.

Given such a low approximation ratio, I wonder if it is reasonable to conjecture that there is a PTAS.