Note: I found a few references to this paper while doing some reading on error-correcting codes and had a difficult time tracking it down. To aid future researchers, I am putting the paper online here.
@inproceedings{gelfand1973complexity, title={On the Complexity of Coding}, author={Gelfand, S. I. and Dobrushin, R. L. and Pinsker, M. S.}, booktitle={Second International Symposium on Information Theory}, pages={177--184}, year={1973} }