Julia sets of quadratic maps are among the most drawn images in Mathematics due both to their beauty, and their intrinsic complexity. We have previously shown with M. Braverman, that even for computable polynomials, some of these sets are not computable, and have characterized the non-computable examples. Many delicate open questions have remained regarding computational complexity of computable quadratic Julia sets. I will briefly review the recent progress and will present a powerful new technique for constructing lower complexity bounds. It originated in our recent work with C. Rojas, which tackled a natural related question of computational complexity of attractors in the family of real quadratics, viewed as mappings of the real line.