+86 (0)10 6276-9219

**xiaotie**

Room 202-2, Courtyard No.5, Jingyuan

Algorithmic Game Theory, Computational Economics, Blockchain, Combinatorics and Optimization### Bio-Sketch

Xiaotie Deng got his BSc from Tsinghua University, MSc from Chinese Academy of Sciences, and PhD from Stanford University in 1989.

He is currently a chair professor at Peking University. He taught in the past at Shanghai Jiaotong University, University of Liverpool, City University of Hong Kong, and York University. Before that, he was an NSERC international fellow at Simon Fraser University. Deng's current research focuses on algorithmic game theory, with applications to Internet Economics and Finance including sponsored search auction, p2p network’s economics such as BitTorrent network, sharing economics, and blockchain. His other works cover online algorithms, parallel algorithms, and combinatorial optimization.

He is an ACM fellow for his contribution to the interface of algorithms and game theory, and an IEEE Fellow for his contributions to computing in partial information and interactive environments.

### Publications

**Selected Papers in major journals/conferences**

- Xiaotie Deng ; Tao Xiao ; Keyu Zhu, Learn to Play Maximum Revenue Auction, IEEE Transaction on Cloud Computing 7(4), 1057-1067 (2019)
- Yukun Cheng, Xiaotie Deng, Dominik Scheder: Recent studies of agent incentives in Internet resource allocation and pricing. 4OR 16(3): 231-260 (2018)
- How to Design a Common Telecom Infrastructure for Competitors to be Individually Rational and Collectively Optimal. IEEE Journal on Selected Areas in Communications 35(3): 736-750 (2017)
- Xiaotie Deng, Qi Qi, Amin Saberi: Algorithmic Solutions for Envy-Free Cake Cutting. Operations Research 60(6): 1461-1476 (2012)
- X. Deng, Q. Qi, A. Saberi, J. Zhang, Discrete Fixed Points: Models, Complexities and Applications, Mathematics of Operations Research. Vol. 36, No. 4, 2011.
- Xi Chen, Xiaotie Deng, Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3): (2009)
- Deng XT, Huang LS, Li MM. On Walrasian price of CPU time, ALGORITHMICA 48 (2): 159-172 JUN 2007.
- Haodi Feng, Kang Chen, Xiaotie Deng, Weimin Zheng: Accessor Variety Criteria for Chinese Word Extraction. Computational Linguistics 30(1): 75-93 (2004).
- X. Deng, C. Papadimitriou, and S. Safra, On the Complexity of Price Equilibrium. Journal of Computer and System Sciences Volume 67, Issue 2 , September 2003 , Pages 311-324. A Special Issue on STOC 2002.
- Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. A Min-Max Theorem on Feedback Vertex Sets. Mathematics of Operations Research Vol. 27 No.2, pp.361-371, May 2002.
- Shunming Zhang, Chunlei Xu, Xiaotie Deng. Dynamic Arbitrage-free Asset Pricing with Proportional Transaction Costs. Mathematical Finance, vol. 12, No. 1, pp.1-9, January, 2002.
- Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. An Approximation Algorithms for Feedback Vertex Sets in Tournaments. SIAM Journal on Computing, Vol. 30, No.6, pp. 1993 – 2007, 2001.
- Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu: Preemptive Scheduling of Parallel Jobs on Multiprocessors. SIAM J. Comput. 30(1): 145-160 June 2000. (P)
- Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi, Wenan Zang. Totally balanced combinatorial optimization games, Math. Program. 87 (May 2000) 3, 441-452.
- X. Deng and C.H. Papadimitriou. Decision making by Hierarchies of Discordant Agents. Mathematical Programming 86(2), pp.417-431, November 1999.
- Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi. Algorithms Aspects of Combinatorial Optimization Games. Mathematics of Operations Research, Vol. 24(3), pp.751-766, 1999.
- X. Deng, E. Koutsoupias and P. McKenzie. Competitive Implementation of Parallel Programs. Algorithmica, Vol. 23 No.1, 1999, pp.14-30.
- Xiaotie Deng, Tiko Kameda, and Christos Papadimitriou. How to Learn an Unknown Environment I: The Rectilinear Case. Journal of the ACM, Vol. 45, No.2, 1998, pp. 215-245.
- X. Deng and S. Mahajan. The Cost of Derandomization: Computability or Competitiveness. SIAM J. Comput., Vol. 26, No. 3, June, 1997, pp.786-802.
- X. Deng, P. Hell and J. Huang. Linear Time Representation Algorithms for Proper Circular Arc Graphs and Proper Interval Graphs. SIAM J. Computing, Vol. 25, No.2, (1996), pp.390—403.
- X. Deng and A. Mirzaian . Competitive Robot Mapping with Homogeneous Markers. IEEE transactions on Robotics and Automation, Vol. 12, No.4, (1996), pp. 532—542.
- X. Deng and C. Papadimitriou. On the Complexity of Cooperative Game Solution Concepts. Mathematics of Operations Research, Vol. 19, No. 2 (1994), pp. 257—266.
- Chenchen Li, Xiang Yan, Xiaotie Deng, Yuan Qi, Wei Chu, Le Song, Junlong Qiao, Jianshan He, Junwu Xiong: Latent Dirichlet Allocation for Internet Price War. AAAI 2019: 639-646.
- Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu: Understanding PPA-Completeness. Conference on Computational Complexity 2016: 23:1-23:25
- Yukun Cheng, Xiaotie Deng, Qi Qi, Xiang Yan: Truthfulness of a Proportional Sharing Mechanism in Resource Exchange. IJCAI 2016: 187-193
- Juntao Wang, Xun Xiao, Jianping Wang, Kejie Lu, Xiaotie Deng, Ashwin Gumaste: When group-buying meets cloud computing. INFOCOM 2016: 1-9
- Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou: Power-Law Distributions in a Two-Sided Market and Net Neutrality. WINE 2016: 59-72
- Xiaotie Deng, Jianping Wang, Juntao Wang: How to design a common telecom infrastructure by competitors individually rational and collectively optimal. INFOCOM Workshops 2015: 552-557
- Yukun Cheng, Xiaotie Deng, Yifan Pi, Xiang Yan: Can Bandwidth Sharing Be Truthful? SAGT 2015: 190-202
- Simina Brânzei, Yiling Chen, Xiaotie Deng, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang: The Fisher Market Game: Equilibrium and Welfare. AAAI 2014: 587-593
- Ning Chen, Xiaotie Deng, Jie Zhang: How Profitable Are Strategic Behaviors in a Market? ESA 2011: 106-118
- Xiaodong Li, Chao Wang, Jiawei Dong, Feng Wang, Xiaotie Deng, Shanfeng Zhu: Improving Stock Market Prediction by Integrating Both Market News and Stock Prices. DEXA (2) 2011: 279-293

**FULL LIST OF PUBLICATION (Xiaotie Deng)**

Summary 282

Books 6 Chapters in Books: 12 Papers in referred journals: 126 Other referred contributions: 132

(Most conference papers have later been modified and improved to appear in

refereed international journals.) Non—referred contribution: 6

Books (edited)

1. Xiaotie Deng:

Algorithmic Game Theory - 11th International Symposium, SAGT 2018, Beijing, China, Sep- tember 11-14, 2018, Proceedings. Lecture Notes in Computer Science 11059, Springer 2018, ISBN 978-3-319-99659-2.

2. Yijia Chen, Xiaotie Deng, Mei Lu:

Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Sanya, China, April 29 - May 3, 2019, Proceedings. Lecture Notes in Computer Science 11458, Springer 2019, ISBN 978-3-030-18125-3

3. Xiaotie Deng, John E. Hopcroft, Jinyun Xue: Frontiers in Algorithmics, Third International Workshop, FAW 2009, Hefei, China, June 20-23, 2009. Proceedings Springer 2009

4. Xiaotie Deng and Fan Chung Graham, Internet and Network Economics, Third International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Proceedings Springer 2007.

5. Xiaotie Deng, Ding-Zhu Du: Algorithms and Computation, 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings Springer 2005.

6. Xiaotie Deng, Yinyu Ye: Internet and Network Economics, First International Workshop, WINE

2005, Hong Kong, China, December 15-17, 2005, Proceedings Springer 2005.

Chapters in books

7. Xiaotie Deng: Combinatorial Optimization Games. Encyclopedia of Optimization 2009: 387-391

8. Xiaotie Deng: Competitive Ratio for Portfolio Management. Encyclopedia of Optimization 2009: 401-405

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

10. Xi Chen, Xiaotie Deng: Complexity of Bimatrix Nash Equilibria. Encyclopedia of Algorithms 2008

11. Xi Chen, Xiaotie Deng: Incentive Compatible Selection. Encyclopedia of Algorithms 2008

12. Xi Chen, Xiaotie Deng: Non-approximability of Bimatrix Nash Equilibria. Encyclopedia of Al-

gorithms 2008

13. Shanfeng Zhu, Xiaotie Deng, Qizhi Fang, Weimin Zheng, A Study on Web Searching: Overlap

and Distance of the Search Engine Results. In Intelligent Agents for Data Mining and Informa-

tion Retrieval, pp.208-225, edited by M. Mohammadian, Idea Group Publishing, 2004.

14. X. Deng. Randomized Geometry Algorithms for Coarse Grained Parallel Computers. Handbook on Randomized Computing, 203-220, Sanguthevar Rajasekaran, Panos Pardalos, John Reif and

Jose Rolim (Eds.). Kluwer Academic Publishers, 2001.

15. Xiaotie Deng. Complexity issues in bilevel linear programming. Multilevel optimization: algo- rithms and applications, 149164, Nonconvex Optim. Appl., 20, Kluwer Acad. Publ., Dordrecht, 1998.

16. X. Deng. Combinatorial Optimization and Coalition Games. Handbook of Combinatorial Optimization. Handbook of combinatorial optimization, Vol. 2, 77--103, D. Du, and P.M. Pardalos (Eds.) KluwerAcad.Publ.,Boston,MA,1998.

17. P.M. Pardalos, and X. Deng. Complexity issues in hierarchical optimization. Mathematical hi- erarchies and biology (Piscataway, NJ, 1996), 219224, B. Mirkin, F.R. McMorris, F.S. Roberts, and A. Rzhetsky (Eds.) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 37, Amer. Math. Soc., Providence, RI, 1997.

18. Yong Jin Zhu, Feng Tian, Xiaotie Deng. Further consideration on the BondyChvátal’s closure theorems. Graph theory, combinatorics, algorithms, and applications (San Francisco, CA, 1989), 518524, SIAM, Philadelphia, PA, 1991.

Papers in referred journals

1. Eleftherios Anastasiadis, Xiaotie Deng, Piotr Krysta, Minming Li, Han Qiao, Jinshan Zhang. Network Pol- lution Games. Algorithmica 81(1): 124-166 (2019)

2. Zhou Chen, Yucheng Cheng, Xiaotie Deng, Qi Qi, Xiang Yan. Agent incentives of strategic behavior in resource exchange. Discrete Applied Mathematics 264: 15-25(2019).

3. Xiaotie Deng ; Tao Xiao ; Keyu Zhu, Learn to Play Maximum Revenue Auction, IEEE Transaction on Cloud Computing 7(4), 1057-1067 (2019)

4. Yukun Cheng, Xiaotie Deng, Dominik Scheder: Recent studies of agent incentives in Internet resource allocation and pricing. 4OR 16(3): 231-260 (2018)

5. Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang, Jinshan Zhang, Pricing ad slots with consecutive multi-unit demand. Autonomous Agents and Multi-Agent Systems 31(3): 584-605 (2017).

6. Xiaotie Deng, Jianping Wang, Juntao Wang:

How to Design a Common Telecom Infrastructure for Competitors to be Individually Rational and Collectively Optimal. IEEE Journal on Selected Areas in Communications 35(3): 736-750 (2017)

7. Xiaotie Deng, Paul W. Goldberg, Bo Tang, Jinshan Zhang:

Multi-Unit Bayesian Auction with Demand or Budget Constraints. Computational Intelligence 32(3): 355-368 (2016)

8. Ning Chen, Xiaotie Deng, Paul W. Goldberg, Jinshan Zhang:

On revenue maximization with sharp multi-unit demands. J. Comb. Optim. 31(3): 1174-1205 (2016)

9. Xiaodong Li, Haoran Xie, Ran Wang, Yi Cai, Jingjing Cao, Feng Wang, Huaqing Min, Xiaotie Deng: Empirical analysis: stock market prediction via extreme learning machine. Neural Computing and Ap- plications 27(1): 67-78 (2016)

10. Xiaodong Li, Haoran Xie, Li Chen, Jianping Wang, Xiaotie Deng:

News impact on stock price return via sentiment analysis. Knowl.-Based Syst. 69: 14-23 (2014)

11. Ning Chen, Xiaotie Deng:

Envy-free pricing in multi-item markets. ACM Trans. Algorithms 10(2): 7:1-7:15 (2014)

12. Xiaotie Deng, Paul W. Goldberg, Bo Tang, Jinshan Zhang:

Revenue maximization in a Bayesian double auction market. Theor. Comput. Sci. 539: 1-12 (2014)

13. Jianfeng Si, Qing Li, Tieyun Qian, Xiaotie Deng:

Users' interest grouping from online reviews based on topic frequency and order. World Wide Web 17(6): 1321-1342 (2014)

14. Yang Sun, Yunhong Zhou, Xiaotie Deng:

Optimal reserve prices in weighted GSP auctions. Electronic Commerce Research and Applications 13(3): 178-187 (2014)

15. Xiaodong Li, Xiaotie Deng, Shanfeng Zhu, Feng Wang, Haoran Xie:

An intelligent market making strategy in algorithmic trading. Frontiers of Computer Science 8(4): 596- 608 (2014)

16. Xiaodong Li, Xiaodi Huang, Xiaotie Deng, Shanfeng Zhu:

Enhancing quantitative intra-day stock return prediction by integrating both market news and stock prices information. Neurocomputing 142: 228-238 (2014)

17. Xiaotie Deng, Paul W. Goldberg, Bo Tang, Jinshan Zhang: Revenue maximization in a Bayesian double auction market. Theor. Comput. Sci. 539: 1-12 (2014)

18. Xiaotie Deng, Qi Qi, Amin Saberi: Algorithmic Solutions for Envy-Free Cake Cutting. Operations Research 60(6): 1461-1476 (2012)

19. Tian-Ming Bu, Xiaotie Deng, Qi Qi: Multi-bidding strategy in sponsored search auctions. J. Comb. Op- tim. 23(3): 356-372 (2012)

20. X. Deng, Q. Qi, A. Saberi, J. Zhang, Discrete Fixed Points: Models, Complexities and Applications, Mathematics of Operations Research. Vol. 36, No. 4, 2011.

17. Xi Chen, Xiaotie Deng, Becky Jie Liu: On Incentive Compatible Competitive Selection Protocols. Algo- rithmica 61(2): 447-462 (2011)

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

19. Guomin Yang, Qiong Huang, Duncan S. Wong, Xiaotie Deng: Universal authentication proto- cols for anonymous wireless communications. IEEE Transactions on Wireless Communications 9(1): 168-174 (2010)

20. Chung Ki Li, Guomin Yang, Duncan S. Wong, Xiaotie Deng, Sherman S. M. Chow: An efficient signcryption scheme with key privacy and its extension to ring signcryption. Journal of Com- puter Security 18(3): 451-473 (2010)

21. Xiaotie Deng, Qizhi Fang, Xiaoxun Sun: Finding nucleolus of flow game. J. Comb. Optim. 18(1): 64-86 (2009)

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

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

24. Xi Chen, Xiaotie Deng: A Simplicial Approach for Discrete Fixed Point Theorems. Algo- rithmica 53(2): 250-262 (2009)

25. Guojun Li, Xiaotie Deng, Ying Xu: A polynomial-time approximation scheme for embed- ding hypergraph in a cycle. ACM Transactions on Algorithms 5(2): (2009)

26. Feng Wang, Keren Dong, Xiaotie Deng: Algorithmic trading system: design and ap- plications. Frontiers of Computer Science in China 3(2): 235-246 (2009)

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

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

29. Hung Chim, Xiaotie Deng: Efficient Phrase-Based Document Similarity for Clustering. IEEE Transactions on Knowledge and Data Engineering, Volume 20, Issue 9, Sept. 2008 Page(s):1217 – 1229.

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

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

32. Guomin Yang, Duncan S. Wong, Huaxiong Wang, Xiaotie Deng: Two-factor mutual authenti- cation based on smart cards and passwords. J. Comput. Syst. Sci. 74(7): 1160-1172 (2008)

33. Yang GM, Duncan S. Wong, Deng XT , Formal security definition and efficient construction for roaming with a privacy-preserving extension. JOURNAL OF UNIVERSAL COMPUT- ER SCIENCE, Volume: 14, Issue: 3, pp.441-462, 2008.

34. Guomin Yang, Jing Chen, Duncan S. Wong, Xiaotie Deng, Dongsheng Wang: A new frame- work for the design and analysis of identity-based identification schemes. Theor. Comput. Sci. 407(1-3): 370-388 (2008)

35. Deng XT, Huang LS, Li MM. On Walrasian price of CPU time, ALGORITHMICA 48 (2): 159-172 JUN 2007.

36. Guomin Yang, Duncan S. Wong, Xiaotie Deng: Anonymous and Authenticated Key Ex- change for Roaming Networks. IEEE Transactions on Wireless Communications 6(9): 3461-3472 (2007).

37. Bessie C. Hu, Duncan S. Wong, Zhenfeng Zhang, Xiaotie Deng: Certificateless signature: a new security model and an improved generic construction. Des. Codes Cryptography 42(2): 109-126 (2007).

38. Li ZF, Yang H, Deng XT, Optimal dynamic portfolio selection with earnings-at-risk, JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, Volume: 132, Issue: 3: 459-473, MAR 2007.

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

40. Anthony Y. Fu, Liu Wenyin, Xiaotie Deng, Detecting Phising Web Pages with Visual Simi- larity Assessment Based on Earth Mover's Distance (EMD) IEEE Transactions on Depend- able and Secure Computing, Vol. 3, No.4, October-December 2006.

41. Cai MC, Deng XT, Li ZF. Computation of arbitrage in frictional bond markets. THEORET- ICAL COMPUTER SCIENCE 363 (3): 248-256 OCT 31 2006.

42. Li P, Chen HS, Deng XT, et al. On default correlation and pricing of collateralized debt obligation by copula functions. INTERNATIONAL JOURNAL OF INFORMATION TECH- NOLOGY & DECISION MAKING 5 (3): 483-493 SEP 2006

43. Liu GZ, Deng XT, Xu CQ. Partitioning series-parallel multigraphs into nu*-excluding edge covers. SCIENCE IN CHINA SERIES A-MATHEMATICS 49 (8): 1082-1093 AUG 2006

44. Anthony Y. Fu, Xiaotie Deng, Liu Wenyin, REGAP: A Tool for Unicode-based Web Identity

Fraud Detection. accepted to appear in Journal of Digital Forensic Practice (JDFP), (Special

Edition on Anti-phishing and Online Fraud), Published By: Taylor & Francis, 2006.

45. 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).

46. Deng XT, Huang LS: On the complexity of market equilibria with maximum social welfare, INFORMATION PROCESSING LETTERS 97 (1): 4-11 JAN 16 2006.

47. Deng XT, Gu YG, Wang SY, Zhang SM: On convergence of a semi-analytical method for American option pricing, JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS 313 (1): 353-365 JAN 1 2006.

48. Shu JW, Gu YG, Deng XT, Zheng WM: A sliced-finite difference method for the American option, IIE TRANSACTIONS 37 (10): 939-944 OCT 2005.

49. Chen LH, Deng XT, Fang QZ, TIAN F, Condorcet Winners for Public Goods, ANNALS OF OPERATIONS RESEARCH 137 (1-4): 229-242 2005.

50. X. Deng, Z. Li, and S. Wang. A Minimax Portfolio Selection Strategy with Equilibrium. European Journal of Operational Research, Vol. 166, Oct 2005, pp.278-292.

51. L. Chen, N. Chen, X. Deng and H. Zhu. Equilibrium Prices for Resource Allocation in Grid Computing, DYNAMICS OF CONTINUOUS, DISCRETE AND IMPULSIVE SYSTEMS B: Applications and Algorithms Volume 12, Number 4 (2005) pp. 607-616.

52. Xiaotie Deng, Zhongfei Li, Shouyang Wang, Hailiang Yang, Necessary and Sufficient Condi- tions for Weak No-Arbitrage in Securities Markets with Frictions, Annals of Operations Research 133, pp. 265-276, 2005.

53. Xiaotie Deng, Haodi Feng, Guojun Li, Benyun Shi: A PTAS for Semiconductor Burn-in Scheduling. J. Comb. Optim. 9(1): 5-17 (2005).

54. Ning Chen, Xiaotie Deng and Xiaoming Sun, On complexity of single-minded auction, Journal of Computer and System Sciences, Vol. 69, Issue 4, December 2004, pp. 675-687.

55. F.Y.L. Chin, Xiaotie Deng, Qizhi Fang, and Shanfeng Zhu, Approximate and dynamic rank aggregation. (P) Theoretical Computer Science Vol. 325, No. 3, pp.409-424, 2004.

56. Xiaotie Deng, Guojun Li, Wenan Zang. Proof of Chvatal's conjecture on maximal stable sets and maximal cliques in graphs. JOURNAL OF COMBINATORIAL THEORY SERIES B 91(2): 301-325 JUL 2004.

57. Jichang Dong, Helen S. Du, Shouyang Wang, Kang Chen and Xiaotie Deng. A framework of Web-based Decision Support Systems for portfolio selection with OLAP and PVM. Decision Support Systems, Volume 37, Issue 3, Pages 367-376 (June 2004).

58. Wuyi Yue, Koji Miyazaki, Xiaotie Deng: Optimal channel assignment in wireless communication networks with distance and frequency interferences. Computer Communications 27(16):1661-1669 (2004).

59. Yunlei Zhao, Xiaotie Deng, Chan H. Lee, Hong Zhu: (2+f(n))-SAT and its properties. Discrete Applied Mathematics 136 (1): 3-11 (2004).

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

61. Xiaotie Deng,Shouyang Wang: A Special Issue On "Computational Finance and Economics" Impact Of IT On Some Economics Problems. International Journal of Information Technology and Decision Making 3(4): 535-538 (2004).

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

63. Bo Chen, Xiaotie Deng, Wenan Zang. Online Scheduling a batch system to minimize total weighted job completion time. J COMB OPTIM 8 (1): 85-95 MAR 2004. (P)

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

65. M. Cai, X. Deng, and L. Wang. Minimum k Arborescences with Bandwidth Constraints. Algo- rithmica, Volume 38, Number 4, pp. 529 ?537, April 2004.

66. Xiaotie Deng, Haodi Feng, Pixin Zhang, Yuzhong Zhang, Hong Zhu. Minimizing Mean Com- pletion Time in Batch Processing System. Algorithmica Volume 38, Number 4, pp. 513 ?528, April 2004.

67. S. Zhang, S. Wang, X. Deng. Portfolio Selection Theory with Different Interest Rates for Bor- rowing and Lending. J GLOBAL OPTIM 28 (1): 67-95 JAN 2004.

68. X. Deng, C. Papadimitriou, and S. Safra, On the Complexity of Price Equilibrium. Journal of Computer and System Sciences Volume 67, Issue 2 , September 2003 , Pages 311-324. A Spe- cial Issue on STOC 2002.

69. X. Deng, C.K. Poon, and Y. Zhang. Approximation Algorithms in Batch Processing. Journal of Combinatorial Optimization, September 2003, Vol. 7, Issue 3, pp. 247-257.

70. *Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, Lusheng Wang: Genetic Design of Drug without Side-effect. SIAM Journal on Computing, Vol 32, No. 4, pp.1073-1090, July 2003.

71. Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng. Nonclairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics. Journal of Scheduling Vol. 6, May-June, pp. 231-250, 2003.

72. X. Deng, G. Li, W. Zang, Y. Zhou. A 2-Approximation Algorithm for Path Coloring on a Re- stricted Class of Trees of Rings. Journal of Algorithms, Vol. 47, pp.1-13, April 2003.

73. Fang QZ, Cai MC, Deng XT: Total balancedness condition for Steiner tree games, DISCRETE APPL MATH 127 (3): 555-563 MAY 1 2003.

74. Mao-cheng Cai, Xiaotie Deng: Arbitrage in Frictional Foreign Exchange Market. Electr. Notes Theor. Comput. Sci. 78: (2003). (P)

75. Mao-Cheng Cai, Xiaotie Deng, Lusheng Wang, Approximate Sequencing for Variable Length Tasks. THEOR COMPUT SCI 290 (3): 2037-2044 JAN 3 2003.

76. Xiaotie Deng, Haodi Feng, Guojun Li and Guizhen Liu. A PTAS for Minimizing Total Comple- tion Time of Bounded Batch Scheduling. International Journal of Foundations of Computer Sci- ence Vol. 13, No. 6 (December 2002), 817-827.

77. X. Deng, Z.F. Li, and S. Wang. Computational Complexity of Arbitrage in Frictional Security Market. International Journal of Foundations of Computer Science, Vol. 13, No.5, (October 2002), 681-684.

78. X.M. Yang, S.Y. Wang, and Xiaotie Deng. Symmetric Duality for a Class of Multiobjective Fractional Programming Problems. Journal of Mathematical Analysis and Applications 274 (October 2002), 279-295.

79. Qizhi Fang, Shanfeng Zhu, Maocheng Cai, Xiaotie Deng. On computational complexity of membership test in flow games and linear production games. Game Theory 31 (September 2002) 1, 39-45.

80. Xiaotie Deng, Guojun Li, Lusheng Wang. Center and Distinguisher for Strings with Unbounded Alphabet. J COMB OPTIM 6 (4): 383-400 DEC 2002.

81. Gu YG, Shu JW, Deng XT, ZHENG WM. A new numerical method on American option pric- ing. SCI CHINA SER F 45 (3): 181-188 JUN 2002.

82. Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. A Min-Max Theorem on Feedback Vertex Sets. Mathematics of Operations Research Vol. 27 No.2, pp.361-371, May 2002.

83. Shou Chen, Xiaotie Deng, Weiguo Liu, Shouyang Wang. Impact on the efficient frontier of portofolio of varying capital structure. Advanced Modeling and Optimization Vol. 4, No. 1, pp. 3-12, 2002.

84. Shunming Zhang, Chunlei Xu, Xiaotie Deng. Dynamic Arbitrage-free Asset Pricing with Pro- portional Transaction Costs. Mathematical Finance, vol. 12, No. 1, pp.1-9, January, 2002.

85. Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. An Approximation Algorithms for Feedback Vertex Sets in Tournaments. SIAM Journal on Computing, Vol. 30, No.6, pp. 1993 – 2007, 2001.

86. X. Deng, E. Milios, A. Mirzaian. Robot Map Verification of a Graph World. Journal of Combinatorial Optimization 5 (4): 383-395 DEC 2001.

87. Y. Xia, S. Wang, and X. Deng, A Compromise Solution to Mutual Funds Portfolio Selection with Transaction Costs. EUR J OPER RES 134 (3): 564-581 NOV 1 2001.

88. Pierluigi Crescenzi, Xiaotie Deng and Christos Papadimitriou. On Approximating a Scheduling Problem. JOURNAL OF COMBINATORIAL OPTIMIZATION 5 (3): 287-297 SEP 2001.

89. Z. Li, Z. Li, S. Wang, X. Deng. Optimal Portfolio Selection of Assets with Transaction Costs and No Short Sales. INT J SYST SCI 32 (5): 599-607 MAY 2001.

90. X. Deng, C.H. Lee and H. Zhu. Deniable authentication protocols. IEE Proceedings - Computers and Digital Techniques, March 2001, Vol. 148, Issue 2, p.101.

91. Patrick Dymond, Jieliang Zhou and Xiaotie Deng. A 2-D Parallel Convex Hull Algorithm with Optimal Communication Phases. Parallel Computing, 27 (3) (2001) pp. 243-255.

92. J. Zhou, P. Dymond, X.Deng. Graph Algorithms with Small Communication Costs. Journal of Combinatorial Optimization 4: (3) 291-305 SEP 2000.

93. Xiao-Tie Deng, Shou-Yang Wang and Yu-Sen Xia. Criteria, Models and Strategies in Portfolio Selection. Advanced Modelling and Optimization, Volume2, Number 2, pp.79-103, 2000.

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

95. X. Deng, G. Li, and W. Zang. Wavelength Allocation on Trees of Rings. Networks, Volume 35, Issue 4, pp. 248-252, July 2000.

96. M. Cai, X. Deng, and W. Zang. Solution to a Problem on Degree Sequence of Graphs. Discrete Mathematics 219, pp.253-257, May 2000.

97. Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi, Wenan Zang. Totally balanced combinatorial optimization games, Math. Program. 87 (May 2000) 3, 441-452.

98. Z.F. Li, S. Y. Wang, and X. Deng. A linear programming algorithm for optimal portfolio selec- tion with transaction costs. International Journal of Systems Science 31(1), pp.107-108, 2000.

99. X. Deng and P. Dymond. Randomized Optimal List Ranking on Coarse-grained Parallel Com- puters with O(log p) Communication Phases. Parallel Algorithms and Applications 14 (3), pp. 165-175, 2000.

100. X. Deng and C.H. Papadimitriou. Decision making by Hierarchies of Discordant Agents. Math- ematical Programming 86(2), pp.417-431, November 1999.

101. X. Deng, and C. Papadimitriou. Exploring an Unknown Graph. Journal of Graph Theory, Vol. 32, pp.265-297, 1999.

102. Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi. Algorithms Aspects of Combinatorial Optimization Games. Mathematics of Operations Research, Vol. 24(3), pp.751-766, 1999.

103. Huafei Zhu, Chan Lee, Xiaotie Deng. A Variation of Cramer-Shoup's Public Key Scheme. IEE Electronic Letters, Vol. 35(14), p.1150, July, 1999.

104. X. Deng and B. Zhu. A Randomized Algorithm for Voronoi Diagram of Line Segments on Coarse Grained Multiprocessors. Algorithmica Vol 24, No 3/4, pp. 270--286, 1999, a Special Issue on Coarse Grained Parallel Algorithms.

105. X. Deng, E. Koutsoupias and P. McKenzie. Competitive Implementation of Parallel Programs. Algorithmica, Vol. 23 No.1, 1999, pp.14-30.

106. Xiaotie Deng, Tiko Kameda, and Christos Papadimitriou. How to Learn an Unknown Environment I: The Rectilinear Case. Journal of the ACM, Vol. 45, No.2, 1998, pp. 215-245.

107. Xiaotie Deng and Patrick Dymond. On Multiprocessor System Scheduling. Journal of Combi- natorial Optimization, Vol. 1, 1998, pp. 377-392, a special issue on Scheduling on Parallel/Dis- tributed Systems. (P) (SCI impact factor 0.291, Rank 72 out of 83 in category Computer Science, Interdisciplanary)

108. F. Dehne, X. Deng, P. Dymond, A. Fabri, and A.~Khokhar. A Randomized Parallel 3D Convex

Hull Algorithm for Coarse Grained Multicomputers. Theory of Computing Systems, Vol. 30, 1997, pp. 547558, a special issue for selected papers presented at the 7th ACM Symposium on Parallel Algorithms and Architectures.

109. T. Brecht, X. Deng, and N. Gu. Competitive Dynamic Processor Allocation for Parallel Ap- plications. Parallel Processing Letters, Vol. 7, No. 1, 1997, pp. 89100. (P)

110. X. Deng and S. Mahajan. The Cost of Derandomization: Computability or Competitiveness. SIAM J. Comput., Vol. 26, No. 3, June, 1997, pp.786-802.

111. X. Deng, H. Liu, J. Long and B. Xiao. Competitive Analysis of Network Load Balancing. Jour- nal of Parallel and Distributed Computing, Vol. 40, No.2, (1997), pp.162-172.

112. X. Deng. Distributed NearOptimal Matching. Combinatorica, Vol. 16, No.4, (1996), pp.453— 464.

113. X. Deng, E. Milios, and A. Mirzaian. Landmark Selection Strategies for Path Execution. Robotics and Autonomous Systems, Vol. 17 (1996) pp. 171—185.

114. X. Deng, P. Hell and J. Huang. Linear Time Representation Algorithms for Proper Circular Arc Graphs and Proper Interval Graphs. SIAM J. Computing, Vol. 25, No.2, (1996), pp.390—403.

115. X. Deng and C. Papadimitriou. Competitive Distributed Decision—Making. Algorithmica, Vol. 16, No.2, (1996), pp.133—150.

116. X. Deng and A. Mirzaian . Competitive Robot Mapping with Homogeneous Markers. IEEE transactions on Robotics and Automation, Vol. 12, No.4, (1996), pp. 532—542.

117. X. Deng. A Lower Bound for Communication on Crossbar. Information Processing Letters, 57 (1996), 103—108.

118. BarNoy, X. Deng, J. Garay, T. Kameda. Optimal Amortized Distributed Consensus. Information and Computation, Vol. 120, No. 1 (1995), pp. 93—100.

119. X. Deng and C. Papadimitriou. On the Complexity of Cooperative Game Solution Concepts. Mathematics of Operations Research, Vol. 19, No. 2 (1994), pp. 257—266.

120. C.K. Chen, X. Deng, Y.Z. Liao, and S. Z. Yao. Compaction of Symbolic Layout under Bridge Rules. IEEE Trans. on CAD, Vol. 11, No.4, (1992), pp. 475—486.

121. X. Deng and S. Mahajan. Server Problems and Resistive Spaces. Information Processing Let- ters 37(1991), 193—196.

122. X. Deng and C. Papadimitriou. On Path Lengths Modulo Three. Journal of Graph Theory, 15(1991), pp. 267—282.

123. Y. Zhu, F. Tian and X. Deng. More Powerful Closure Operations on Graphs. Discrete Mathe- matics 87(1991), pp.197—214.

124. X. Deng. An Optimal Parallel Algorithm for Linear Programming in the Plane. Information Processing Letters 35(1990) 213—217.

125. Y. Zhu, H. Li and X. Deng. Implicit—degrees and circumstance. Graphs and Combinatorics 5(1989), pp.283—290.

126. F. Tian, R. Shi and X. Deng. Smallest Regular Graphs with Girth Pair (4,2t+1). Graphs and Combinatorics 1(1985), pp.201—202.

Other referred contributions:

127. Chenchen Li, Xiang Yan, Xiaotie Deng, Yuan Qi, Wei Chu, Le Song, Junlong Qiao, Jianshan He, Junwu Xiong: Latent Dirichlet Allocation for Internet Price War. AAAI 2019: 639-646

128. Yukun Cheng, Xiaotie Deng, Mengqian Zhang: A Novel Business Model for Electric Car Sharing. FAW 2019: 76-87

129. Xiang Yan, Fan Ye, Yuanyuan Yang, Xiaotie Deng: An autonomous compensation game to facilitate peer data exchange in crowdsensing. IWQoS 2017: 1-6

130. Chenchen Li, Xiaowei Li, Hongji Cao, He Jiang, Xiaotie Deng, Danny Z. Chen, Lin Yang, Zhifeng Shao: Fast Background Removal Method for 3D Multi-channel Deep Tissue Fluo- rescence Imaging. MICCAI (2) 2017: 92-99

131. Zhou Chen, Yukun Cheng, Xiaotie Deng, Qi Qi, Xiang Yan: Agent Incentives of Strategic Behavior in Resource Exchange. SAGT 2017: 227-239

132. Xiaotie Deng, Zhe Feng, Rucha Kulkarni: Octahedral Tucker is PPA-Complete. Electronic Colloquium on Computational Complexity (ECCC) 24: 118 (2017)

133. Ning Chen, Xiaotie Deng, Bo Tang, Hongyang Zhang: Incentives for Strategic Behavior in Fisher Market Games. AAAI 2016: 453-459

134. Eleftherios Anastasiadis, Xiaotie Deng, Piotr Krysta, Minming Li, Han Qiao, Jinshan Zhang: Network Pollution Games. AAMAS 2016: 23-31

135. Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu: Understanding PPA-Completeness. Conference on Computational Complexity 2016: 23:1-23:25

136. Eleftherios Anastasiadis, Xiaotie Deng, Piotr Krysta, Minming Li, Han Qiao, Jinshan Zhang: New Results for Network Pollution Games. COCOON 2016: 39-51

137. Min Zhang, Juntao Wang, Xiaotie Deng: Cost-Efficient Cooperative Sharing of a Complete Wi- Fi Signature Scheme for Indoor Localization in Shopping Malls. ICEBE 2016: 196-201

138. Yukun Cheng, Xiaotie Deng, Qi Qi, Xiang Yan: Truthfulness of a Proportional Sharing Mechanism in Resource Exchange. IJCAI 2016: 187-193

139. Juntao Wang, Xun Xiao, Jianping Wang, Kejie Lu, Xiaotie Deng, Ashwin Gumaste: When group-buying meets cloud computing. INFOCOM 2016: 1-9

140. Yu Chen, Xiaotie Deng, Ziwei Ji, Chao Liao: The Beachcombers' Problem: Walking and Searching from an Inner Point of a Line. LATA 2016: 270-282

141. Zhansheng Jiang, Lingxi Xie, Xiaotie Deng, Weiwei Xu, Jingdong Wang:Fast Nearest N eigh- bor Search in the Hamming Space. MMM (1) 2016: 325-336

142. Min Zhang, Ling Pei, Xiaotie Deng: GraphSLAM-based Crowdsourcing framework for indoor Wi-Fi fingerprinting. UPINLBS 2016: 61-67

143. Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou: Power-Law Distributions in a Two-Sided Market and Net Neutrality. WINE 2016: 59-72

144. Xiaotie Deng, Jianping Wang, Juntao Wang: How to design a common telecom infrastructure by competitors individually rational and col- lectively optimal. INFOCOM Workshops 2015: 552-557

145. Yukun Cheng, Xiaotie Deng, Yifan Pi, Xiang Yan: Can Bandwidth Sharing Be Truthful? SAGT 2015: 190-202

146. Simina Brânzei, Yiling Chen, Xiaotie Deng, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang: The Fisher Market Game: Equilibrium and Welfare. AAAI 2014: 587-593

147. Ning Chen, Xiaotie Deng: Computation and Incentives of Competitive Equilibria in a Matching Market. SAGT 2011: 2-6

148. Ning Chen, Xiaotie Deng, Jie Zhang: How Profitable Are Strategic Behaviors in a Market? ESA 2011: 106-118

149. Xiaodong Li, Chao Wang, Jiawei Dong, Feng Wang, Xiaotie Deng, Shanfeng Zhu: Improving Stock Market Prediction by Integrating Both Market News and Stock Prices. DEXA (2) 2011: 279-293

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

151. Xiaotie Deng, Qi Qi and Jie Zhang. Direction Preserving Zero Point Computing and Applications, WINE 2009.

152. Jiajin Yu and Xiaotie Deng. A New Ranking Scheme of the GSP Mechanism with Markovian Users.WINE 2009.

153. Xiaotie Deng and Qi Qi. Priority Right Auction for Komi Setting，WINE 2009.

154. Liu Wenyin, Anthony Y. Fu, Xiaotie Deng: Exposing Homograph Obfuscation Intentions by Coloring Unicode Strings, Progress in WWW Research and Development, 10th Asia-Pacific Web Conference, APWeb 2008, Shenyang, China, April 26-28, 2008. Proceedings. Lecture Notes in Computer Science 4976 Springer 2008: 275-286

155. Tian-Ming Bu, Xiaotie Deng and Qi Qi: Arbitrage Opportunities across Search Markets, Workshop on Targeting and Ranking for Online Advertising, WWW, April, 2008.

156. Tian-Ming Bu, Xiaotie Deng, Qianya Lin, Qi Qi: Strategies in Dynamic Pari-Mutual Markets. Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings. Lecture Notes in Computer Science 5385 Springer 2008: 138-153

157. Tian-Ming Bu, Xiaotie Deng, Qi Qi: Multi-bidding Strategy in Sponsored Keyword Auction. Frontiers in Algorithmics, Second Annual International Workshop, FAW 2008, Changsha, Chi- na, June 19-21, 2008, Proceeedings. Lecture Notes in Computer Science 5059: 124-134

158. Tian-Ming Bu, Xiaotie Deng, Qi Qi: Dynamics of Strategic Manipulation in Ad-Word Auction. SSA 2007.

159. Hung Chim, Xiaotie Deng: A new suffix tree similarity measure for document clustering. Pro- ceedings of the 16th International Conference on World Wide Web, WWW 2007, Banff, Alber- ta, Canada, May 8-12, 2007. ACM 2007: 121-130.

160. Bessie C. Hu, Duncan S. Wong, Qiong Huang, Guomin Yang, Xiaotie Deng: Time Capsule Sig- nature: Efficient and Provably Secure Constructions. Public Key Infrastructure, 4th European PKI Workshop: Theory and Practice, EuroPKI 2007, Palma de Mallorca, Spain, June 28-30, 2007, Proceedings. Lecture Notes in Computer Science 4582 Springer 2007: 126-142

161. Chung Ki Li, Guomin Yang, Duncan S. Wong, Xiaotie Deng, Sherman S. M. Chow: An Effi- cient Signcryption Scheme with Key Privacy. Public Key Infrastructure, 4th European PKI Workshop: Theory and Practice, EuroPKI 2007, Palma de Mallorca, Spain, June 28-30, 2007, Proceedings. Lecture Notes in Computer Science 4582 Springer 2007: 78-93

162. Guomin Yang, Jing Chen, Duncan S. Wong, Xiaotie Deng, Dongsheng Wang: A More Natural Way to Construct Identity-Based Identification Schemes. Applied Cryptography and Network Security, 5th International Conference, ACNS 2007, Zhuhai, China, June 5-8, 2007, Proceed- ings. Lecture Notes in Computer Science 4521 Springer 2007: 307-322.

163. Xiaotie Deng, Kazuo Iwama, Qi Qi, Aries Wei Sun, Toyotaka Tasaka: Properties of Symmetric Incentive Compatible Auctions. Computing and Combinatorics, 13th Annual International Con- ference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings. Lecture Notes in Computer Science 4598 Springer 2007: 264-273.

164. Xi Chen, Xiaotie Deng, Becky Jie Liu: On Incentive Compatible Competitive Selection Proto- col, Computing and Combinatorics, 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings. Lecture Notes in Computer Science 4112 Springer 2006: 13-22.

165. Xi Chen, Xiaotie Deng: A Simplicial Approach for Discrete Fixed Point Theorems. Computing and Combinatorics, 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings. Lecture Notes in Computer Science 4112 Springer 2006: 3-12

166. Xi Chen and Xiaotie Deng。 Settling the Complexity of 2-Player Nash-Equilibrium. 47th An- nual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. IEEE Computer Society 2006: 261-272. (The best paper award winner,)

167. Xi Chen, Xiaotie Deng and Shang-Hua Teng。 Computing Nash Equilibria: Approximation and

Smoothed Complexity。 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. IEEE Computer Society 2006: 603-612.

168. Xi Chen, Xiaotie Deng: Lattice Embedding of Direction-Preserving Correspondence over Inte- grally Convex Set. Algorithmic Aspects in Information and Management, Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006, Proceedings. Lecture Notes in Computer Science 4041 Springer 2006: 53-63

169. Bessie C. Hu, Duncan S. Wong, Zhenfeng Zhang, Xiaotie Deng: Key Replacement Attack Against a Generic Construction of Certificateless Signature. Information Security and Privacy, 11th Australasian Conference, ACISP 2006, Melbourne, Australia, July 3-5, 2006, Proceedings. Lecture Notes in Computer Science 4058 Springer 2006: 235-246

170. Xi Chen, Xiaotie Deng: On the Complexity of 2D Discrete Fixed Point Problem. Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I. Lecture Notes in Computer Science 4051 Springer 2006: 489- 500

171. Guomin Yang, Duncan S. Wong, Xiaotie Deng, Huaxiong Wang: Anonymous Signature Schemes. Public Key Cryptography 2006: 347-363

172. Xiaotie Deng, Qizhi Fang, Xiaoxun Sun: Finding nucleolus of flow game. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006. ACM Press 2006: 124-131.

173. Anthony Y. Fu, Wan Zhang, Xiaotie Deng, Liu Wenyin: Safeguard against unicode attacks: gen- eration and applications of UC-simlist. Proceedings of the 15th international conference on World Wide Web, WWW 2006, Edinburgh, Scotland, UK, May 23-26, 2006. ACM 2006: 917-918

174. Mao-cheng Cai, Xiaotie Deng, Zhongfei Li: Computation of Arbitrage in a Financial Market with Various Types of Frictions. Algorithmic Applications in Management, First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings. Lecture Notes in Com- puter Science 3521: 270-280

175. Guomin Yang, Duncan S. Wong, Xiaotie Deng: Deposit-Case Attack Against Secure Roaming. Information Security and Privacy, 10th Australasian Conference, ACISP 2005, Brisbane, Aus- tralia, July 4-6, 2005, Proceedings. Lecture Notes in Computer Science 3574: 417-428

176. Guomin Yang, Duncan S. Wong, Xiaotie Deng: Efficient Anonymous Roaming and Its Security Analysis. Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005, Proceedings. Lecture Notes in Computer Science 3531: 334-349

177. Xiaotie Deng, Li-Sha Huang, Minming Li: On Walrasian Price of CPU Time. Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, Au- gust 16-29, 2005, Proceedings. Lecture Notes in Computer Science 3595: 586-595

178. Hung Chim, Becky Jie Liu, Xiaotie Deng: A Group Decision Approach for Information As- sessment. Internet and Multimedia Systems and Applications, EuroIMSA 2005, Grindelwald, Switzerland, February 21-23, 2005: 7-12

179. Therese C. Biedl, Franz-Josef Brandenburg, Xiaotie Deng: Crossings and Permutations. Graph Drawing, 13th International Symposium, GD 2005, Limerick, Ireland, September 12-14, 2005, Revised Papers. Lecture Notes in Computer Science 3843: 1-12

180. Liu Wenyin, Guanglin Huang, Liu Xiaoyue, Xiaotie Deng, Zhang Min: Phishing Webpage De- tection. Eighth International Conference on Document Analysis and Recognition (ICDAR 2005), 29 August - 1 September 2005, Seoul, Korea. IEEE Computer Society 2005: 560-564

181. Guomin Yang, Duncan S. Wong, Xiaotie Deng: Analysis and Improvement of a Signcryption Scheme with Key Privacy. Information Security, 8th International Conference, ISC 2005, Sin- gapore, September 20-23, 2005, Proceedings. Lecture Notes in Computer Science 3650: 218-232

182. Xi Chen, Xiaotie Deng: On algorithms for discrete and approximate brouwer fixed points. Pro- ceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005. ACM 2005: 323-330

183. Anthony Fu, Xiaotie Deng, Wenyin Liu: A Potential IRI Based Phishing Strategy. Web Informa- tion Systems Engineering - WISE 2005, 6th International Conference on Web Information Sys- tems Engineering, New York, NY, USA, November 20-22, 2005, Proceedings. Lecture Notes in Computer Science 3806: 618-619

184. Liu Wenyin, Guanglin Huang, Liu Xiaoyue, Zhang Min, Xiaotie Deng: Detection of phishing webpages based on visual similarity. WWW (Special interest tracks and posters) 200Proceed- ings of the 14th international conference on World Wide Web, WWW 2005, Chiba, Japan, May 10-14, 2005 - Special interest tracks and posters. ACM 20055: 1060-1061

185. Ying Xu, Lusheng Wang, Xiaotie Deng: Exact Pattern Matching for RNA Secondary Structures. Second Asia-Pacific Bioinformatics Conference (APBC 2004), January 18-22, 2004, Dunedin, New Zealand. CRPIT 29 Australian Computer Society 2004: 257-263

186. Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao: Fisher Equilibrium Price with a Class of Concave Utility Functions. Algorithms - ESA 2004, 12th Annual European Sympo- sium, Bergen, Norway, September 14-17, 2004, Proceedings. Lecture Notes in Computer Sci- ence 3221: 169-179

187. Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao: Dynamic Price Sequence and Incentive Compatibility (Extended Abstract). Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings. Lecture Notes in Computer Science 3142: 320-331

188. Xiaotie Deng, Guojun Li: A PTAS for Embedding Hypergraph in a Cycle (Extended Abstract). Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings. Lecture Notes in Computer Science 3142: 433-444

189. Haodi Feng, Kang Chen, Chunyu Kit, Xiaotie Deng: Unsupervised Segmentation of Chinese Corpus Using Accessor Variety. Natural Language Processing - IJCNLP 2004, First In- ternational Joint Conference, Hainan Island, China, March 22-24, 2004, Revised Selected Papers. Lecture Notes in Computer Science 3248: 694-703

190. Ning Chen, Xiaotie Deng, Hong Zhu: Combinatorial auction across independent markets (extended abstract). ACM Conference on Electronic Commerce 2003: 206-207.

191. Xiaotie Deng, Qizhi Fang, Shanfeng Zhu: Approximate Rank Aggregation (Preliminary Ver- sion). Computing and Combinatorics, 9th Annual International Conference, COCOON 2003, Big Sky, MT, USA, July 25-28, 2003, Proceedings. Lecture Notes in Computer Science 2697:262-271

192. Lihua Chen, Xiaotie Deng, Qizhi Fang, Feng Tian: Majority Equilibrium for Public Facility Allocation (Preliminary Version). Computing and Combinatorics, 9th Annual International Con- ference, COCOON 2003, Big Sky, MT, USA, July 25-28, 2003, Proceedings. Lecture Notes in Computer Science 2697: 435-444

193. 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

194. Yunlei Zhao, Xiaotie Deng, Chan H. Lee, Hong Zhu: Resettable Zero-Knowledge in the Weak Public-Key Model. EUROCRYPT 2003, International Conference on the Theory and Ap- plications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings. Lecture Notes in Computer Science 2656: 123-139

195. Shanfeng Zhu, Qizhi Fang, Xiaotie Deng, Weiming Zheng: Metasearch via Voting. Intelligent Data Engineering and Automated Learning, 4th International Conference, IDEAL 2003, Hong Kong, China, March 21-23, 2003, Revised Papers. Lecture Notes in Computer Science 2690 2003: 734-741

196. Weimin Zheng, Jiwu Shu, Xiaotie Deng, Yonggen Gu: Parallel Computing Method of Valuing for Multi-asset European Option. International Conference on Computational Science 2003: 3-9

197. Ning Chen, Xiaotie Deng, Hong Zhu: Double Auction in Two-Level Markets. International Conference on Computational Science 2003: 34-45

198. Xiaotie Deng, Chan H. Lee, Yunlei Zhao, Hong Zhu: (2+ f(n))-SAT and Its Properties. Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings. Lecture Notes in Computer Science 2387: 28-36

199. Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, Lusheng Wang: A PTAS for Distinguishing (Sub)string Selection. Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings. Lecture Notes in Computer Science 2380: 740-751

200. Mao-cheng Cai, Xiaotie Deng, Haodi Feng, Guojun Li, Guizhen Liu: A PTAS for Minimizing Total Completion Time of Bounded Batch Scheduling. Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings. Lecture Notes in Computer Science 2337: 304-314

201. Chan H. Lee, Xiaotie Deng, Huafei Zhu: Design and Security Analysis of Anonymous Group Identification Protocols. Public Key Cryptography 2002: 188-198

202. Xiaotie Deng, Chan H. Lee, Yunlei Zhao, Hong Zhu: Reduction Zero-Knowledge. Security in Communication Networks, Third International Conference, SCN 2002, Amalfi, Italy, September 11-13, 2002. Revised Papers. Lecture Notes in Computer Science 2576: 303-317

203. Shirley H. C. Cheung, Xiaotie Deng, Chan H. Lee, Yunlei Zhao: A New Notion of Soundness in Bare Public-Key Model. Security in Communication Networks, Third International Conference, SCN 2002, Amalfi, Italy, September 11-13, 2002. Revised Papers. Lecture Notes in Computer Science 2576: 318-325

204. Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra: On the complexity of equilibria. Pro- ceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Mon- tréal, Québec, Canada. ACM, 2002: 67-71

205. Kang Chen, Weimin Zheng, Xiaotie Deng, Haodi Feng, Shanfeng Zhu: Text Distinguishers Used in an Interactive Meta Search Engine. Advances in Web-Age Information Management, Third International Conference, WAIM 2002, Beijing, China, August 11-13, 2002, Proceedings. Lecture Notes in Computer Science 2419: 181-188

206. Qizhi Fang, Shanfeng Zhu, Mao-cheng Cai, Xiaotie Deng: Membership for Core of LP Games and Other Games. Computing and Combinatorics, 7th Annual International Conference, CO- COON 2001, Guilin, China, August 20-23, 2001, Proceedings. Lecture Notes in Computer Sci- ence 2108: 247-256

207. Chan H. Lee, Xiaotie Deng, Huafei Zhu: An Identification Scheme Provably Secure against Reset Attack. Information and Communications Security, Third International Conference, ICI- CS 2001, Xian, China, November 13-16, 2001. Lecture Notes in Computer Science 2229: 271-279

208. Kang Chen, Weimin Zheng, Hung Chim, Xiaotie Deng, Haodi Feng, Shanfeng Zhu: On-Line Selection Of Distinguishing Elements For Focused Information Retrieval, Proceedings of the 2001 IEEE International Conference on Multimedia and Expo, ICME 2001, August 22-25, 2001, Tokyo, Japan. IEEE Computer Society 2001.

209. B. Chen, X. Deng, and W. Zang, On-line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time, 12th International Symp. On Algorithms and Computa- tion, LNCS2223, pp.380-389, Christchurch, New Zealand, Dec. 2001.

210. X. Deng, H. Feng, P. Zhang, and H. Zhu, A Polynomial Time Approximation Scheme for Mini- mizing Total Completion Time of Unbounded Batch Scheduling, 12th International Symp. On Algorithms and Computation, LNCS2223, pp.26-35, Christchurch, New Zealand, Dec. 2001.

211. DENGX,IPHHS,LAWKCK,LIJ,ZHENGWandZHUS,"ParallelModelsandJobChar- acterisation for System Scheduling", Lecture Notes in Computer Science, International Com- puter Science Conference (ICSC2001), LNCS2074, pp.648-656, San Francisco, USA, May 28- 30, 2001.

212. X. Deng and S. Zhang. Arbitrage-free Asset Pricing in General State Space. Intelligent Data Engineering and Automated Learning - IDEAL 2000, Data Mining, Financial Engineering, and Intelligent Agents, Second International Conference, Shatin, N.T. Hong Kong, China, Decem- ber 13-15, 2000, Proceedings. Lecture Notes in Computer Science 1983: pp. 551-558.

213. X. Deng, G. Li, W. Zang and Y. Zhou. A 2-approximation algorithm for path coloring on trees of rings, Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings. Lecture Notes in Computer Science 1969: pp. 144-155.

214. D. Wang, X. Deng, W. Zheng. CHARM: A Checkpoint-based Rollback Recovery and Process Migration System for Cluster of Workstations. Proceedings of the 4th International Conference on Algorithms and Architectures for Parallel Processing, pp.708-709, December 2000, Hong Kong.

215. X. Deng, CH Lee, D. Pointcheval, H. Zhu. Extension of Classical Decisional Diffie-Hellman Problem. Proceedings of 2000 International Conference on Information Society in the 21st Cen- tury, pp. 401-402, November 5-8, Aizu-Wakamatzu City, Japan.

216. X. Deng, Z. Li, and S. Wang. On Computation of Arbitrage for Markets with Friction. Lecture Notes in Computer Science 1858, pp. 310-319, July 2000.

217. X. Deng, C.K. Poon, and Y. Zhang. Approximation Algorithms in Batch Processing. Lecture Notes in Computer Science 1741, pp.153-162, December 1999.

218. X. Deng, E. Milios, and A. Mirzaian. Robot Map Verification of a Graph World. Lecture Notes in Computer Science 1663, pp.86-97, August 1999.

219. X. Deng, and Yuzhong Zhang. Minimizing Mean Response Time for Batch Processing Systems. Lecture Notes in Computer Science 1627, pp.231-240, July 1999.

220. M. Cai, X. Deng, and W. Zang. A Max-Min Theorem for Feedback Vertex Set. Lecture Notes in Computer Science 1610, pp. 73-86, June 1999.

221. Pierluigi Crescenzi, Xiaotie Deng and Christos Papadimitriou. On Approximating a Scheduling Problem. Proceedings of Conference on "Approximation and Complexity in Numerical Opti- mization: Continuous and Discrete Problems", February 28 - March 2, 1999, University of Flor- ida.

222. X. Deng, CH. Lee and H. Zhu. A proposal for data encryption scheme. International Database Conference, Hong Kong, 1999.

223. X. Deng, CH. Lee and H. Zhu. A proposal for hash algorithm. Cryp/TEC’99, Hong Kong.

224. CH. Lee, X. Deng and H. Zhu. Deniable encryption system. Cryp/TEC’99, Hong Kong.

225. Binhai Zhu, Xiaotie Deng. On Computing and Drawing Maxmin-Height Covering Triangulation. Lecture Notes in Computer Science 1547, pp 464-466, 1998.

226. M.Cai, X. Deng, and W. Zang. A TDI System and Its Application to Approximation Algorithm. Proceedings of IEEE Annual Symposium on Foundations of Computer Science, pp. 227-231, Palo Alto, November 1998.

227. Z. Li, S. Wang, and X. Deng. A New Linear Programming Algorithm for Portfolio Selection. Advances in Operations Research and Systems Engineering, Edited by J. Gu, G. Fan, S. Wang and B. Wei, pp. 55-60, 1998.

228. Y. Xia, S. Wang, and X. Deng. An Optimal Portfolio Selection Model with Transaction Costs. Advances in Operations Research and Systems Engineering, Edited by J. Gu, G. Fan, S. Wang and B. Wei, pp. 118-123, 1998.

229. X. Deng and C.H. Papadimitriou. Decision-making by Hierarchies of Discordant Agents. Lecture Notes in Computer Science 1350, pp. 183-192, December 1997.

230. D. Tremaine, P.W. Dymond and X. Deng. Experimental Results on Minimising Communication Phases on a network of Workstations. Proc. 10th International Conference on Parallel and Dis- tributed Computing Systems, pp. 204-209, International Society for Computers and their Ap- plications (ISCA), 1997.

231. Jieliang Zhou, Patrick Dymond, and Xiaotie Deng. A Parallel Convex Hull Algorithm with Op- timal Communication Phases. Proceedings of the 11th IEEE International Parallel Processing Symposium, Geneva, April 1997, pp.596-602.

232. Jeff Edmonds, Donald D. Chinn,Tim Brecht, Xiaotie Deng. Nonclairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics. Proceedings of the 29th ACM Symposium on Theory of Computing, May 1997, pp.120-129.

233. Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi. Combinatorial Optimization Games. Pro- ceedings of the Eighth ACM/SIAM Symposium on Discrete Algorithms, New Orleans, January 1997, pp.720-729.

234. Jieliang Zhou, Patrick Dymond, Xiaotie Deng. Graphs Algorithms with Small Communication Cost. Presented at the 30th Hawaii International Conference on System Science, Maoi, Hawaii, January 1997.

235. Xiaotie Deng. Portfolio Management with Optimal Regret Ratio. Proceedings of International Conference on Management Science, Hong Kong, July 1996, pp. 289-295.

236. Xiaotie Deng and Patrick Dymond. On Multiprocessor System Scheduling. Proceedings of the Seventh ACM Symposium on Parallel Architectures and Algorithms, June 1996, pp. 82-88.

237. X. Deng and B. Zhu. A Randomized Algorithm for Voronoi Diagram of Line Segments on Coarse Grained Multiprocessors. Proceedings of the 10th IEEE International Parallel Processing Symposium, Honolulu, Hawaii, April 1996, pp. 192-198.

238. X. Deng, N. Gu, T. Brecht, and K. Lu. Preemptive Scheduling of Parallel Jobs on Multiproces- sors. Proceedings of the Seventh ACM/SIAM Symposium on Discrete Algorithms, Atlanta, Georgia, January 1996, pp.159-167.

239. T. Brecht, X. Deng, and N. Gu. Competitive Dynamic Processor Allocation for Parallel Ap- plications. Proceedings on the Seventh IEEE Symposium on Parallel and Distributed Process- ing, San Antonio, Texas, 1995, pp. 448-455.

240. X. Deng, Q. Wang and S. Wang. On The Complexity of Linear Bilevel Programming. Proceed- ings of the first International Symposium on Operations Research with Applications, Beijing, China, 1995, pp.205-212.

241. F. Dehne, X. Deng, P. Dymond , A. Fabri, and A.~Khokhar. A Randomized Parallel 3D Convex Hull Algorithm For Coarse Grained Multicomputers. Proceedings of the Sixth ACM Sympo- sium on Parallel Architectures and Algorithms, Santa Barbara, 1995, pp. 27-33.

242. X. Deng. Distributed NearOptimal Matching. Lecture Notes in Computer Science 920, pp.135- 144, May, 1995.

243. X. Deng and P. Dymond. Efficient Routing and Message Bounds for optimal parallel algo- rithms. Proceedings of 9th IEEE International Parallel Processing Symposium, Santa Barbara, California, 1995, pp.556-562.

244. X. Deng and N. Gu, Good Algorithm Design Style for Multiprocessors, Proceedings of IEEE Symposium on Parallel and Distributed Processing, Dallas, October 1994, pp. 538-543.

245. X. Deng. On Computational Rational Decision Making. ADVANCES IN MANAGEMENT SCIENCE (ed. by Z.M.Lu, C.Q.Liu, X.T.Chen and S.Y.Wang), International Academic Publish- ers, 1994, pp.147-151.

246. X. Deng. A Convex Hull Algorithm on Multiprocessor. Lecture Notes in Computer Science 834, pp. 634-642, August 1994.

247. X. Deng and E. Koutsoupias. Competitive Implementation Of Parallel Programs. The Fourth Annual ACM—SIAM Symposium on Discrete Algorithms, 1993, pp.455-461.

248. X. Deng and A. Mirzaian. Competitive Mapping with Foot—Print. Lecture Notes in Computer Science 762, pp.353-362, December 1993.

249. X. Deng, E. Milios and A. Mirzaian. Landmark Selection for Path Execution. Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, July 1993, pp.1339-1348.

250. X. Deng and C. Papadimitriou. Competitive Distributed Decision—Making. Algorithms, Soft- ware, Architecture, ed. J. van Leeuwen, Elseview Science Publishers B.V., 1992 IFIP, pp. 350-356.

251. X. Deng, P. Hell and J. Huang. Recognition and representation of proper circular arc graphs, Proceedings of the Second Conference on Integer Programming and Combinatorial Optimiza- tion, (Egon Balas, G. Cornuejols, and R. Kannan, eds.), 1992, pp. 114-121.

252. X. Deng, T. Kameda and C. Papadimitriou. How to Learn an Unknown Environment. IEEE 32nd Symposium on Foundations of Computer Science, 1991, 298-303.

253. X. Deng and S. Mahajan. Randomization vs Computability in Online Algorithms. ACM Sym- posium on Theory of Computing, 1991, pp.289-298.

254. C.K. Chen, X. Deng , Y.Z. Liao, and S. Z. Yao. Compaction of Symbolic Layout under Bridge Rules. Proceedings of ISCAS, 1991, pp. 2132-2135.

255. BarNoy, X. Deng, J. Garay, T. Kameda. Optimal Amortized Distributed Consensus. Proceedings of the 5th International Workshop on Distributed Algorithms, September 1991, pp. 13-23.

256. X. Deng and C. Papadimitriou. Exploring an Unknown Graph. IEEE 31st Annual Symposium on Foundations of Computer Science, 1990, pp. 355-361.

257. X. Deng, H. Liu and B. Xiao. Deterministic Load Balancing in Computer Networks. The 2nd IEEE Symposium on Parallel and Distributed Processing, 1990, pp.50-57.

258. X. Deng. On the Parallel Complexity of Integer Programming. The First ACM Symposium on Parallel Algorithms and Architectures, pp.110116, 1989.

Non-referred publications (Technical Reports)

259.260. 261. 262. 263. 264.

X. Deng and B. Zhu. A Randomized Algorithm for Voronoi Diagram of Line Segments on Coarse Grained Multiprocessors. Technical Report, No. CS 9505, Department of Computer Sci- ence, York University, 1995.

X. Deng, N. Gu, K. Lu, and T. Brecht. Preemptive Scheduling of Parallel Jobs on Multiproces- sors. Technical Report, No. CS 9504, Department of Computer Science, York University, 1995. X. Deng and P. Dymond. Efficient Routing and Message Bounds for Implementing Parallel

Algorithms. Tech. Report CS9404, Department of Computer Science, York University.

X. Deng, T. Kameda and C. Papadimitriou. How to Learn an Unknown Environment I: The

Rectilinear Case. Tech. Report CS9305, Department of Computer Science, York University.

X. Deng and T. Kameda. Reaching Byzantine Agreement in Amortized Constant Number of Rounds. SFU LCCR Tech Report 91—4.

X. Deng and C. Papadimitriou. On Path lengths module three: the first three cases. Technical Report Number CS90170, Dept of computer science and engineering, UCSD, La Jolla.

### Research Lab

**Name**

Distributed and Automated Games And Managerial Economics (daGAME) Lab

**Introduction**

The research subjects of lab are algorithmic game theory, Internet and blockchain economics, theory of multi-agents and deep reinforcement learning. We focuses on the methodological studies for the interactions of human with agents, in the epistemological changes with respect to acquisition of data and information, equilibrium and game dynamics among human and agents, computational and communication complexity, design and analysis of algorithms and protocols. We are especially interested in applications in the Internet market design, analysis of incentives and cooperative competition, as well as high performance consensus, reputation system design, as well as cross-chain mechanism design in Blockchain economics and technology.

https://cfcs.pku.edu.cn/english/research/researchlabs/237314.htm