Suppose a CSP instance satisfies the conditions of the Lovasz Local Lemma (LLL). For example, in kSAT where clauses do not repeat variables, we require the maximum degree $D$ is at most $$ D \le \fr...
If the covering radius of a code is $r$, then for every vector $v$, there is a codeword with distance at most $r$ from $v$. One can bound the covering radius by the distance of the *dual* code from [t...
The Parisi value (approximately -0.763166...) represents the ground state energy density of the SK model in the thermodynamic limit. The main conjecture is whether QAOA, as depth p approaches infinity...
What is the best polynomial-time approximation ratio achievable for Max Di-Cut? Max Di-Cut is the directed graph version of Max Cut: given a directed graph, find a partition of vertices maximizing ...