[English]

本研究组的宗旨是学习和探索理论计算机科学领域的知识与真理,同时培养学生的专业才能。我们着力于从现实生活中抽象出问题,为这些问题设计算法,并分析这些算法的计算复杂度。目前,我们的研究领域包括:社交网络、通信复杂度、博弈论、组合优化、在线算法、量子计算以及决策树复杂度等。

现今,我们组共有四位研究人员(一位研究员,一位副研究员以及两位助理研究员)、两位合作导师、十三个学生。我们组每年都会邀请来自世界各地的知名科学家进行访问,同时也欢迎长期的客座交流。关于本组学术交流的详细信息,请访问sigma.ict.ac.cn。此外,我们研究组还与其他大学和研究机构,例如清华大学、微软亚洲研究院等,有着密切的合作关系。伴随如此活跃的研究氛围,我们正向着成为先进的理论计算机科学研究组的目标努力。

近期学术讲座

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits . Jul. 30, 02:00

Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms . Jul. 23, 02:00

Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds . Jul. 16, 02:00

近期事件

TCS Youth Forum (16th Oct., 2019)

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

最近发表

Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang: Optimization from Structured Samples for Coverage Functions. ICML 2020 Accepted.

Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng: On the Degree of Boolean Functions as Polynomials over Z_m. ICALP 2020 Accepted. arXiv: 1910.12458

Bujiao Wu, Bin Cheng, Fei Jia, Jialin Zhang, Man-Hong Yung, Xiaoming Sun: Speedup in classical simulation of Gaussian boson sampling. Science Bulletin, vol. 65, no. 10, pp. 832-841, 30 May 2020, doi: 10.1016/j.scib.2020.02.012. arXiv: 1908.10070

Riling Li, Bujiao Wu, Mingsheng Ying, Xiaoming Sun, Guangwen Yang: Quantum Supremacy Circuit Simulation on Sunway TaihuLight. IEEE Transactions on Parallel and Distributed Systems, vol. 31, no. 4, pp. 805-816, 1 April 2020, doi: 10.1109/TPDS.2019.2947511. arXiv: 1804.04797

Youming Qiao, Xiaoming Sun, Nengkun Yu: Local Equivalence of Multipartite Entanglement. IEEE Journal on Selected Areas in Communications 38(3): 568-574, March 2020.

Feidiao Yang, Jiaqing Jiang, Xiaoming Sun, Jialin Zhang: Revisiting Online Quantum State Learning. AAAI 2020.

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. SODA 2020. arXiv: 1907.05087

Xiaohui Bei, Xiaoming Sun, Hao Wu, Jialin Zhang, Zhijie Zhang, Wei Zi: Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol. SODA 2020. arXiv: 1907.05083

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 (2019, Accepted). arXiv: 1810.04279

Kun He, Qian Li, Xiaoming Sun and Jiapeng Zhang: Quantum Lovász Local Lemma: Shearer's Bound is Tight. STOC 2019. arXiv: 1804.07055

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

科研人员
孙晓明
社会网络与博弈论相关的算法研究,量子计算,通信复杂性,判定树复杂度,组合数学
张家琳
次模优化,量子计算,近似算法,算法博弈论,组合优化,在线算法
杨光
密码学基础,随机性与去随机化,在线算法与流算法,博弈论,机器学习
田国敬
量子纠缠,量子非局域性,量子态的局域区分性,量子相干性,量子计算
卜东波 (合作导师)
算法设计与分析,包括SAT问题,信息检索以及生物信息学
陈卫 (客座研究员)
社交和信息网络,在线学习,算法博弈论,互联网经济,分布式计算和容错
研究生&客座学生
陈志怀
博士生
杨飞雕
博士生
吴步娇
博士生
袁佩
博士生
夏之雨
博士生
孙元
博士生
张智杰
研究生
蒋佳卿
研究生
何啸宇
研究生
杨帅
研究生
寿立夫
研究生
聂均鸿
博士生
张硕
博士生
王成龙
研究生
陈祖志
研究生
朱钦霖
研究生
毕业生
张佳
微软亚洲研究院
单小涵
清华大学
李乾
深圳研究院
李强
快手
曾钢
快手
何昆
深圳研究所
Spring 2020
Fall 2012
Show more seminars
    2020
  • Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang: Optimization from Structured Samples for Coverage Functions. ICML 2020 Accepted.
  • Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng: On the Degree of Boolean Functions as Polynomials over Z_m. ICALP 2020 Accepted. arXiv: 1910.12458
  • Bujiao Wu, Bin Cheng, Fei Jia, Jialin Zhang, Man-Hong Yung, Xiaoming Sun: Speedup in classical simulation of Gaussian boson sampling. Science Bulletin, vol. 65, no. 10, pp. 832-841, 30 May 2020, doi: 10.1016/j.scib.2020.02.012. arXiv: 1908.10070
  • Riling Li, Bujiao Wu, Mingsheng Ying, Xiaoming Sun, Guangwen Yang: Quantum Supremacy Circuit Simulation on Sunway TaihuLight. IEEE Transactions on Parallel and Distributed Systems, vol. 31, no. 4, pp. 805-816, 1 April 2020, doi: 10.1109/TPDS.2019.2947511. arXiv: 1804.04797
  • Youming Qiao, Xiaoming Sun, Nengkun Yu: Local Equivalence of Multipartite Entanglement. IEEE Journal on Selected Areas in Communications 38(3): 568-574, March 2020.
  • 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. ITCS 2020. arXiv: 1904.03950
  • Feidiao Yang, Jiaqing Jiang, Xiaoming Sun, Jialin Zhang: Revisiting Online Quantum State Learning. AAAI 2020.
  • 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. SODA 2020. arXiv: 1907.05087
  • Xiaohui Bei, Xiaoming Sun, Hao Wu, Jialin Zhang, Zhijie Zhang, Wei Zi: Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocl. SODA 2020. arXiv: 1907.05083
  • 2019
  • Kun He, Qian Li, Xiaoming Sun: A tighter relation between sensitivity complexity and certificate complexity. Theoretical Computer Science 762: 1-12 (2019), with a earlier version published in COCOON 2017. arXiv: 1609.04342
  • 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 (2019, Accepted). arXiv: 1810.04279
  • Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia: On the Relationship between Energy Complexity and other Boolean Function Measures. COCOON 2019. arXiv: 1810.03811
  • Xiaoming Sun, Yuan Sun, Zhiyu Xia, Jialin Zhang: The One-Round Multi-player Discrete Voronoi Game on Grids and Trees. COCOON 2019.
  • Xiaohan Shan, Wei Chen, Qiang Li, Xiaoming Sun, Jialin Zhang: Cumulative activation in social networks. Science China Information Sciences (2019). [PDF]
  • Luis Barba, Malte Milatz, Jerri Nummenpalo, Xiaoming Sun, Antonis Thomas, Jialin Zhang, Zhijie Zhang: The Complexity of Optimization on Grids. Algorithmica (2019).
  • Zhihuai Chen, Yinan Li, Xiaoming Sun, Pei Yuan, Jialin Zhang: A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorizations. IJCAI 2019.
  • David P. Woodruff and Guang Yang. Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. ICALP 2019. arXiv: 1905.07135
  • Xiaoming Sun, David P. Woodruff, Guang Yang and Jialin Zhang: Querying a Matrix through Matrix-Vector Products. ICALP 2019. arXiv: 1906.05736
  • Kun He, qian Li, Xiaoming Sun and Jiapeng Zhang: Quantum Lovász Local Lemma: Shearer's Bound is Tight. STOC 2019. arXiv: 1804.07055
  • Simina Brânzei, Claudio Orlandi, Guang Yang: Sharing Information with Competitors. SAGT 2019. arXiv: 1809.10637
  • 2018
  • Feidiao Yang, Tiancheng Jin, Tie-Yan Liu, Xiaoming Sun, Jialin Zhang: Boosting dynamic programming with neural networks for solving NP-hard problems. ACML 2018, pp. 726-739 (Best student paper) [PDF]
  • Bujiao Wu, Jiaqing Jiang, Jialin Zhang, Guojing Tian, Xiaoming Sun: Local unitary classification for sets of generalized Bell states. Phys. Rev. A 98, 022304 arXiv: 1711.06026
  • Xiaoyu He, Neng Huang, Xiaoming Sun. On the Decision Tree Complexity of String Matching. ESA2018 arXiv: 1712.09738
  • Wei Chen, Xiaohan Shan, Xiaoming Sun, Jialin Zhang. Coreness of Cooperative Games with Truncated Submodular Profit Functions. SAGT2018 arXiv: 1806.10833
  • Qian Li, and Xiaoming Sun. On the Module Degree Complexity of Boolean Functions. Accepted by Theoretical Computer Science.
  • Jiaqing Jiang, Jialin Zhang, Xiaoming Sun: Quantum-to-quantum Bernoulli factory problem. Phys.Rev.A. 97, 032303. arXiv: 1712.09817
  • 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

地址:北京海淀区中关村科学院南路6号 邮编:100190

联系电话:010-62600853

算法与复杂性课题组隶属前瞻实验室,主要从事计算机理论研究,具体方向包括量子计算、近似算法、计算复杂性、算法博弈论等。课题组承担了国基重点、科学院先导等多项重要科研项目,科研经费充足,同时与国内外著名高校及微软、华为等业界知名企业建立有广泛深入的合作关系。

只要你喜欢数学、热爱算法设计,有一定的英语基础,对科研感兴趣,勤奋努力,喜欢挑战有意思的问题,我们欢迎你攻读我们的研究生和博士学位。同时我们也非常欢迎其他院校本科学生或研究生短期或长期的客座实习。

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