Ciliberti; Mézard (Lossy Compression Data Compression)
Jump to navigation
Jump to search
Time Complexity
$O(n^{2})$
Space Complexity
$O(n^{2})$? bits
(Derived: size of the factor graph representation of the generator matrix, or size of the generator matrix itself)
Description
Constraint Satisfaction Problem with Random Gates
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2005