Ciliberti; Mézard (Lossy Compression Data Compression)

From Algorithm Wiki
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

Reference

https://arxiv.org/abs/cond-mat/0504509