Earlier lower bounds by Furst-Saxe-Sipser and Yao. Both also use random restriction methods.