[简体中文]
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

The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle . Nov. 30, 10:00

抑制超导量子计算机中ZZ串扰的波形-调度协同优化方法 . Nov. 23, 10:00

Recent Events

TCS Youth Forum (16th Oct., 2019)

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

Recent Publications

  • Siyao Guo, Qian Li, Qipeng Liu, and Jiapeng Zhang. Unifying Presampling via Concentration Bounds. Accepted by the Theory of Cryptography Conference (TCC 2021).
  • Yong Liu, Jiaqing Jiang, Pingyu Zhu, Dongyang Wang, Jiangfang Ding, Xiaogang Qiang, Anqi Huang, Ping Xu, Jialin Zhang, Guojing Tian, Xiang Fu, Mingtang Deng, Chunqing Wu, Xiaoming Sun, Xuejun Yang, Junjie Wu. General quantum Bernoulli factory: framework analysis and experiments. Quantum Science and Technology, 6, pp. 045025. [PDF]
  • Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang. Network Inference and Influence Maximization from samples. In 38th International Conference on Machine Learning (ICML 2021).
  • Weiming Feng, Kun He, Yitong Yin. Sampling Constraint Satisfaction Solutions in the Local Lemma Regime. In 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
Hongyi Zhou Hongyi Zhou
quantum communication, quantum optics
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
Yiren Lu
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
Fall 2021
Spring 2021
Spring 2020
Fall 2012
    2021
  • Siyao Guo, Qian Li, Qipeng Liu, and Jiapeng Zhang. Unifying Presampling via Concentration Bounds. Accepted by the Theory of Cryptography Conference (TCC 2021).
  • Zhi-Chao Zhang, Guojing Tian, Tian-Qing Cao. Strong quantum nonlocality for multipartite entangled states. Quantum Inf Process, 20, pp. 334. [PDF]
  • Yong Liu, Jiaqing Jiang, Pingyu Zhu, Dongyang Wang, Jiangfang Ding, Xiaogang Qiang, Anqi Huang, Ping Xu, Jialin Zhang, Guojing Tian, Xiang Fu, Mingtang Deng, Chunqing Wu, Xiaoming Sun, Xuejun Yang, Junjie Wu. General quantum Bernoulli factory: framework analysis and experiments. Quantum Science and Technology, 6, pp. 045025. [PDF]
  • Kejia Zhang, Xu Zhao, Long Zhang, Guojing Tian, Tinging Song. A Quantum Dual-Signature Protocol Based on SNOP States without Trusted Participant. Entropy-Switz, 23, pp. 1294.
  • Wei Zi, Shuai Yang, Cheng Guo, and Xiaoming Sun. Optimization of 16-Element Quantum Search on IBMQ. SPIN, 11(3), pp. 214003.
  • Zhihuai Chen, Bo Li, Xiaohan Shan, Xiaoming Sun, and Jialin Zhang. Discouraging pool block withholding attacks in Bitcoin. Journal of Combinatorial Optimization, None, pp. 1-16. [PDF]
  • Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang. Network Inference and Influence Maximization from samples. In 38th International Conference on Machine Learning (ICML 2021).
  • Feidiao Yang, Wei Chen, Jialin Zhang, Xiaoming Sun. Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization. Frontiers of Computer Science, 15(5), pp. 1-12. [PDF]
  • Weiming Feng, Kun He, Yitong Yin. Sampling Constraint Satisfaction Solutions in the Local Lemma Regime. In 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]
  • Qian Li, Xiaoming Sun. On the Sensitivity Complexity of k-Uniform Hypergraph Properties. ACM Transactions on Computation Theory, 13(2), pp. 12:1-12:13. [PDF]
  • 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]
  • 2020
  • 何昆, 孙晓明. 洛瓦兹局部引理的新变种及其应用. 中国科学 : 信息科学, 50(11), pp. 1680-1696.
  • Zhihuai Chen, Qiang Li, Xiaoming Sun, Lirong Xia, Jialin Zhang. Approximate Single-Peakedness in Large Elections. In 11th IEEE International Conference on Knowledge Graph (ICKG 2020), pp. 433-440.
  • Zhihuai Chen, Xiaoming Sun, Xiaohan Shan, Jialin Zhang. Decentralized Mining Pool Games in Blockchain. In 11th IEEE International Conference on Knowledge Graph (ICKG 2020), pp. 426-432.
  • 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]
  • Minming Li, Pinyan Lu, Yuhao Yao, Jialin Zhang. Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio. In 29th International Joint Conferences on Artificial Intelligence (IJCAI 2020), pp. 238-245. [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]
  • Heng Guo, Kun He. Tight bounds for popping algorithms. Random Structures & Algorithms, 57(2), pp. 371-392.
  • 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, Shiteng Chen, Ji Guan, Youming Qiao, Xiaoming Sun. From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pp. 568-574.
  • 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]
  • Xiaoming Sun, Yuan Sun, Jialin Zhang. Better Upper Bounds for Searching on a Line with Byzantine Robots. In Complexity and approximation 2020, pp. 151-171.
  • Wei Chen, Xiaohan Shan, Xiaoming Sun, Jialin Zhang. Coreness of cooperative games with truncated submodular profit functions. Theoretical Computer Science, 822, pp. 49-60.
  • Zhihuai Chen, Ken C.K. Fong, Minming Li, Kai Wang, Hongning Yuan, Yong Zhang. Facility location games with optional preference. Theoretical Computer Science, 847, pp. 185-197.
  • Youming Qiao, Xiaoming Sun, Nengkun Yu. Local Equivalence of Multipartite Entanglement. IEEE Journal on Selected Areas in Communications, 38(3), pp. 568-574.
  • Qian Li, Xiaoming Sun. On the modulo degree complexity of Boolean functions. Theoretical Computer Science, 818, pp. 32-40.
  • Qian Li, Xiaoming Sun, Jialin Zhang. On the Optimality of Tape Merge of Two Lists with Similar Size. Algorithmica, 82(7), pp. 2107-2132. [arXiv]
  • 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]
  • Xiaoming Sun, Yuan Sun, Zhiyu Xia, Jialin Zhang. The one-round multi-player discrete Voronoi game on grids and trees. Theoretical Computer Science, 838, pp. 143-159.
  • 2019
  • Simina Branzei, Claudio Orlandi, Guang Yang. Sharing Information with Competitors. In 12th International Symposium on Algorithmic Game Theory (SAGT 2019), pp. 34-48.
  • Zhihuai Chen, Yinan Li, Xiaoming Sun, Pei Yuan, Jialin Zhang. A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization. In 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 4511-4517.
  • Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia. On the Relationship between Energy Complexity and Other Boolean Function Measures. In 25nd International Conference on Computing and Combinatorics Conference (COCOON 2019), pp. 516-528.
  • Xiaoming Sun, Yuan Sun, Zhiyu Xia, Jialin Zhang. The One-Round Multi-player Discrete Voronoi Game on Grids and Trees. In 25nd International Conference on Computing and Combinatorics Conference (COCOON 2019), pp. 529-540.
  • Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang. Querying a Matrix through Matrix-Vector Products. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pp. 94:1-94:16.
  • David P. Woodruff, Guang Yang. Separating k-Player from t-player One-Way Communication, with Applications to Data Streams. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pp. 97:1-97:14.
  • 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]
  • Luis Barba, Malte Milatz, Jerri Nummenpalo, Xiaoming Sun, Antonis Thomas, Jialin Zhang, Zhijie Zhang. The Complexity of Optimization on Grids. Algorithmica, 81(9), pp. 3494-3518.
  • Xiaohan Shan, Wei Chen, Qiang Li, Xiaoming Sun, Jialin Zhang. Cumulative activation in social networks. SCIENCE CHINA Information Sciences, 62(5), pp. 52103:1-52103:21.
  • Kun He, Qian Li, Xiaoming Sun. A tighter relation between sensitivity complexity and certificate complexity. Theoretical Computer Science, 762, pp. 1-12.
  • 2018
  • Feidiao Yang, Tiancheng Jin, Tie-Yan Liu, Xiaoming Sun, Jialin Zhang. Boosting Dynamic Programming with Neural Networks for Solving NP-hard Problems. In 10th Asian Conference on Machine Learning (ACML 2018), pp. 726-739.
  • Wei Chen, Xiaohan Shan, Xiaoming Sun, Jialin Zhang. Coreness of Cooperative Games with Truncated Submodular Profit Functions. In 11th International Symposium on Algorithmic Game Theory (SAGT 2018), pp. 56-68.
  • Xiaoyu He, Neng Huang, Xiaoming Sun. On the Decision Tree Complexity of String Matching. In 26th Annual European Symposium on Algorithms (ESA 2018), pp. 45:1-45:13.
  • Jiaqing Jiang, Jialin Zhang, Xiaoming Sun. Quantum-to-quantum Bernoulli factory problem. Physical Review A, 97(3), pp. 032303.
  • Bujiao Wu, Jiaqing Jiang, Jialin Zhang, Guojing Tian, Xiaoming Sun. Local unitary classification for sets of generalized Bell states. Physical Review A, 98(2), pp. 022304.
  • 2017
  • Qiang Li, Wei Chen, Xiaoming Sun, Jialin Zhang. Influence Maximization with ε-Almost Submodular Threshold Function. In 31st Annual Conference on Neural Information Processing Systems (NIPS 2017), pp. 3802-3812.
  • Kun He, Liang Li, Xingwu Liu, Yuyi Wang and Mingji Xia. Variable Version Lovász Local Lemma: Beyond Shearer's Bound. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pp. 451-462.
  • Kun He, Qian Li, Xiaoming Sun. A Tighter Relation Between Sensitivity Complexity and Certificate Complexity. In 23rd International Conference on Computing and Combinatorics Conference (COCOON 2017), pp. 262-274.
  • Qian Li, Xiaoming Sun. On the Modulo Degree Complexity of Boolean Functions. In 23rd International Conference on Computing and Combinatorics Conference (COCOON 2017), pp. 384-395.
  • Qian Li, Xiaoming Sun. On the Sensitivity Complexity of k-Uniform Hypergraph Properties. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), pp. 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. In 31st AAAI Conference on Artificial Intelligence (AAAI 2017), pp. 252-258.
  • Jia Zhang, Weidong Ma, Tao Qin, Xiaoming Sun, Tie-Yan Liu. Randomized Mechanisms for Selling Reserved Instances in Cloud Computing. In 31st AAAI Conference on Artificial Intelligence (AAAI 2017), pp. 750-757.
  • Qin Huang, Xingwu Liu, Xiaoming Sun, Jialin Zhang. Partial Sorting Problem on Evolving Data. Algorithmica, 79(3), pp. 960-983.
  • Xiaoming Sun, Jia Zhang, Jialin Zhang. Near optimal algorithms for online weighted bipartite matching in adversary model. Journal of Combinatorial Optimization, 34(3), pp. 689-705.
  • 2016
  • Gang Zeng, Yuyi Wang, Juhua Pu, Xingwu Liu, Xiaoming Sun, Jialin Zhang. Communities in Preference Networks: Refined Axioms and Beyond. In 16th IEEE International Conference on Data Mining (ICDM 2016), pp. 599-608.
  • Qian Li, Xiaoming Sun, Jialin Zhang. On the Optimality of Tape Merge of Two Lists with Similar Size. In 27th International Symposium on Algorithms and Computation (ISAAC 2016), pp. 51:1-51:17.
  • Yiming Zou, Gang Zeng, Yuyi Wang, Xingwu Liu, Xiaoming Sun, Jialin Zhang, Qiang Li. Shortest Paths on Evolving Graphs. In 5th International Conference on Computational Social Networks (CSoNet 2016), pp. 1-13.
  • Wei Chen, Qiang Li, Xiaoming Sun, Jialin Zhang. The Routing of Complex Contagion in Kleinberg's Small-World Networks. In 22nd International Conference on Computing and Combinatorics Conference (COCOON 2016), pp. 307-318.
  • Periklis Papakonstantinou, Jia Xu, Guang Yang. On the Power of Distance-Based Learning. In 33rd International Conference on Machine Learning (ICML 2016), pp. 2263–2271.
  • Tie-Yan Liu, Weidong Ma, Tao Qin, Pingzhong Tang, and Bo Zheng. Online Non-Preemptive Story Scheduling in Web Advertising. In 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), pp. 269-227.
  • Xiaohui Bei, Wei Chen, Jugal Garg, Martin Hoefer, Xiaoming Sun. Learning Market Parameters Using Aggregate Demand Queries. In 30th AAAI Conference on Artificial Intelligence (AAAI 2016), pp. 411-417.
  • Periklis Papakonstantinou, David Woodruff and Guang Yang. True Randomness from Big Data. Scientific Reports, 6, pp. 33740.
  • Qizhi Fang, Bo Li, Xiaoming Sun, Jia Zhang, Jialin Zhang. Computing the least-core and nucleolus for threshold cardinality matching games. Theoretical Computer Science, 609, pp. 500-510.
  • Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang. Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions. Computational Complexity, 25(2), pp. 349-418.
  • 2015
  • Qin Huang, Xingwu Liu, Xiaoming Sun, Jialin Zhang. How to Select the Top k Elements from Evolving Data?. In 26th International Symposium on Algorithms and Computation (ISAAC 2015), pp. 60-70.
  • Qiang Li, Maojie Gu, Keren Zhou, Xiaoming Sun. Multi-Classes Feature Engineering with Sliding Window for Purchase Prediction in Mobile Commerce. In 15th IEEE International Conference on Data Mining Workshop (ICDM 2015), pp. 1048-1054.
  • Zhihao Yi, Danning Wang, Kai Hu, Qiang Li. Purchase Behavior Prediction in M-Commerce with an Optimized Sampling Methods. In 15th IEEE International Conference on Data Mining Workshop (ICDM 2015), pp. 1085-1092.
  • Xiaoming Sun, David P. Woodruff. Tight Bounds for Graph Problems in Insertion Streams. In 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 (APPROX-RANDOM 2015), pp. 435-448.
  • Qizhi Fang, Bo Li, Xiaohan Shan, Xiaoming Sun. The Least-Core and Nucleolus of Path Cooperative Games. In 21st International Conference on Computing and Combinatorics Conference (COCOON 2015), pp. 70-82.
  • Minming Li, Jialin Zhang, Qiang Zhang. Truthful Cake Cutting Mechanisms with Externalities: Do Not Make Them Care for Others Too Much!. In 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 589-595.
  • Raghav Kulkarni, Youming Qiao, Xiaoming Sun. On the Power of Parity Queries in Boolean Decision Trees. In 12th Annual Conference on Theory and Applications of Models of Computation (TAMC 2015), pp. 99-109.
  • Raghav Kulkarni, Youming Qiao, Xiaoming Sun. Any monotone property of 3-uniform hypergraphs is weakly evasive. Theoretical Computer Science, 588, pp. 16-23.
  • 2014
  • Xiaoming Sun, Jia Zhang, Jialin Zhang. Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol. In 25th International Symposium on Algorithms and Computation (ISAAC 2014), pp. 661-673.
  • Qizhi Fang, Bo Li, Xiaoming Sun, Jia Zhang, Jialin Zhang. Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games. In Web and Internet Economics: 10th International Conference (WINE 2014), pp. 474-479.
  • Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff. On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model. In 28th International Symposium on Distributed Computing (DISC 2014), pp. 499-513.
  • Peng Zhang, Wei Chen, Xiaoming Sun, Yajun Wang, Jialin Zhang. Minimizing seed set selection with probabilistic coverage guarantee in a social network. In 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2014), pp. 1306-1315.
  • Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo. Tighter Relations between Sensitivity and Other Complexity Measures. In 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), pp. 101-113.

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

Postcode: 100190     Telephone: 010-62600853    

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

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

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