My Home Page

Before joining Liverpool in 2010, I taught at City University of Hong Kong and York University. I did my (NSERC international fellowship) postdoc at Simon Fraser University with Tiko Kameda and Pavel Hell, PhD at Stanford University with Christos Papadimitriou, MSc at Chinese Academy of Sciences with Yonjin Zhu, and B.Eng at Tsinghua University.

RESEARCH: My research focus is on Algorithmic Game Theory, which deals with computational issue on fundamental economic problems such as Nash equilibrium, resource pricing and allocation protocols such as auction and market equilibrium, as well as theory and practice in Internet market design. This methodology integrates Algorithms with micro- and macro-economics, information economics, and has become a powerful tool in our understanding of the Internet and the practice of e-Commerce.

TEACHING: I have taught most computer science classes in algorithm related topics. In addition, I designed and taught graduated courses in web search, Internet market protocols. I gave lectures in special topics at summer schools such as equilibrium computation at Fudan University, sponsored search auctions at Karlsruhe University, online algorithms at Zhejiang University. I also taught short courses in algorithms at visiting institutes such as Kyoto University, Peking University, Tsinghua University, and Xiamen University.

PROFESSIONAL ACTIVITIES:
I have been an ACM Fellow since 2008, an IFIP TC1 member since 2007.
I have been program committee members of major theory conferences such as COCOON, ESA, FSTTCS, ICALP, ISAAC, STOC, and algorithmic game theory related conferences: ACM-EC, SAGT, WINE.

· Xiaotie Deng, Yang Sun, Ming Yin, Yunhong Zhou: Mechanism Design for Multi-slot Ads Auction in Sponsored Search Markets. FAW 2010: 11-22

· Ning Chen, Xiaotie Deng: Envy-Free Pricing in Multi-item Markets. ICALP (2) 2010: 418-429

· Ning Chen, Xiaotie Deng, Arpita Ghosh: Competitive Equilibria in Matching Markets with Budgets CoRR abs/1004.2565: (2010)

· Jessie Wenhui Zou, Xiaotie Deng, Ming Li: Detecting Market Trends by Ignoring It, Some Days. J. UCS 16(5): 852-861 (2010)

· Xiaotie Deng, Qi Qi, Jie Zhang: Direction Preserving Zero Point Computing and Applications. WINE 2009: 410-421

· Xiaotie Deng, Qi Qi: Priority Right Auction for Komi Setting. WINE 2009: 521-528

· Xiaotie Deng, Qi Qi, Amin Saberi: On the Complexity of Envy-Free Cake Cutting CoRR abs/0907.1334: (2009)

· Xi Chen, Xiaotie Deng, Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3): (2009)

· Xi Chen, Xiaotie Deng: On the complexity of 2D discrete fixed point problem. Theor. Comput. Sci. 410(44): 4448-4456 (2009)

· Tian-Ming Bu, Xiaotie Deng, Qianya Lin, Qi Qi: Strategies in Dynamic Pari-Mutual Markets. WINE 2008: 138-153

· Mao-cheng Cai, Xiaotie Deng: Arbitrage in Frictional Foreign Exchange Market. Encyclopedia of Algorithms 2008

· Hung Chim, Xiaotie Deng: Efficient Phrase-Based Document Similarity for Clustering. IEEE Trans. Knowl. Data Eng. 20(9): 1217-1229 (2008)

· Tian-Ming Bu, Xiaotie Deng, Qi Qi: Forward looking Nash equilibrium for keyword auction. Inf. Process. Lett. 105(2): 41-46 (2008)

· Xiaotie Deng, Ye Du: The computation of approximate competitive equilibrium is PPAD-hard. Inf. Process. Lett. 108(6): 369-373 (2008)

· Xi Chen, Xiaotie Deng: Matching algorithmic bounds for finding a Brouwer fixed point. J. ACM 55(3): (2008)

· Tian-Ming Bu, Xiaotie Deng, Qi Qi: Arbitrage opportunities across sponsored search markets. Theor. Comput. Sci. 407(1-3): 182-191 (2008)

· Hung Chim, Xiaotie Deng: A new suffix tree similarity measure for document clustering. WWW 2007: 121-130

· Xiaotie Deng, Li-Sha Huang, Minming Li: On Walrasian Price of CPU Time. Algorithmica 48(2): 159-172 (2007)

· Xi Chen, Xiaotie Deng: Recent development in computational complexity characterization of Nash equilibrium. Computer Science Review 1(2): 88-99 (2007)

· Xi Chen, Xiaotie Deng: Settling the Complexity of Two-Player Nash Equilibrium. FOCS 2006: 261-272

· Anthony Y. Fu, Wan Zhang, Xiaotie Deng, Liu Wenyin: Safeguard against unicode attacks: generation and applications of UC-simlist. WWW 2006: 917-918

· Wenyin Liu, Xiaotie Deng, Guanglin Huang, Anthony Y. Fu: An Antiphishing Strategy Based on Visual Similarity Assessment. IEEE Internet Computing 10(2): 58-65 (2006)

· Anthony Y. Fu, Liu Wenyin, Xiaotie Deng: Detecting Phishing Web Pages with Visual Similarity Assessment Based on Earth Mover's Distance (EMD). IEEE Trans. Dependable Sec. Comput. 3(4): 301-311 (2006)

· Xi Chen, Xiaotie Deng: On algorithms for discrete and approximate brouwer fixed points. STOC 2005: 323-330

· Lihua Chen, Xiaotie Deng, Qizhi Fang, Feng Tian: Condorcet Winners for Public Goods. Annals OR 137(1): 229-242 (2005)

· Haodi Feng, Kang Chen, Xiaotie Deng, Weimin Zheng: Accessor Variety Criteria for Chinese Word Extraction. Computational Linguistics 30(1): 75-93 (2004)

· Weimin Zheng, Jiwu Shu, Yonggen Gu, Xiaotie Deng: Parallel Computing Method Of Valuing For Multi-Asset European Option. International Journal of Information Technology and Decision Making 3(4): 575-581 (2004)

· Xiaotie Deng, Guojun Li, Wenan Zang: Proof of Chv?tal's conjecture on maximal stable sets and maximal cliques in graphs. J. Comb. Theory, Ser. B 91(2): 301-325 (2004)

· Francis Y. L. Chin, Xiaotie Deng, Qizhi Fang, Shanfeng Zhu: Approximate and dynamic rank aggregation. Theor. Comput. Sci. 325(3): 409-424 (2004)

· Hung Chim, Xiaotie Deng, Jianping Li, Wuyi Yue: Channel Assignment in Wireless Mobile Networks with Frequency Interference Over Distance. Communications in Computing 2003: 195-199

· Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra: On the complexity of price equilibria. J. Comput. Syst. Sci. 67(2): 311-324 (2003)

· Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, Lusheng Wang: Genetic Design of Drugs Without Side-Effects. SIAM J. Comput. 32(4): 1073-1090 (2003)

· Kang Chen, Weimin Zheng, Xiaotie Deng, Haodi Feng, Shanfeng Zhu: Text Distinguishers Used in an Interactive Meta Search Engine. WAIM 2002: 181-188

· Xiaotie Deng, Zhongfei Li, Shouyang Wang: Computational Complexity of Arbitrage in Frictional Security Market. Int. J. Found. Comput. Sci. 13(5): 681-684 (2002)

· Mao-cheng Cai, Xiaotie Deng, Wenan Zang: A Min-Max Theorem on Feedback Vertex Sets. Math. Oper. Res. 27(2): 361-371 (2002)

· Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu: Preemptive Scheduling of Parallel Jobs on Multiprocessors. SIAM J. Comput. 30(1): 145-160 (2000)

· Xiaotie Deng, Elias Koutsoupias, Philip D. MacKenzie: Competitive Implementation of Parallel Programs. Algorithmica 23(1): 14-30 (1999)

· Mao-cheng Cai, Xiaotie Deng, Wenan Zang: A TDI System and its Application to Approximation Algorithms. FOCS 1998: 227-243

· Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou: How to Learn an Unknown Environment I: The Rectilinear Case. J. ACM 45(2): 215-245 (1998)

· Xiaotie Deng, Christos H. Papadimitriou: Decision-Making by Hierarchies of Discordant Agents. ISAAC 1997: 183-192

· Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi: Combinatorial Optimization Games. SODA 1997: 720-729

· Xiaotie Deng, Hai-Ning Liu, Junsheng Long, Bing Xiao: Competitive Analysis of Network Load Balancing. J. Parallel Distrib. Comput. 40(2): 162-172 (1997)

· Xiaotie Deng, Sanjeev Mahajan: The Cost of Derandomization: Computability or Competitiveness. SIAM J. Comput. 26(3): 786-802 (1997)

· Frank K. H. A. Dehne, Xiaotie Deng, Patrick W. Dymond, Andreas Fabri, Ashfaq A. Khokhar: A Randomized Parallel Three-Dimensional Convex Hull Algorithm for Coarse-Grained Multicomputers. Theory Comput. Syst. 30(6): 547-558 (1997) 1996

· Xiaotie Deng, Patrick W. Dymond: On Multiprocessor System Scheduling. SPAA 1996: 82-88

· Xiaotie Deng, Christos H. Papadimitriou: Competitive Distributed Decision-Making. Algorithmica 16(2): 133-150 (1996)

· Xiaotie Deng: Distributed Near-Optimal Matching. Combinatorica 16(4): 453-464 (1996)

· Xiaotie Deng: A Lower Bound for Communication in the Crossbar. Inf. Process. Lett. 57(2): 103-108 (1996)

· Xiaotie Deng, Pavol Hell, Jing Huang: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs. SIAM J. Comput. 25(2): 390-403 (1996)

· Xiaotie Deng, Juan A. Garay, Tiko Kameda: Optimal Amortized Distributed Consensus Inf. Comput. 120(1): 93-100 (1995)

· Xiaotie Deng, Elias Koutsoupias: Competitive Implementation of Parallel Programs. SODA 1993: 455-461

· Xiaotie Deng, Christos H. Papadimitriou: Exploring an Unknown Graph (Extended Abstract) FOCS 1990: 355-361

· Xiaotie Deng: An Optimal Parallel Algorithm for Linear Programming in the Plane. Inf. Process. Lett. 35(4): 213-217 (1990)