Robust stability of a continuous-time system with coefficients of the characteristic polynomial varying in a diamond can be considered as a ’dual’ problem to Kharitonov’s theorem on interval polynomials. This paper aims at developing similar results for discrete-time systems. Specifically, it shows that stability of a family of polynomials, whose complex coefficients lie in a diamond of a transformed parameter space, can be determined by simply checking four (eight) extreme polynomials. This result can be viewed as a counterpart of Kharitonov’s result (strong version) for discrete-time systems.