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, decisiontree 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 wellknown 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: Quantumclassical 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. 17151724. [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:1100: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. 66076614. [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 ACMSIAM Symposium on Discrete Algorithms (SODA 2020), pp. 21142123. [arXiv]

Jiaqing Jiang, Xiaoming Sun, ShangHua Teng, Bujiao Wu, Kewen Wu, Jialin Zhang: Optimal spacedepth tradeoff of CNOT circuits in quantum logic synthesis. In 40th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2020), pp. 213229. [arXiv]

Youming Qiao, Xiaoming Sun, Nengkun Yu: Local Equivalence of Multipartite Entanglement. IEEE Journal on Selected Areas in Communications, 38(3), pp. 568574.

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. 805816. [arXiv]

Bujiao Wu, Bin Cheng, Fei Jia, Jialin Zhang, ManHong Yung, Xiaoming Sun: Speedup in classical simulation of Gaussian boson sampling. Science Bulletin, 65(10), pp. 832841. [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 ComputerAided Design of Integrated Circuits and Systems, 39(10), pp. 24102421. [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. 461472. [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: 201986 to 201988 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: 2018518 to 2018520 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: 2018517 to 2018518 VENUE: Xijiao Hotel, Beijing HOMEPAGE
Faculty
Xiaoming Sun
decision tree complexity, quantum computing, communication complexity, combinatorics and social network
Jialin Zhang
submodular maximization, quantum computing, approximation algorithm, algorithmic game theory, combinatorial optimization, online algorithm
Guojing Tian
quantum entanglement, quantum nonlocality, local discrimination of quantum state, quantum coherence, quantum computing
Cheng Guo
quantum information theory, quantum computation theory, tensor rank and polynomial rank, quantum protocols, numerical range
Qian Li
quantum computing，boolean function analysis，randomized algorithms
Kun He
probabilistic method, counting and sampling
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
foundation of cryptography, randomness and derandomization, online agorithms and streaming computation, game theory, learning theory
Engineers
Postgraduates & Visiting Students
Alumni
Qian Li
Institute of Computing Technology, CAS
Kun He
Institute of Computing Technology, CAS