UCSC Theory CS Reading Group: Impossibility of low-rank embeddings for triangle-rich graphs
C. Seshadhri · 56:25
This lecture (part 2) proves that random graphs generated from \(n\) vectors in \(\mathbb{R}^d\) via clipped inner-product edge probabilities cannot be both sparse and triangle-rich on constant-degree vertices unless...