邓小铁

姓  名:
邓小铁
职  称:
讲席教授
研究领域:
大数据算法、算法博弈论、互联网经济学、在线算法
通信地址:
静园五院202-3
电子邮件:
xiaotie [at] pku.edu.cn

 

  邓小铁,1982年于清华大学获得学士学位,1984年于中国科学院获得硕士学位,1989年于斯坦福大学获得博士学位。1984-1985年,任中国科学院系统科学研究所助理研究员;1991-1999年任加拿大约克大学计算机科学与工程系助理教授、副教授;1997-2012年任香港城市大学计算机科学与工程系副教授、教授、讲席教授,同时,于2010年-2012年兼任英国利物浦大学计算机科学与工程系讲席教授;2012-2017年任上海交通大学计算机科学与工程系讲席教授;2017年12月入职北京大学,任信息科学技术学院前沿计算研究中心讲席教授。

 

  邓小铁教授的主要科研方向为算法及博弈论、互联网经济、在线算法,及并行计算。2008年,他因在博弈论算法的贡献获选ACM Fellow。邓小铁教授近期的研究兴趣包括算法博弈论研究、均衡和机制设计、互联网广告系统、云计算定价及资源分配、社交网络行为分析及推荐系统,以及交通及物流网络算法。作为项目负责人,他曾承担十几项加拿大、香港、英国,及国家基金委科研项目,并担任多种国际期刊编委。他曾担任多个国际学术会议主席,并发起网络经济学国际三大洲(亚洲欧洲美洲)循环举办的全球性会议互联网及网络经济学术会议The Conference on Web and Internet Economics (WINE)。他在算法博弈论方面及网络搜索的研究成果,被国际同行广泛引用,发表论文200余篇,被引用数千次;多次做国际学术会议特邀报告;曾获得IEEE理论计算机学术会议FOCS的最佳论文奖;其成果“关于图与组合优化的若⼲经典问题的研究”获2015年度⾼等学校科学研究优秀成果奖 (⾃然科学)二等奖(排名第⼆)。应用方面获得多项美国专利及国家专利,曾担任主要互联网公司机制设计顾问。

  

科研兴趣

  大数据算法、算法博弈论、互联网经济学、在线算法

  

主要学术贡献

  邓小铁教授科研重心集中在算法与博弈交互领域上,并有多项突出的原创性和重要成果。1986年开创性地探讨合作博弈合理性地算法复杂性基础。此后将算法复杂性原理推广到管理结构扁平化,金融套利,市场均衡。在互联网时代产生更深程度地学科交融地今天,邓小铁教授的研究兴趣在于计算机科学的角度对互联网经济学进行深入的研究,获得了相关领域内广泛的国际认同。2005年创立互联网经济学国际研讨会,历经十三年,已经成为国际互联网经济学重要会议。在互联网经济学中确认参与者的前瞻最优策略,跨平台套利均衡,市场均衡博弈收敛解,获得互联网经济模式设计多项专利,并历任国际国内互联网经济关键企业机制设计顾问(包括百度和微软)。2008年因在算法与博弈论交互发展方面的贡献,当选计算机协会会士(ACM Fellow)。

  

  在算法与复杂性领域,邓小铁教授取得许多在线算法成长初期的开拓性成果,包括网络搜索及几何搜索算法,在线问题的随机算法分析,并行及分布系统在线调度。在不动点算法设计及分析的研究方向上,取得oracle模型及电路计算模型的精确复杂性结果,以及二人博弈NASH均衡PPAD完全性证明,并在最近证明莫比斯带上不动点计算是PPA完全类。在不同的算法设计及分析方面,研究环路去见图判定、3D凸包并行算法、竞赛反馈点集TDI特性刻划及算法,网络流博弈的核计算。更多算法应用研究:中文分词的Accessor变数分析、体育竞赛策略机制设计、CPU时间均衡定价、群体决策最优摊余成本代价。

  

  邓小铁教授致力于大数据时代算法的理论和应用以及与大量参与者交互作用的原理及优化,研究工作包括互联网经济中最优拍卖算法,平台竞争分析,互联网中性原则,区块链技术应用,生物3D重构和材料基因组中深度机器学习方法。

 

Selected publications

Algorithmic Game Theory

  • Xiaotie Deng, Christos H. Papadimitriou:
    On the complexity of cooperative solution conceptsMathematics of Operations Research, 19(2): 257-266 (1994).
  • Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi:
    Algorithmic aspects of the core of combinatorial optimization games, Mathematics of Operations Research, 24(3): 751-766 (1999).
  • Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi, Wenan Zang:
    Totally balanced combinatorial optimization gamesMathematical Programming, 87(3): 441-452 (2000).

 

Equilibrium Computation

  • Xi Chen, Xiaotie Deng:
    Settling the complexity of two-player Nash equilibriumFOCS 2006 : 261-272.
    Journal version in JACM 2009, with X. Chen and S. Teng.
  • Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
    On the complexity of equilibria, STOC 2002: 67-71.
  • Tian-Ming Bu, Xiaotie Deng, Qi Qi:
    Arbitrage opportunities across sponsored search marketsTheoretical Computer Science, 407(1-3): 182-191 (2008).
  • Tian-Ming Bu, Xiaotie Deng, Qi Qi:
    Forward looking Nash equilibrium for keyword auctionInformation Processing Letters, 105(2): 41-46 (2008).
  • Xiaotie Deng, Qi Qi, Amin Saberi:
    Algorithmic solutions for envy-free cake cuttingOperations Research, 60(6): 1461-1476 (2012).
  • Xiaotie Deng, Jianping Wang, Juntao Wang:
    How to Design a Common Telecom Infrastructure for Competitors to be Individually Rational and Collectively OptimalIEEE Journal on Selected Areas in Communications (IEEE-JSAC), 35(3): 736-750 (2017).
  • Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou:
    Power-Law Distributions in a Two-Sided Market and Net NeutralityWINE 2016 : 59-72.

 

Incentive Analysis in Market Equilibrium

  • Yukun Cheng, Xiaotie Deng, Yifan Pi, Xiang Yan:
    Can Bandwidth Sharing Be Truthful? SAGT 2015 : 190-202.
  • Ning Chen, Xiaotie Deng, Bo Tang, Hongyang Zhang:
    Incentives for Strategic Behavior in Fisher Market Games, AAAI 2016 : 453-459.
  • Yukun Cheng, Xiaotie Deng, Qi Qi, Xiang Yan:
    Truthfulness of a Proportional Sharing Mechanism in Resource Exchange, IJCAI 2016 : 187-193.

 

Fixed point computation

  • Xi Chen, Xiaotie Deng:
    Matching algorithmic bounds for finding a Brouwer fixed pointJournal of the ACM (JACM), 55(3): 13:1-26 (2008).
  • Xiaotie Deng, Qi Qi, Amin Saberi, Jie Zhang:
    Discrete fixed points: Models, complexities, and applicationsMathematics of Operations Research, 36(4): 636-652 (2011).
  • Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu:
    Understanding PPA-completenessConference on Computational Complexity 2016 : 23:1-25.

 

Approximate Computing under Incomplete Information 

  • Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou:
    How to learn an unknown environment I: the rectilinear case, Journal of the ACM (JACM), 45(2): 215-245 (1998). 
  • Xiaotie Deng, Christos H. Papadimitriou:
    Exploring an unknown graph, Journal of Graph Theory, 32(3): 265-297 (1999). 
  • Xiaotie Deng, Andranik Mirzaian:
    Competitive robot mapping with homogeneous markersIEEE Transactions on Robotics and Automation, 12(4): 532-542 (1996).

 

Multi-Agent Protocols

  • Amotz Bar-Noy, Xiaotie Deng, Juan A. Garay, Tiko Kameda:
    Optimal amortized distributed consensusInformation and Computation, 120(1): 93-100 (1995).
  • Xiaotie Deng, Sanjeev Mahajan:
    Infinite games: randomization, computability, and applications to online problems, STOC 1991 : 289-298.
  • Anthony Y. Fu, Liu Wenyin, Xiaotie Deng:
    Detecting phishing web pages with visual similarity assessment based on earth mover's distance (EMD), IEEE Transactions on Dependable and Secure Computing (IEEE-TDSC), 3(4): 301-311 (2006).
  • Guomin Yang, Duncan S. Wong, Xiaotie Deng:
    Anonymous and authenticated key exchange for roaming networksIEEE Transactions on Wireless Communications (IEEE-TWC), 6(9): 3461-3472 (2007).
  • Guomin Yang, Qiong Huang, Duncan S. Wong, Xiaotie Deng:
    Universal authentication protocols for anonymous wireless communications, IEEE Transactions on Wireless Communications (IEEE-TWC), 9(1): 168-174 (2010).

 

Parallel Algorithms

  • Frank K. H. A. Dehne, Xiaotie Deng, Patrick W. Dymond, Andreas Fabri, Ashfaq A. Khokhar:
    A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, SPAA 1995 : 27-33.
  • Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu:
    Preemptive scheduling of parallel jobs on multiprocessors, SIAM Journal on Computing, 30(1): 145-160 (2000).

 

Combinatorics

  • Xiaotie Deng, Pavol Hell, Jing Huang:
    Linear-time representation algorithms for proper circular arc graphs, SIAM Journal on Computing, 25(2): 390-403 (1996). 
  • Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, Lusheng Wang:
    Genetic design of drugs without side-effectsSIAM Journal on Computing, 32(4): 1073-1090 (2003).
  • Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
    A min-max theorem on feedback vertex setsMathematics of Operations Research, 27(2): 361-371 (2002).
  • Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
    An approximation algorithm for feedback vertex sets in tournaments, SIAM Journal on Computing, 30(6): 1993-2007 (2001).

 

Information Retrievals

  • Haodi Feng, Kang Chen, Xiaotie Deng, Weimin Zheng:
    Accessor variety criteria for Chinese word extractionComputational Linguistics, 30(1): 75-93 (2004).
  • Hung Chim, Xiaotie Deng:
    A new suffix tree similarity measure for document clustering, WWW 2007 : 121-130.
  • Jianfeng Si, Arjun Mukherjee, Bing Liu, Qing Li, Huayi Li, Xiaotie Deng:
    Exploiting topic based twitter sentiment for stock predictionACL (2) 2013 : 24-29.