MAX k-CUT and approximating the chromatic number of random graphs

88 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

The fundamental group of random 2-complexes (2007, background): “These intermediate results do not involve randomness and may be of independent interest.”
Random Simplicial Complexes (2014, background): “One may mention random surfaces [15], random 3-manifodls [4], random configuration spaces of linkages [6].”
Limit theorems for Betti numbers of random simplicial complexes (2010, background): “Several papers have recently appeared concerning the topology of random simplicial complexes [11, 2, 10, 12, 13, 16, 9].”
Minimum Interference Channel Assignment in Multiradio Wireless Mesh Networks (2008, methodology): “Now, the semidefinite program for the channel assignment problem in the standard SDP form (Matrix Notation) [34] can be represented as follows.”
Minimum Interference Channel Assignment in Multi-Radio Wireless Mesh Networks (2007, methodology): “In [37], the authors consider Gn,p graphs which are defined as random graph over n vertices where each edge exists with a uniform probability ofp.”
The threshold function for vanishing of the top homology group of random $d$-complexes (2009, background): “To place this paper in a more general context, we mention that there has recently been quite a bit of exciting work on topologically constructed probability spaces; we refer in particular to [6, 7, 8, 9, 12, 14] and the references therein.”