An SDP Primal-Dual Algorithm for Approximating the Lovasz-Theta Function The Lovasz Theta function on a graph G = (V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X(i,j) = 0$ whenever {i,j} is in E. This function appears as a subroutine for many algorithms on graph problems such as maximum independent set and maximum clique. We apply Arora and Kale's primal-dual method for SDP to design an algorithm to approximate the Theta-function within an additive error of d > 0 which runs in time O( (an/d)^2 (log n) M_e), where a = Theta(G) and M_e = O(n^3) is the time for a matrix exponentiation operation. It follows that on perfect graphs G, our primal-dual method computes Theta(G) exactly in time O(a^2 n^5 log n). Moreover, our techniques generalize to the weighted Lovasz Theta-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1 + e) in time $O( n^5/e^2 log n)$. This is joint work with Kevin Chang and Rajiv Raman.