We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian H which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>>

A graph G has an \emph{S-factor} if there exists a spanning subgraph F of G such that for all v \in V: \deg_F(v) \in S.
The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>