Using L^2 cohomology, Cheeger and Gromov define the L^2 rho-invariant on manifolds with arbitrary fundamental groups, as a generalization of the Atiyah-Singer rho-invariant. There are many interesting applications in geometry and topology. In this talk, we show linear bounds on the rho-invariants in terms of simplicial complexity of manifolds. First, we obtain linear bounds on Cheeger-Gromov invariants, using hyperbolizations. Next, we give linear bounds on Atiyah-Singer invariants, employing a combinatorial concept of G-colored polyhedra. As applications, we give new concrete examples in the complexity theory of high-dimensional (homotopy) lens spaces. This is a joint work with Shmuel Weinberger.