Decentralized optimization methods enable on-device training of machine\nlearning models without a central coordinator. In many scenarios communication\nbetween devices is energy demanding and time consuming and forms the bottleneck\nof the entire system.\n We propose a new randomized first-order method which tackles the\ncommunication bottleneck by applying randomized compression operators to the\ncommunicated messages. By combining our scheme with a new variance reduction\ntechnique that progressively throughout the iterations reduces the adverse\neffect of the injected quantization noise, we obtain the first scheme that\nconverges linearly on strongly convex decentralized problems while using\ncompressed communication only.\n We prove that our method can solve the problems without any increase in the\nnumber of communications compared to the baseline which does not perform any\ncommunication compression while still allowing for a significant compression\nfactor which depends on the conditioning of the problem and the topology of the\nnetwork. Our key theoretical findings are supported by numerical experiments.\n