Monday, June 5, 2023, 3pm

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

Event Type: Thesis Proposals
Room Number: In Person
Building: Traffic21 Classroom, Gates Hillman 6501
Speaker's Name: XINYU WU
Speaker Website: www.andrew.cmu.edu…
Speaker's Professional Title: Ph.D. Student, Computer Science Department, Carnegie Mellon University
Talk Title: Applications of spectral properties of random matrices in algorithms
Event Poster Title: Poster
Event Poster URL: www.cs.cmu.edu…
For More Information: jennsbl@cs.cmu.edu | deb@cs.cmu.edu
Affiliations: Computer Science Department (CSD)
Organization(s): SCS