We study new cohomologies for the BPS operators of the N=4 Yang-Mills theory with SU(2), SU(3) and SU(4) gauge groups. The goal of this programme is to identify the black hole microstates in the dual field theory that are successfully counted by the index to match the Bekenstein-Hawking entropy. We first study the index over non-graviton cohomologies and identify their threshold levels. We present examples of the non-graviton operators in the SU(2) theory and in a subsector of the SU(3) theory that corresponds to the BMN matrix model. We also present an ansatz that can be used to construct these operators. Finally, we discuss non-trivial tower structures and partial no-hair behaviours of quantum black holes.