来客网

清华三篇FOCS 大放异彩:Nash均衡点是PPAD完全的!

声明:本文转载自 「科技时空」, 或因排版与篇幅原因进行过编辑,内容未经本站独立核实,不代表本站立场、观点或建议。 如涉及版权问题,请联系我们,核实后立即删除。 [ 免责声明 ]

FOCS是和STOC并列的计算机理论界的最高会议, 我亲耳听过一位very well-known computer scientist抱怨,要进STOC/FOCS太难了,因为必须迎合那些giants(指谁?呵呵,那就不方便说了)的口味。另外,我查过几位ACM fellows的publications,似乎STOC+FOCS一般不会超过10篇,可见这两个会议有多难进。

FOCS 2006 accepted papers:

Computing Nash Equilibria: Approximation and Smoothed Complexity

|by Xi Chen, Xiaotie Deng and Shang-Hua Teng

On the Quantum Query Complexity of Local Search in Two and Three Dimensions

|by Xiaoming Sun and Andrew C. Yao

Settling the Complexity of 2-Player Nash-Equilibrium

|by Xi Chen and Xiaotie Deng

陈汐:清华计算机系博士生, 男,1982年3月出生于吴江平望镇,九七届桃源中学毕业生。96年获江苏省数学竞赛一等奖;97年荣获全国数学竞赛一等奖,同年考入国家理科实验班清华大学附中。2005年12月,陈汐与邓小铁教授合作解决了计算机科学理论中一个著名难题-二人博弈的复杂性问题,他们证明了二人博弈问题的Nash均衡点的复杂性是PPAD完全的。陈汐的工作是与邓小铁合作的。陈汐去年曾经中过一篇STOC。

孙晓明,清华高研中心副教授,是姚先生在清华的第一个博士毕业生。

评论 (0)