Seminar on Sep. 14, 2011

Date: Wednesday, September 14, 2011.


Math Building, Room 201,

Software Engineering Institute,

East China Normal University,

Zhongshan North Road 3663#, Putuo, Shanghai.


11:00 am - 11:50 am

Title: Shortest paths among obstacles in the plane

Speaker: Haitao Wang (王海涛) (University of Notre Dame, USA)


Given a set of obstacles and two points s and t in the plane, a fundamental problem in computational geometry is to find a shortest path from s to t that avoids the obstacles. The problem has been studied extensively. Various versions of this problem has been considered. We give efficient algorithms for the following two versions. The first version is the L1 polygonal version where all obstacles are polygonal and the length of a path is measured by L1 metric. The second version is the Euclidean curved version where the obstacles may have curved boundaries and the length of a path is measured by Euclidean metric.


Haitao Wang received his Ph.D in Computer Science from University of Notre Dame, Indiana, USA, in May 2010. Since then, he has been a Research Assistant Professor in Department of Computer Science and Engineering at the University of Notre Dame. His research focuses on algorithm design and analysis in computational geometry.


1:30 pm - 2:10 pm

Title: Studies on algorithmic mechanism design by using complex numbers

Speaker: Dr Haoyang Wu ( Shanghai Tenly Software Co. )


The Maskin's theorem for Nash implementation is a fundamental work in the theory of mechanism design. A recent work [Wu, Quantum mechanism helps agents combat ``bad'' social choice rules. Intl. J. of Quantum Information 9 (2011) 615-623] shows that when an additional condition is satisfied, the Maskin's theorem will not hold if agents use quantum strategies. Although quantum mechanisms are theoretically feasible, they are not applicable immediately due to the restriction of current experimental technologies. In this paper, we will go beyond the obstacle of how to realize quantum mechanisms, and propose an algorithmic mechanism which amends the sufficient conditions of the Maskin's theorem immediately just in the macro world (i.e., computer or Internet world).

Biography: 吴浩扬博士1999年博士毕业于西安交通大学,2002年清华大学博士后,现为上海天律信息技术有限公司副总经理。研究兴趣包括量子计算、博弈论、机制设计等。


2:20 pm - 3:10 pm

Title: Arithmetic operators over regular languages

Speaker: Boru Gong ( Fudan University )


Regular language is a classic topic in theory of computation. Here some of its new features are introduced and discussed.

Biography: Gong Boru is a graduate student in Theory group, Fudan University, with research interest focusing on graph theory and computational complexity.


3:20 pm - 4:00 pm

Title: Some complexity problems on binary strings

Speaker: Peng Zhang ( East China Normal University )


In the paper, we study a basic question: given a set of binary strings and several binary operations like disjunction and conjunction, which new binary strings can be generated? And three problems related to this question are studied. They are: No.1, If we are only allowed to use at most k strings from the set W, then both problems are NP-complete. No.2, Counting the number of strings generated from W by operators disjunction and conjunction is #P-complete. No.3, We try to find from W, the maximum expressible independent set among which each string cannot be generated from the others. We show this problem is NP-hard. Finally, we considered if negation is allowed as well as disjunction and conjunction, how the above four problems changed?