Closing the Gap Between Short and Long XORs for Model Counting

Shengjia Zhao, Sorathan Chaturapruek, Ashish Sabharwal +1

Many recent algorithms for approximate model counting are based on a reduction to combinatorial searches over random subsets of the space defined by parity or XOR constraints. Long…