However, it's important to note that this paper doesn't show that NAS algorithms as originally designed, with completely independent training of each proposed architecture, are equivalent to random search. Rather, it shows that weight sharing, a technique introduced by ENAS [1] which tries to minimize necessary compute by training multiple models simultaneously with shared weights, doesn't outperform random baselines. Intuitively, this makes sense: weight sharing dramatically reduces the number of independent evaluations, and thereby leads to far less signal for the controller, which proposes architectures.
The paper itself makes this fairly clear, but I think it's easy to misinterpret this distinction from the abstract.
[1] ] H. Pham, M. Y. Guan, B. Zoph, Q. V. Le, and J. Dean. Efficient neural architecture search via parameter sharing. ICML, 2018.