The fourth set of Lecture notes for my course is available here. This one is large deviation and concentration inequalities, for sums of independent scalar or matrices random variables. It also has 5 open problems related to problems involving concentration of certain random matrices. As usual, I will document the open problems here, while referring a much more detailed description of the problems on the notes, including description of partial progress.

**Open Problem 4.1. (Improvement over Non-commutative Khintchine inequality)**

Let be symmetric matrices and i.i.d.. Does the following hold?

This problem is motivated by the results here and here. See Open Problem 4.1. in these notes for references, motivation, partial progress, and discussion of potential directions for progress.

**Open Problem 4.2. (Lataa-Riemer-Schutt)**

Let be a symmetric matrix with (otherwise) independent gaussian entries. Prove (or disprove):

Note that, . This conjecture is motivated by comments and results in this, this, and this paper. If the largest variance of an entry is comparable to the one of many of the entries, the results in here imply this conjecture. However, in general, the best known upperbound, due to Ramon van Handel, and has an extra factor of . The notes have a lot more information.

**Open Problem 4.3. (Matrix version of 6 deviations suffice)**

This open problem appears in a nice blog post by Raghu Meka. We refer to the discussion on the notes and to Raghu’s blog post for references, and context of the problem.

Prove or disprove: there exists a universal constant such that, for any choice of symmetric matrices satisfying (for all ), there exists such that

In the notes we also propose investigating (and motivate) a strengthening of this conjecture, asking, in the same conditions, for

$latex \left\| \sum_{k=1}^n \eps_k H_k \right\| \lesssim \left\| \sum_{k=1}^n H_k^2 \right\|^{\frac12}$

**Open Problem 4.4. (OSNAP)**

This problem concerns a conjecture by Jelani Nelson and Huy L. Nguyen regarding Sparse Norm-Approximating Projections, a form of dimension reduction useful for fast linear algebra.

We defer the exposition of the full open problem to the notes and present here part (3) of it, a particularly interesting instance of the conjecture.

Part (3) of the problem: Let and i.i.d. random vectors with i.i.d. entries

Note that The conjecture is that, there exists $c_1$ and $c_2$ positive universal constants such that

for and $s\geq c_2 \frac{\log\left( \frac{d}{\delta} \right)}{\varepsilon^2}$.

I think this would is an interesting question even for fixed , for say , or even simply understand the value of

**Open Problem 4.5. (Random k-lifts of graphs)**

The next problem of this lecture is inspired in this paper (see the notes for more context and current status). Given a graph , on nodes and with max-degree , and an integer a random lift of is a graph on nodes obtained by replacing each edge of by a random bipartite matching. More precisely, the adjacency matrix of is a matrix with blocks given by

where is uniformly randomly drawn from the set of permutations on elements, and all the edges are independent, except for the fact that . In other words,

where corresponds to the Kronecker product. Note that , where is the all-ones matrix.

Give a tight upperbound to