The OP is asking for the underside concrete cover above a parking deck for nonprestressed concrete. If you have a crack through the slab which allows water and contaminants to leak through, the bottom cover could be 3/4" or 3" and there would still be cracked and spalled concrete due to steel expansion at the crack. Bottom cover is immaterial to this corrosion.
@Hokie - since concrete is usually a water saturated environment for reinforcement, it is not the water exposure that causes corrosion of steel. It is the water in combination with a contaminant (typically chlorides). The better strategies are geared at limiting rebar exposure to chlorides (and other contaminants).
For top rebar this includes cover, tighter concrete (usually with higher strength, fly ash or GGBFS), corrosion inhibitors (DCI), and the sealing/limiting of cracks.
For bottom reinforcement, bottom cover doesn't matter for chloride attacks (water carries the chlorides down) unless you are in a surf zone (New York is not). The worst I can think of would be carbonation from the underside due to high CO2.
@TXStructural - How can you make the statement "This requirement is frequently overlooked"? This table is new (2008) and just now being adopted by building codes.