[简体中文]
ribbon

The mission of the lab 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, online algorithms, quantum computing, communication complexity, decision-tree complexity, etc.

Currently, the lab contains 7 faculty members (including 2 professors, 1 associate professor and 4 assistant professors), 3 affiliated faculty members and over 20 students. The lab 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 lab 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 lab is on its way to become an outstanding lab on theoretical computer science.

Upcoming Seminars

New Coresets for Clustering: Beyond Euclidean Geometry . Sep. 16, 10:00

Graphical language for quantum computing and its application . Sep. 09, 10:00

Recent Events

TCS Youth Forum (16th Oct., 2019)

Algorithmic Aspects in Information and Management (AAIM Aug. 2019)

Recent Publications

  • Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang: Network Inference and Influence Maximization from samples. Accepted to 38th International Conference on Machine Learning (ICML 2021).
  • Weiming Feng, Kun He, Yitong Yin: Sampling Constraint Satisfaction Solutions in the Local Lemma Regime. Accepted to 53rd Annual ACM Symposium on Theory of Computing (STOC 2021). [arXiv]
  • Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun, Patrick Rebentrost: Quantum-classical algorithms for skewed linear systems with an optimized Hadamard test. Physical Review A, 103(4), pp. 042422. [arXiv]
  • Weiming Feng, Kun He, Xiaoming Sun, Yitong Yin: Dynamic Inference in Probabilistic Graphical Models. In 12th Innovations in Theoretical Computer Science Conference, pp. 25:1–25:20. [arXiv]
  • Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang: Optimization from Structured Samples for Coverage Functions. In 37th International Conference on Machine Learning (ICML 2020), pp. 1715-1724. [arXiv]
  • Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng: On the degree of Boolean Functions as Polynomials over $\mathbb Z_m$. In 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), pp. 100:1-100:19. [arXiv]
  • Feidiao Yang, Jiaqing Jiang, Jialin Zhang, Xiaoming Sun: Revisiting Online Quantum State Learning. In 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 6607-6614. [PDF]
  • Xiaohui Bei, Xiaoming Sun, Hao Wu, Jialin Zhang, Zhijie Zhang, Wei Zi: Cake cutting on graphs: a discrete and bounded proportional protocol. In 40th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 2114-2123. [arXiv]
  • Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, Jialin Zhang: Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis. In 40th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 213-229. [arXiv]
  • Youming Qiao, Xiaoming Sun, Nengkun Yu: Local Equivalence of Multipartite Entanglement. IEEE Journal on Selected Areas in Communications, 38(3), pp. 568-574.
  • Riling Li, Bujiao Wu, Mingsheng Ying, Xiaoming Sun, Guangwen Yang: Quantum Supremacy Circuit Simulation on Sunway TaihuLight. IEEE Transactions on Parallel and Distributed Systems, 31(4), pp. 805-816. [arXiv]
  • Bujiao Wu, Bin Cheng, Fei Jia, Jialin Zhang, Man-Hong Yung, Xiaoming Sun: Speedup in classical simulation of Gaussian boson sampling. Science Bulletin, 65(10), pp. 832-841. [arXiv]
  • Pei Yuan, Guojing Tian, Xiaoming Sun: Strong Quantum Nonlocality without Entanglement in Multipartite Quantum Systems. Physical Review A, 102(4), pp. 042228. [arXiv]
  • Jiaqing Jiang, Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia: Structured decomposition for reversible Boolean functions. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(10), pp. 2410-2421. [arXiv]
  • Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang: Quantum Lovász local lemma: Shearer's bound is tight. In 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), pp. 461-472. [arXiv]
AAIM 2019

AAIM 2019, the Thirteenth International Conference on Algorithmic Aspects in Information and Management, was hosted by Instdditute of Computing Technology Chinese Academy of Sciences, located in Beijing, China. It will provide a forum on current trends of research on algorithms, data structures, and their applications.

TIME: 2019-8-6 to 2019-8-8 VENUE: Xijiao Hotel, Beijing HOMEPAGE

AAAC 2018

The 11th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC) was hosted by Instdditute of Computing Technology Chinese Academy of Sciences, located in Beijing, China. AAAC was founded in 2007, aiming at promoting collaborations in theoretical computer science within the region.

TIME: 2018-5-18 to 2018-5-20 VENUE: Xijiao Hotel, Beijing HOMEPAGE

C&A 2018

Complexity & Algorithms Workshop 2018 was hosted by Institute of Computing Technology Chinese Academy of Sciences, located in Beijing, China.

TIME: 2018-5-17 to 2018-5-18 VENUE: Xijiao Hotel, Beijing HOMEPAGE

Faculty
Xiaoming Sun Xiaoming Sun
decision tree complexity, quantum computing, communication complexity, combinatorics and social network
Jialin Zhang Jialin Zhang
submodular maximization, quantum computing, approximation algorithm, algorithmic game theory, combinatorial optimization, online algorithm
Guojing Tian Guojing Tian
quantum entanglement, quantum nonlocality, local discrimination of quantum state, quantum coherence, quantum computing
Cheng Guo Cheng Guo
quantum information theory, quantum computation theory, tensor rank and polynomial rank, quantum protocols, numerical range
Qian Li Qian Li
quantum computing,boolean function analysis,randomized algorithms
Kun He Kun He
probabilistic method, counting and sampling
Meng Li Meng Li
quantum walk, quantum information, 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
Guang Yang Guang Yang
foundation of cryptography, randomness and derandomization, online agorithms and streaming computation, game theory, learning theory
Engineers
Postgraduates & Visiting Students
Zhiyu Xia
doctoral candidate
Yuan Sun
doctoral candidate
Zhijie Zhang
doctoral candidate
Xiaoyu He
doctoral candidate
Shuai Yang
doctoral candidate
Junhong Nie
doctoral candidate
Shuo Zhang
doctoral candidate
Chenglong Wang
master candidate
Zuzhi Chen
master candidate
Qinlin Zhu
master candidate
Wei Zi
doctoral candidate
Yu Han
master candidate
Zongqi Wan
master candidate
Rui Mao
doctoral candidate
Ci Lei
master candidate
Fangjie Peng
master candidate
Yiwei Gao
doctoral candidate
Sirui Peng
doctoral candidate
Longcheng Li
master candidate
Alumni
Jia Zhang
Microsoft Research Asia
Xiaohan Shan
Tsinghua University
Qian Li
Institute of Computing Technology, CAS
Kun He
Institute of Computing Technology, CAS
Qiang Li
Kuaishou
Gang Zeng
Kuaishou
Feidiao Yang
Microsoft Research Lab - Asia
Jiaqing Jiang
California Institute of Technology
Pei Yuan
Tencent
Bujiao Wu
Peking Univerisity
Zhihuai Chen
Huawei
Lifu Shou
Kuaishou
AAAC 2018
Spring 2021
Spring 2020
Fall 2012

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

Postcode: 100190     Telephone: 010-62600853    

中科院计算技术研究所量子计算与算法理论实验室诚聘助理研究员,欢迎从事:

及其他相关方向的研究人员加盟,同时也欢迎青年学子前来客座实习,精诚携手,共赴前程!

报名方式:发送简历至
孙晓明老师 sunxiaoming@ict.ac.cn
张家琳老师 zhangjialin@ict.ac.cn
详细情况,欢迎邮件咨询!