Compressed sensing (CS) is a signal processing technique that allows for accurate, polynomial time recovery of sparse data-vectors based on a small number of linear measurements. In its most basic form, robust CS can be viewed as a specialized error-control coding scheme in which the data alphabet does not necessarily have the structure of a finite field and where the notion of a “parity-check” is replaced by a more general functionality. It is therefore possible to combine and extend classical CS and coding-theoretic paradigms in terms of introducing new minimum distance, reconstructions complexity, and quantization precision constraints. In this setting, we derive fundamental lower and upper bounds on the achievable compression rate for such constrained compressed sensing (CCS) schemes, and also demonstrate that sparse reconstruction in the presence of noise can be performed via low-complexity correlation-maximization algorithms that operate based on belief propagation iterations. Our problem analysis is motivated by a myriad of applications ranging from compressed sensing microarray designs, reliability-reordering decoding of linear block-codes, identification in multi-user communication systems, and fault tolerant computing. This is a joint work with Wei Dai and Vin Pham Hoa from the ECE Department at UIUC.