[简体中文]
ribbon

The mission of the group is to develop knowledge and seek truth in the field of theoretical computer science as well as to train the talents of students. We are interested in the design of algorithms and analysis of the computational complexity for many problems abstracting from the issue in our real life. The current research area includes model and algorithm design in social network, algorithmic game theory, combinatorial optimization, graph theory, online algorithm, quantum computing, communication complexity, decision-tree complexity, etc.

Currently, the group contains 4 faculty members (including 1 professor, 1 associate professor and 2 assistant professors), 2 affiliated faculty members and 13 students. The group enjoys frequent visits by well-known scientists from all over the world each year. A small number of visitors for a longer period of time are also available. For more detailed information about our academic exchange, please refer to ref sigma.ict.ac.cn. In addition, the group also works in close collaboration with other universities and research centers such as Tsinghua University, Microsoft Research Asia, and so on. With a vibrant research environment, the group is on its way to become an outstanding group on theoretical computer science.

Upcoming Events

CNCC Quantum Computing (Oct. 2017)

Quantum Computing and Quantum Information Processing (QCQIP Nov. 2017)

Asian Association for Algorithms and Computation (AAAC May 2018)

Recent Publications

Qin Huang, Xingwu Liu, Xiaoming Sun, Jialin Zhang: Partial Sorting Problem on Evolving Data. Algorithmica 79(3): 960-983 (2017)

Qiang Li, Wei Chen, Xiaoming Sun, Jialin Zhang: Influence Maximization with ε-Almost Submodular Threshold Function. NIPS 2017.

Kun He, Liang Li, Xingwu Liu, Yuyi Wang and Mingji Xia: Variable Version Lovász Local Lemma: Beyond Shearer's Bound. FOCS 2017.

Faculty
Xiaoming Sun Xiaoming Sun
decision tree complexity, quantum computing, communication complexity, combinatorics and social network
Jialin Zhang Jialin Zhang
distributed computing theory, algorithmic game theory, social network, smoothed analysis and combinatorial optimization
Guang Yang Guang Yang
Foundation of Cryptography, Randomness and Derandomization, Online agorithms and Streaming Computation, Game Theory, Learning Theory
Guojing Tian Guojing Tian
Quantum Entanglement, Quantum Nonlocality, Local Discrimination of Quantum State, Quantum Coherence, Quantum Computing
Affiliated Faculty
Dongbo Bu
algorithm design and analysis, including the SAT problem, information retrieval and bioinformatics
Wei Chen
social and information networks, online learning, algorithmic game theory, Internet economics, distributed computing and fault tolerance
Postgraduates & Visiting Students
Xiaohan Shan
doctoral candidate
Qian Li
doctoral candidate
Zhihuai Chen
doctoral candidate
Kun He
doctoral candidate
Feidiao Yang
doctoral candidate
Bujiao Wu
master candidate
Pei Yuan
doctoral candidate
Zhiyu Xia
doctoral candidate
Ang Gao
master candidate
Yuan Sun
doctoral candidate
Zhijie Zhang
master candidate
Jiaqing Jiang
master candidate
Xiaoyu He
master candidate
Shuai Yang
master candidate
Alumni
Jia Zhang
Microsoft Research Asia
Qiang Li
Kuaishou
Gang Zeng
Kuaishou
Fall 2012
    2017
  • Qin Huang, Xingwu Liu, Xiaoming Sun, Jialin Zhang: Partial Sorting Problem on Evolving Data. Algorithmica 79(3): 960-983 (2017)
  • Xiaoming Sun, Jia Zhang, Jialin Zhang: Near optimal algorithms for online weighted bipartite matching in adversary model. J. Comb. Optim. 34(3): 689-705 (2017)
  • Qiang Li, Wei Chen, Xiaoming Sun, Jialin Zhang: Influence Maximization with ε-Almost Submodular Threshold Function. NIPS 2017.
  • Kun He, Liang Li, Xingwu Liu, Yuyi Wang and Mingji Xia: Variable Version Lovász Local Lemma: Beyond Shearer's Bound. FOCS 2017.
  • Kun He, Qian Li, Xiaoming Sun: A Tighter Relation Between Sensitivity Complexity and Certificate Complexity. COCOON 2017: 262-274
  • Qian Li, Xiaoming Sun: On the Modulo Degree Complexity of Boolean Functions. COCOON 2017: 384-395
  • Qian Li, Xiaoming Sun: On the Sensitivity Complexity of k-Uniform Hypergraph Properties. STACS 2017: 51:1-51:12
  • Jia Zhang, Zheng Wang, Qian Li, Jialin Zhang, Yanyan Lan, Qiang Li, Xiaoming Sun: Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising. AAAI 2017: 252-258
  • Jia Zhang, Weidong Ma, Tao Qin, Xiaoming Sun, Tie-Yan Liu: Randomized Mechanisms for Selling Reserved Instances in Cloud Computing. AAAI 2017: 750-757
  • 2016
  • Periklis Papakonstantinou, Jia Xu, Guang Yang: On the Power of Distance-Based Learning. ICML 2016: 2263–2271.
  • Qian Li, Xiaoming Sun, Jialin Zhang: On the Optimality of Tape Merge of Two Lists with Similar Size. ISAAC 2016: 51:1-51:17
  • Periklis Papakonstantinou, David Woodruff and Guang Yang: True Randomness from Big Data. Scientific Reports, 6:33740, 2016.
  • Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang: Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions. Computational Complexity 25(2): 349-418 (2016)
  • Tie-Yan Liu, Weidong Ma, Tao Qin, Pingzhong Tang, and Bo Zheng: Online Non-Preemptive Story Scheduling in Web Advertising. AAMAS 2016: 269-227
  • Xiaohui Bei, Wei Chen, Jugal Garg, Martin Hoefer, Xiaoming Sun: Learning Market Parameters Using Aggregate Demand Queries. AAAI 2016: 411-417
  • Qizhi Fang, Bo Li, Xiaoming Sun, Jia Zhang, Jialin Zhang: Computing the least-core and nucleolus for threshold cardinality matching games. Theor. Comput. Sci. 609: 500-510 (2016)
  • Gang Zeng, Yuyi Wang, Juhua Pu, Xingwu Liu, Xiaoming Sun, Jialin Zhang: Communities in Preference Networks: Refined Axioms and Beyond. IEEE International Conference on Data Mining (ICDM 2016).
  • Yiming Zou, Gang Zeng, Yuyi Wang, Xingwu Liu, Xiaoming Sun, Jialin Zhang, Qiang Li: Shortest Paths on Evolving Graphs. CSoNet 2016: 1-13
  • Wei Chen, Qiang Li, Xiaoming Sun, Jialin Zhang: The Routing of Complex Contagion in Kleinberg's Small-World Networks. COCOON 2016: 307-318
  • 2015
  • Xiaoming Sun, David P. Woodruff: Tight Bounds for Graph Problems in Insertion Streams. APPROX-RANDOM 2015: 435-448
  • Minming Li, Jialin Zhang, Qiang Zhang: Truthful Cake Cutting Mechanisms with Externalities: Do Not Make Them Care for Others Too Much! IJCAI 2015: 589-595
  • Qin Huang, Xingwu Liu, Xiaoming Sun, Jialin Zhang: How to Select the Top k Elements from Evolving Data? ISAAC 2015: 60-70
  • Raghav Kulkarni, Youming Qiao, Xiaoming Sun: On the Power of Parity Queries in Boolean Decision Trees. TAMC 2015: 99-109
  • Raghav Kulkarni, Youming Qiao, Xiaoming Sun: Any monotone property of 3-uniform hypergraphs is weakly evasive. Theor. Comput. Sci. 588: 16-23 (2015)
  • Qizhi Fang, Bo Li, Xiaohan Shan, Xiaoming Sun: The Least-Core and Nucleolus of Path Cooperative Games. COCOON 2015: 70-82
  • Qiang Li, Maojie Gu, Keren Zhou, Xiaoming Sun: Multi-Classes Feature Engineering with Sliding Window for Purchase Prediction in Mobile Commerce. ICDM Workshops 2015: 1048-1054
  • Zhihao Yi, Danning Wang, Kai Hu, Qiang Li: Purchase Behavior Prediction in M-Commerce with an Optimized Sampling Methods. ICDM Workshops 2015: 1085-1092
  • 2014
  • Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo: Tighter Relations between Sensitivity and Other Complexity Measures. ICALP 2014: 101-113
  • Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff: On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model. DISC 2014: 499-513
  • Xiaoming Sun, Jia Zhang, Jialin Zhang: Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol. ISAAC 2014: 661-673
  • Qizhi Fang, Bo Li, Xiaoming Sun, Jia Zhang, Jialin Zhang: Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games. WINE 2014: 474-479
  • Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang: Minimizing seed set selection with probabilistic coverage guarantee in a social network. KDD 2014: 1306-1315

Address: No.6 Kexueyuan South Road Zhongguancun, Haidian District, Beijing, China

Postcode: 100190     Telephone: 010-62600853