Summary Organisms continually tune their perceptual systems to the features they encounter in their environment 1–3 . We have studied how ongoing experience reorganizes the synaptic connectivity of neurons in the olfactory (piriform) cortex of the mouse. We developed an approach to measure synaptic connectivity in vivo , training a deep convolutional network to reliably identify monosynaptic connections from the spike-time cross-correlograms of 4.4 million single-unit pairs. This revealed that excitatory piriform neurons with similar odor tuning are more likely to be connected. We asked whether experience enhances this like-to-like connectivity but found that it was unaffected by odor exposure. Experience did, however, alter the logic of interneuron connectivity. Following repeated encounters with a set of odorants, inhibitory neurons that responded differentially to these stimuli exhibited a high degree of both incoming and outgoing synaptic connections within the cortical network. This reorganization depended only on the odor tuning of the inhibitory interneuron and not on the tuning of its pre- or postsynaptic partners. A computational model of this reorganized connectivity predicts that it increases the dimensionality of the entire network’s responses to familiar stimuli, thereby enhancing their discriminability. We confirmed that this network-level property is present in physiological measurements, which showed increased dimensionality and separability of the evoked responses to familiar versus novel odorants. Thus, a simple, non-Hebbian reorganization of interneuron connectivity may selectively enhance an organism’s discrimination of the features of its environment.