i=1 given any x efﬁciently, as justiﬁed by the following theorem.

3 COMPUTATIONALLY EFFICIENT (DE)COMPRESSION WITH PCS

In the previous section, we have boiled down the task of lossless compression to calculating con-
ditional probabilities {li(xi), hi(xi)}D
i=1 given p and xi. This section takes PCs into consideration
and demonstrates how these queries can be computed efﬁciently. In the following, we ﬁrst introduce
relevant background on PCs (Sec. 3.1), and then proceed to introduce the PC-based (de)compression
algorithm (Sec. 3.2). Finally, we empirically evaluate the optimality and speed of the proposed
compressor and decompressor (Sec. 3.3).
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS