Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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!
