@inproceedings{b71281f04d4444209bfa2c45b74c02af,

title = "Ramanujan graphs and the solution of the Kadison-Singer problem",

abstract = "We survey the techniques used in our recent resolution of the Kadison-Singer problem and proof of existence of Ramanujan Graphs of every degree: mixed characteristic polynomials and the method of interlacing families of polynomials. To demonstrate the method of interlacing families of polynomials, we give a simple proof of Bourgain and Tzafriri's restricted invertibility principle in the isotropic case.",

keywords = "Interlacing polynomials, Kadison-Singer, Mixed characteristic polynomials, Mixed discriminants, Ramanujan graphs, Restricted invertibility",

author = "Marcus, {Adam W.} and Spielman, {Daniel A.} and Nikhil Srivastava",

note = "Funding Information: Thus, each vector has the same norm ‖r(a,b)‖2 = 2/d, and applying Theorems 1.7 and 5.1 shows that ( √ )2 ∗ 2 √ (a,b)∈Er(a,b)r(a,b)≤d 1+ d = d + 2 + 2 2d with positive probability. This bound has asymptotically the same dependence on d as the correct bound established using matching polynomials. Moreover, it immediately proves that the dependence on ϵ in Theorem 5.1 cannot be improved: if it could,√ the above argument would imply the existence of signings with largest eigenvalue o( d), contradicting the Alon–Boppana bound. Thus, the matrices arising in the study of Ramanujan graphs witness the sharpness of our bounds on mixed characteristic polynomials. 2 Acknowledgements. Adam W. Marcus: Research partially supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship, Grant No. DMS-0902962. Daniel A. Spielman: Research partially supported by NSF grants CCF-0915487 and CCF-1111257, a Simons Investigator Award, and a MacArthur Fellowship. Funding Information: Adam W. Marcus: Research partially supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship, Grant No. DMS-0902962. Daniel A. Spielman: Research partially supported by NSF grants CCF-0915487 and CCF-1111257, a Simons Investigator Award, and a MacArthur Fellowship. Publisher Copyright: {\textcopyright} ICM 2014.All rights reserved.; 2014 International Congress of Mathematicans, ICM 2014 ; Conference date: 13-08-2014 Through 21-08-2014",

year = "2014",

language = "English (US)",

series = "Proceeding of the International Congress of Mathematicans, ICM 2014",

publisher = "KYUNG MOON SA Co. Ltd.",

pages = "363--386",

editor = "Jang, {Sun Young} and Kim, {Young Rock} and Dae-Woong Lee and Ikkwon Yie",

booktitle = "Invited Lectures",

}