<p>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", <a href="https://arxiv.org/abs/1505.08010" rel="nofollow noreferrer">https://arxiv.org/abs/1505.08010</a> 
(..I dont know if before this paper anyone had guessed that random matrix is the way of think of this question..)</p>

<p>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! </p>

CC BY-SA 3.0
2018-03-03T08:08:42.950Z
2018-03-03T21:27:00.490Z
2018-03-03T21:27:00.490Z
Student
<p>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?</p>

<p>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. </p>

<matrices><open-problem>
Open/unsolved problems in (computational) random matrix theory / matrix completion?
Drew Brady
# Open/unsolved problems in (computational) random matrix theory / matrix completion?

(Asked by: username_0 on 2018-03-03)

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.

**Tags:** matrices, open-problem


---

## 1 answers

### Answer by username_1 on 2018-03-03. Score: 2

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!


---

