Open/unsolved problems in (computational) random matrix theory / matrix completion?
Not sure if this is the kind of thing you want but here is something I find fascinating : This particular breakthrough paper's proof technique is in a sense  "random matrix theory", https://arxiv.org/abs/1505.08010 
(..I dont know if before this paper anyone had guessed that random matrix is the way of think of this question..)

I feel it is a deeply important question to be able to (a) come up with a version of this which shows this existential result restricted to only simple graphs and (b) come up with a deterministic polynomial time algorithm (or prove that such a thing can't exist!) which makes this existential argument constructive in the case of simple graphs.  This isnt clear for even just bipartite graphs!