Complexity and robustness of frame structures