Computer Science Thesis Proposal

June 5, 2023 3:00pm — 4:30pm

Location:
In Person - Traffic21 Classroom, Gates Hillman 6501

Speaker:
XINYU WU , Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.andrew.cmu.edu/user/xinyuw1/

Random matrices have found various applications in computer science. Some examples include data analysis, numerical linear algebra, wireless communications and more. In particular, spectral properties of random matrices can have many applications and have been widely studied. A common class of matrices which we have results on is matrices with independent and identically distributed (i.i.d.) entries. However, random matrices with relations between entries tend to be harder to analyze.

In this thesis, we study three applications of random matrices without i.i.d. entries in algorithms.

1. We study random graphs which have adjacency matrices which are matrix-coefficient polynomials evaluated on random permutation and matching matrices. We identify properties of these graphs, and give some examples. We investigate two algorithmic properties of these graphs: first, we analyze an algorithm which constructs in deterministic polynomial time examples of these graphs which have spectrums close to certain infinite graphs.  

2. For the other application, we interpret graphs of this form as degree-2 constraint satisfaction problems (CSPs), and we find a tight estimate of the SDP value of these CSPs.

3. Finally, we will look at an application in quantum tomography, i.e. learning properties of quantum states. We will prove a lower bound on the number of samples needed of an unknown state in order to learn the value of measurements of observables with respect to the state. To do so, we will need to prove some technical results involving tensor products of random unitary matrices.

Thesis Committee:

Ryan O'Donnell (Co-chair)
Pravesh Kothari Co-chair)
Aayush Jain
Tselil Schramm (Stanford University)

Additional Information

Add event to Google
Add event to iCal