Traditional compression schemes typically require decompressing the entire compressed archive to access a single bit. Similarly, updating a single bit requires re-encoding the entire archive. In this talk, I will present recent advances in compression with locality, where the goal is to minimize the number of bits that need to be accessed or modified when decoding or updating a single bit. Sample questions we will address include: What is the minimum number of bits that must be read or changed to decode or update a single bit? How does this minimum change when compression is handled in a distributed fashion (Ã la Slepian-Wolf)? And is it possible to decode a single bit with perfect privacy?