Consider the accepting POVM ($\Pi$, $I-\Pi$) of a fixed QMA machine. Let d be the number of eigenstates of $\Pi$ that are at least 2/3. Decide if d is at least some fixed s, or at most s/2. This i...
Suppose you are given a sparse directed graph on $n$ vertices with a maximum degree at most $d$ and a parameter $\epsilon \in [0,1]$. We wish to design a testing algorithm that accepts (with probabili...
The complexity class QMA(2) has no known upper bounds aside from NEXP. It is unknown whether this class lies in BQEXP, which gives a quantum computer exponential time to decide a problem with $\ge ...
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...
Does envy-freeness up to any good (EFX) always exist for indivisible item allocation? An allocation is EFX if no agent envies another agent after removing any single item from the other agent's bun...
QAC0 is the class of constant-depth quantum circuits with single-qubit gates and Toffoli gates. Is QAC0 with fanout more powerful than QAC0 with fanout *only allowed at the beginning of the circuit...
Let $F_k(G)$ be the $k$-token graph of $G$, which has: * ${n \choose k}$ vertices, represented by $S \subseteq [n]$ of size $|S| = k$ * each edge $(S,T)$ is where the symmetric difference of S and 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 α for which α-MMS (maximin share) allocations always exist? The maximin share (MMS) is the value an agent can guarantee by dividing items into n bundles and receiving the worst bun...
What is the complexity of computing the ground state energy of the EPR Hamiltonian? The EPR Hamiltonian is a quantum Hamiltonian defined on a graph where each edge contains a projector onto the sym...
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 ...