Brain-inspired computing—leveraging neuroscientific principles underpinning the unparalleled efficiency of the brain in solving cognitive tasks—is emerging to be a promising pathway to solve several algorithmic and computational challenges faced by deep learning today. Nonetheless, current research in neuromorphic computing is driven by our well-developed notions of running deep learning algorithms on computing platforms that perform deterministic operations. In this article, we argue that taking a different route of performing temporal information encoding in probabilistic neuromorphic systems may help solve some of the current challenges in the field. The article considers superparamagnetic tunnel junctions as a potential pathway to enable a new generation of brain-inspired computing that combines the facets and associated advantages of two complementary insights from computational neuroscience: 1) how information is encoded and 2) how computing occurs in the brain. The hardware-algorithm co-design analysis demonstrates 97.41% accuracy of a state-compressed 3-layer spintronics-enabled stochastic spiking network on the MNIST dataset with high spiking sparsity due to temporal information encoding.