I was wondering what some open problems are in random matrix theory (especially those of interest to TCS people/so mainly non-asymptotic things, I imagine). Also, and relatedly, what are remaining/outstanding open problems in matrix completion?

In view of the questions above, I'd also be interested if people can point to research monographs/survey papers/texts that provide some background on the topics (RMT in computer science/matrix completion) above.


1 Answer 1


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.