Perform matrix completion of a real $2n \times 2n$ matrix $\mathbf{C}$ (i.e., we have only a few entries of the matrix $C$ and want to fill in the remaining ones) with the constraints that:
- $\mathbf{C}$ is positive semidefinite with eigenvalues less than $1$,
- $\mathbf{C}$ has some submatrices with a fixed Pfaffian
We have the assumption that there exists at least one solution that satisfies the above constraints.
It is possible to solve in $O(\mathrm{poly}(n))$ time the following problem?
(Note that, without constraint $2$), it would be a semidefinite program, so the solution can be found in $O(\mathrm{poly}(n))$ time.