Embedding pico/femto base-stations and relay nodes in a macro-cellular network is a promising method for achieving substantial gains in coverage and capacity compared to macro only networks. These heterogeneous base-station types operate on the same wireless channel providing range expansion and higher spatial reuse via cell splitting. However, since these base-stations are deployed in an unplanned manner, they require the use of innovative interference coordination techniques across cells in order to realize the promised capacity and range gains. In this paper, we describe new paradigms for design and operation of such heterogeneous cellular networks. Specifically, we focus on cell splitting, range expansion, semi-static resource negotiation on third-party backhaul connections, and fast dynamic interference management for QoS via over-the-air signaling. Notably, our methodologies and algorithms are simple, lightweight, and incur extremely low overhead; thus, they can be incorporated easily into 4G standards such as Long Term Evolution (LTE) in 3GPP.