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.
New Coresets for Clustering: Beyond Euclidean Geometry
. Sep. 16, 10:00
Graphical language for quantum computing and its application
. Sep. 09, 10:00
TCS Youth Forum (16th Oct., 2019)
Algorithmic Aspects in Information and Management (AAIM Aug. 2019)
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, 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
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
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
decision tree complexity, quantum computing, communication complexity, combinatorics and social network
submodular maximization, quantum computing, approximation algorithm, algorithmic game theory, combinatorial optimization, online algorithm
quantum entanglement, quantum nonlocality, local discrimination of quantum state, quantum coherence, quantum computing
quantum information theory, quantum computation theory, tensor rank and polynomial rank, quantum protocols, numerical range
quantum computing，boolean function analysis，randomized algorithms
probabilistic method, counting and sampling
quantum walk, quantum information, quantum computing
algorithm design and analysis, including the SAT problem, information retrieval and bioinformatics
social and information networks, online learning, algorithmic game theory, Internet economics, distributed computing and fault tolerance
foundation of cryptography, randomness and derandomization, online agorithms and streaming computation, game theory, learning theory
Postgraduates & Visiting Students
Institute of Computing Technology, CAS
Institute of Computing Technology, CAS