| Title: | Holographic Reduction: Design Algorithms and Prove Hardness |
| Date: |
May 5, 2008 (Monday)
|
| Time: |
3:00 p.m. - 4:00 p.m.
|
| Venue: |
Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong, Shatin, N.T. |
| Speaker: |
Mr LU Pinyan
Institute for Theoretical Computer Science Tsinghua University China |
In this talk, I will give a general framework for dealing with some families of counting problems. The framework is based on holographic reduction, which is a many-to-many reduction introduced by Vailant.
In the first part of the talk, I will show how this reduction can be used to design polynomial time algorithms. And in the second part, I will show that this powerful reduction also provides a very generic method to prove hardness results. In particular, we are able to get dichotomy theorems for some families of counting problems.
This talk is based on joint work with Jin-Yi Cai and Mingji Xia.
BIOGRAPHY:
Mr. Pinyan Lu received his B.S. in computer science from Tsinghua University in 2005, and is currently a third year Ph.D. student at the Institute for Theoretical Computer Science (ITCS) of Tsinghua University. His advisor is Prof. Andrew C. Yao and he is also co-supervised by Prof. Jin-Yi Cai of the University of Wisconsin-Madison. His main research interests include computational complexity, design of algorithms and algorithmic game theory. His recent paper with Jin-Yi Cai on holographic algorithms won the best paper award at ICALP 2007.
Enquiries: Miss Temmy So at tel 2609 8444
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar