This doesn't seem correct? All the compression algorithms I have some amount of understanding of (that being JPEG and H.264; not a ton, but fairly widespread) have some concept of mostly-independently-compressed blocks. You also see in practice that many compression tools can use multiple threads.

From a theoretical perspective, compressing something is largely a search problem; you're searching through a space of possible representations in order to find the smallest one. Search problems can often be parallelized.