************************** Special Time/Date **************************

             Department of Systems Engineering and Engineering Management
                                  The Chinese University of Hong Kong


Title : Theory of Semidefinite Programming for Euclidean Distance Geometry Problems
Speaker : Mr. Anthony Man-Cho So
    Stanford University
Date : February 13th, 2007 (Tuesday)
Time : 12:00 noon - 13:00 p.m.
Venue : Room 513, MMW Engineering Building
    (Engineering Building Complex Phase 2)



It is a trivial matter to see that given the coordinates of n points in R^d, the distance between any two points can be computed efficiently. However, the inverse problem --- given a subset of interpoint distances, find the coordinates of points (called a realization) in R^d (where d is fixed) that fit those distances --- turns out to be anything but trivial. This problem arises from many applications, e.g., sensor network localization and molecular conformation. Part of the difficulty comes from the facts that the realization must lie in an d--dimensional space, and that there may not be a unique realization. Many heuristics have been proposed for this problem. However, they either do not have any theoretical guarantees, or they work only for some very restricted classes of instances.

In this talk, I will introduce a semidefinite programming (SDP) based model for the problem and discuss its theoretical properties. In particular, I will show how the SDP model can be used to find a realization in the required dimension if the input instance satisfies certain uniqueness properties. Besides identifying a large class of polynomial-time realizable instances, our result has interesting implications in the rigidity theory of graphs. I will also discuss a connection between our SDP model and the theory of tensegrities in discrete geometry, and show how SDP theories can be used to provide constructive proofs for results in the latter area.



Anthony Man-Cho So is a PhD candidate in the Computer Science Department at Stanford University, working under the supervision of Professor Yinyu Ye. He received a Master of Science degree in computer science from Stanford University, and a Bachelor of Science in Engineering degree in computer science with minors in Applied and Computational Mathematics, Engineering and Management Systems, and German Language and Culture from Princeton University. His current research focuses on the interplay between optimization theory and various areas of algorithm design, such as computational geometry, stochastic optimization, combinatorial optimization, and algorithmic game theory.

************************* ALL ARE WELCOME ************************

Host : Professor Li, Duan
Tel : (852) 2609-8323
Email : dli@se.cuhk.edu.hk
Enquiries : Bolin Ding or Jeffrey Xu Yu
  : Department of Systems Engineering and Engineering Management
Website : http://www.se.cuhk.edu.hk/~seg5810
Email : seg5810@se.cuhk.edu.hk