Lovasz theta function - uses Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
 A: Schrijver long ago established a connection to the Delsarte bound for a 
Hamming association scheme:
A. Schrijver, "A comparison of the Delsarte and Lovasz bounds," IEEE Transactions on Information Theory, 25: 425-429 (1979).
A: One of the most important properties of the Lovász theta function is that for any $\epsilon >0$, it can be approximated to within an $\epsilon$ additive error in polynomial time (by the Ellipsoid Method).
Moreover, for every graph $G$, it is well-known that
$$\alpha(G) \leq \vartheta(G) \leq \overline{\chi}(G),$$
where $\alpha(G)$ is the size of a largest independent in $G$, $\vartheta(G)$ is the Lovasz theta number of $G$, and $\overline{\chi}(G)$ is the chromatic number of the complement of $G$.
For perfect graphs, we have $\alpha(G) = \vartheta(G) = \overline{\chi}(G)$.  In particular $\vartheta(G)$ is always an integer.  Therefore, rounding an approximation of the Lovász theta function yields a polynomial-time algorithm to compute the chromatic number of perfect graphs.  As far as I know, no other efficient algorithm is known.
