演讲人： Ravi Kannan Microsoft Research Labs, India
时间： 2007-10-19 10:00-2007-10-19 11:00
地点：FIT Building 4-603, Tsinghua University
内容：

 Spectral methods refer to algorithms which use Linear Algebra on the input matrix. There have been a wide range of applications of this. We will focus on two of them. The first use is in clustering problems in data generated by prbabilistic models. The typical problem here is - given random graphs with edge probabilities conforming to a certail law, find the law (the model). This uses crucially Wigner-type theorems on eigenvalues of random graphs. But in many applications, the undelying assumption that all entries of the matrix are independent is unrealistic. We argue that a more natural asssumption is that the columns of the matrix are independent vector-valued random variables. We show that Wigner-type bounds can be proved under this weaker assumption and use it carry out the clustring algorithms.
       In the second application, we look at combinatorial problems line maximum satisfiability and more generally Constraint Satisfaction Problems (CSP). These can be posed as tensor-optimization problems. We develop an analog of spectral dcomposition for tensors which can be carried out in polynomial time and use this to solve CSP approximately.

个人简介:

Ravi Kannan is now a Principal Researcher with Microsoft Research Labs, India. He has been on the faculty at MIT, CMU and lastly was the William Lanman Professor of Computer Science and Applied Mathematics at Yale University. He was awarded the Fulkerson Prize in Discrete Mathematics and the Distinguished Alumni award of the Indian Institute of Technology, Bombay.