http://focs06.cs.princeton.edu/program.pdf
Bets Paper Award: （最佳论文奖）Settling the Complexity of 2-Player Nash-Equilibrium
by Xi Chen and Xiaotie Deng
Best Student Paper Award: （最佳学生论文奖）Algebraic Structures and Algorithms for Matching and Matroid Problemsby Nicholas J. A. Harvey
陈汐的两篇论文被理论计算机界最著名的会议FOCS 2006录用，一篇论文获得FOCS 2006最佳论文奖。陈汐同学是张钹老师的博士研究生，跟随姚期智讲席教授组一起工作，他的另一篇论文去年曾经被理论计算机届另一个著名的会议STOC录用。
陈汐：清华计算机系博士生, 男，1982年3月出生于吴江平望镇，九七届桃源中学毕业生。96年获江苏省数学竞赛一等奖；97年荣获全国数学竞赛一等奖，同年考入国家理科实验班清华大学附中。2005年12月，陈汐与邓小铁教授合作解决了计算机科学理论中一个著名难题-二人博弈的复杂性问题，他们证明了二人博弈问题的Nash均衡点的复杂性是PPAD完全的。陈汐的工作是与邓小铁合作的。陈汐去年曾经中过一篇STOC。
智能实验室去年毕业的博士生、现在清华大学高研中心工作的孙晓明博士的一篇论文也同时被FOCS 2006录用。孙晓明，清华高研中心副教授，是姚先生在清华的第一个博士毕业生。在此之前已经在Algorithmica、IEEE Transactions onInformation Theory等期刊上发表论文。
STOC和FOCS是理论计算机科学界最著名的两个国际会议，在该会议上同时有三篇论文录用，标志着智能实验室在理论计算机科学领域的研究中，进入了一个新的台阶。
有人说，能在STOC/FOCS上发一篇论文就已经是超牛了。获得最佳论文奖，就不能用牛说了，只能说是“犇”了。
呵呵。
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-Equilibriumby Xi Chen and Xiaotie Deng
评论 (0)