If you don't mind filling the gaps in our knowledge with the gaps in yours, what are your favorite applications of spectral methods to graph algorithms ? I know there are applications to the search of large cliques (and more generally dense subgraphs), but surely there must be lots of other applications...
Pascal: the Arora-Barak-Steurer slightly subexponential algorithm for unique games is my worry of the day.
Luca: true. I taught a lecture on half of the Arora-Barak-Steurer paper yesterday, and got to show how confused I was about more or less everything. My nose is barely above the water, and when a factor of n suddenly appears or disappears, or an x becomes 1-x, or there is an extraneous factor of 1/2, I cannot tell whether there is a typo or whether I am overlooking something. Fortunately I get a second chance next week... (and I printed notes from your blog today, just in case they happen to be enlightening!)
If you don't mind filling the gaps in our knowledge with the gaps in yours, what are your favorite applications of spectral methods to graph algorithms ?
ReplyDeleteI know there are applications to the search of large cliques (and more generally dense subgraphs), but surely there must be lots of other applications...
You can teach those classes now. Then you'll learn even more than if you had taken those classes when you were a student
ReplyDeletePascal: the Arora-Barak-Steurer slightly subexponential algorithm for unique games is my worry of the day.
ReplyDeleteLuca: true. I taught a lecture on half of the Arora-Barak-Steurer paper yesterday, and got to show how confused I was about more or less everything. My nose is barely above the water, and when a factor of n suddenly appears or disappears, or an x becomes 1-x, or there is an extraneous factor of 1/2, I cannot tell whether there is a typo or whether I am overlooking something. Fortunately I get a second chance next week... (and I printed notes from your blog today, just in case they happen to be enlightening!)