There has been a recent surge of interest in algorithmic questions relating to information revelation in games and auctions. Given that equilibrium outcomes of a game are intimately related to the beliefs of its participants, how should an informed authority reveal information to players in order to optimize a specified objective? We consider the computational complexity of two of the simplest instantiations of this question: (1) a single-item auction in which the seller possesses additional information regarding the item for sale, and (2) a Bayesian zero-sum game in which the authority chooses the information structure. In both cases, we prove that optimal signaling is hard assuming the hardness of a certain graph partitioning problem closely related to the k-densest subgraph problem.