☆

1

Great SDP relaxation of max-k-cut and max-bisection: very inspiring!
### Complicated analysis:
The analysis to prove the approximation guarantee is quite complicated though. Much more complicated than the one of [the Goemans-Williamson algorithm](https://en.wikipedia.org/wiki/Semidefinite_programming#Example_3) for max-cut.
Is a simpler analysis possible? Or another relaxation leading to a simpler analysis having similar or better approximation guarantees?
### Implementing the algorithms in a scalable way:
How can we implement such an algorithm in a scalable way? Say for a sparse graph with 1M nodes and 100M edges?
For Goemans-Williamson, this is a try: https://github.com/maxdan94/spingraphSDP

☆

2

For me, the paper is similar to Kleinberg's [masterpiece](https://www.cs.cornell.edu/home/kleinber/nips15.pdf).

## Comments: