Special Interest Group on Mathematics & Algorithms

SIGMA aims to promote the exchange of knowledge in theoretical computer science.
Anyone who wants to subscribe or unsubscribe can send email to Jia Zhang (

Schedule for Spring 2018

Speaker Topic Time Location
Lirong Xia Improving Group Decision-Making by Artificial Intelligence 14:00 Jul.24 Room 850, 8th floor, ICT, CAS
Cheng Guo Quantum Entanglement Transformation via Local Operations and Classical Communication 14:00 Jun.12 Room 850
David Woodruff Sublinear Time Low Rank Approximation of PSD Matrices 10:30 May.31 Room 801
Xiaohui Bei Cake Cutting - Envy and Truth 14:00 Apr.24 Room 850
Yuan Su Toward the first quantum simulation with quantum speedup 14:00 Mar.15 Room 850
Youming Qiao Matrix spaces as a linear algebraic analogue of graphs 14:00 Mar.13 Room 850

Schedule for Fall 2017

Speaker Topic Time Location
Tongyang Li Quantum query complexity of entropy estimation 15:30 Dec.27 Room 850
Xun Gao An effecient quantum algorithm for generative machine learning 14:00 Dec.14 Room 850
Nengkun Yu Chernoff Bound for Quantum Operations is Faithful 14:00 Nov.16 Room 850
Jianxin Chen Pure state tomography via Pauli measurements 10:30 Sep.29 Room 440

Schedule for Spring 2017

Speaker Topic Time Location
Kai Wang Energy-Aware Real-Time Task Scheduling on Local/Shared Memory Systems 13:30 Aug.24 Room 850
Peng Zhang, Georgia Tech Solving Graph-Structured Linear Systems 10:00 Aug.10 Room 801
程永席 组合群试问题的一些最新研究进展 10:30 Jul.20 Room 801
Lijie Chen Polynomial Approximate Degree and Oracle Separations 14:30 Mar.09 Room 850

Schedule for Fall 2016

Speaker Topic Time Location
Jiapeng Zhang Robust sensitivity 14:00 Dec.27 ROOM 801
Xiongfeng Ma From quantumness to security 13:30 Dec.02 Room 801
Jian Li Pure Exploration in Stochastic Multi-armed bandit Problems 11:00 Nov.11 Room 446
Siyao Guo The Power of Negations in Cryptography 11:00 Nov.04 Room 446
Youming Qiao Quantum matching problems 13:30 Sep.13 Room 801

Schedule for Spring 2016

Speaker Topic Time Location
Yixin Cao The Hardness of Minimum Fill-In: A Dark Secret of the Old Chinese Art 11:00 Aug.22 Room 801
Shengyu Zhang Assignment and Pricing in Roommate Market 11:00 Jul.21 Room 801
Jin-yi Cai Is the FKT algorithm universal for planar sum-of-product computation? 14:00 Jun.30 Room 446
Shiteng Chen Depth reduction for composites 11:00 May.24 Room 1201
David Woodruff (IBM Almaden) Beating CountSketch for Heavy Hitters in Insertion Streams 11:00 Feb.18 Room 850, 8th floor, ICT, CAS

Schedule for Fall 2015

Speaker Topic Time Location
Xiangliang Zhang (KAUST) Large-scale Streaming Data Mining, Model Design and Application 13:00 Dec.25 Room 801, 8th floor, ICT, CAS
Fei Gao Introduction to Quantum Cryptology 10:00 Dec.24 Room 801, 8th floor, ICT, CAS
Jian Li Learning Arbitrary Statistical Mixtures of Discrete Distributions 16:00 Sep.24 Room 850
Prof. Runyao Duan On zero-error communication via quantum channels in the presence of noiseless feedback 16:00 Sep.15 Room 446, 4th floor, ICT, CAS
Zhaohui Wei Assessing the dimension of a unknown quantum system in a device-independent manner 11:00 Sep.12 Room 801, 8th floor, ICT, CAS
Tian Liu A Recent Result on Circuit Complexity and Gate Elimination 11:00 Sep.05 Room 801, 8th floor, ICT, CAS

Schedule for Spring 2015

Speaker Topic Time Location
Tao Qin Cloud Computing Pricing: Algorithms and Mechanisms 14:00 Aug.31 Room 446
Ran Duan Approximate and Exact Algorithms for Maximum Weight Matching 14:00 Aug.27 Room 850
Yuchen Zhang Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds 14:30 Aug.13 Room 850
Huacheng Yu, Stanford University An Improved Combinatorial Algorithm for Boolean Matrix Multiplication 15:00 Jul.23 Room 850, 8th floor, ICT, CAS
Kai Jin, Tsinghua University Finding maximal parallelograms in convex polygons 15:00 May.21 Room 850, 8th floor, ICT, CAS
Periklis A. Papakonstantinou Big Data as a powerful source of randomness 15:00 May.07 Room 850, 8th floor, ICT, CAS
Pinyan Lu Approximate Counting via Correlation Decay 09:30 Apr.23 Room 446
Zhaohui Wei An introduction to PSD-rank and its applications 10:30 Apr.16 Room 801
Wei Chen Combinatorial Learning for Combinatorial Optimizations --- A Trilogy 10:20 Apr.08 Room 446

Schedule for Fall 2014

Speaker Topic Time Location
Zhaohui Wei On the power of linear programming and semidefinite programming over polytopes 10:30 Nov.20 Room 801
Uri Zwick The Random-Facet pivoting rule 10:30 Sep.20 Room 801
David Woodruff Lower Bounds for Data Streams- A Survey and Open Questions 10:00 Sep.18 Room 801

Schedule for Spring 2014

Speaker Topic Time Location
Huacheng Yu Finding Four-Node Subgraphs in Triangle Time 14:00 Jul.23 Room 850
Jing Chen Optimal Provision-After-Wait in Healthcare 11:00 Jul.14 Room 801
Penghui Yao A parallel repetition theorem for entangled two-player one-round games under product distributions 15:30 Jun.25 Room 848
Minming Li Algorithmic mechanism design on cloud computing and facility location 10:30 Jun.13 Room 848
David Guoliang Wang Log-concavity of combinations of sequences and applications to genus distributions 10:30 Jun.04 Room 301
Xiaohui Bei Balancing Efficiency and Fairness in Resource Allocation 10:30 May.30 Room 1201
Dominik Scheder On the average sensitivity and density of k-CNF formulas 10:30 May.16 Room 446
Wei Chen Incentives and Intermediaries in Network Diffusions 10:30 May.05 Room 446

Schedule for Fall 2013

Speaker Topic Time Location
Liwei Wang Privacy Preserving Machine Learning in the Big Data Era: A Theoretically Sound Approach 14:00 Dec.31 Room 1234
Chia-Jung Lee Beating Bandits in Gradually Evolving Worlds 10:20 Dec.20 Room 1234
Chenggang Wu Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture 11:00 Nov.15 Room 1234
Kevin Matulef The Art of Proving Lower Bounds in Property Testing 11:00 Oct.22 Room 1234
Pinyan Lu Pricing and Auctions for Markets with Externalities 10:30 Oct.15 Room 440
Peter Bro Miltersen Some applications of semi-algebraic geometry to proving complexity results in computational game theory 10:30 Oct.11 Room 446
Mingsheng Ying Floyd–Hoare Logic for Quantum Progras 10:30 Sep.29 Lecture Room of 4th Floor

Schedule for Spring 2013

Speaker Topic Time Location
Lirong Xia Statistical Algorithms for Computing Parametric Ranking Models 14:00 Jul.16 Room 1234
Youming Qiao Generalized Wong sequences and their applications to Edmonds' problem 14:00 Jul.02 Room 1234
Guang Yang Streaming Cryptography 14:00 Jun.05 Room 1234
Chengu Wang Communication Complexity of Inner Product and Determinant 14:00 May.07 Room 1234
Xi Yang Robust consensus of multi-agent systems with communication errors 10:30 Apr.12 Room 1234
Angsheng Li Network science: A new perspective 14:00 Apr.09 Room 446
Jie Zhang Fixed-point Models, Complexities, and Applications 10:30 Mar.29 Room 446
Wei Yu Budget Error-Correcting under Earth-Mover Distance 09:30 Mar.29 Room 446
Yajun Wang lgorithms for submodular matroid secretary problems 14:00 Mar.07 Room 1234

Schedule for Fall 2012

Speaker Topic Time Location
Xingwu Liu Perturbation Analysis of Maximum-Weighted Bipartite Matchings with Low Rank Data 14:00 Jan.31 Room 1234
Haitao Wang Shortest Path Problems in Computational Geometry 14:00 Jan.17 Room 1234
Jian Li Uncertainty in Combinational Optimization 14:00 Jan.09 Room 1234
Jie Tang Social Influence Analysis in Large Social Networks 09:45 Jan.04 Room 446
Liwei Wang Margin theories for machine learning 14:00 Dec.13 Room 446
Yuan Zhou Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs 11:00 Dec.10 Room 1234
Hoong Chuin Lau Dynamic Experience Management in Theme Parks via Coordination and Incentives 10:00 Dec.10 Lecture Room of 4th Floor
Bo An Next Generation Applications of Security Games: Challenges and Progress 13:30 Dec.06 Room 1234
Pingzhong Tang Optimal Mechanism Design: Computation and Economics 10:00 Dec.04 Room 446
Xujin Chen Lower Price of Anarchy of Selfish Task Allocation with More Selfishness 14:00 Nov.22 Room 446
Tian Liu Algorithm on Tree Convex Bipartite Graphs 14:00 Oct.25 Room 1234
Navid Talebanfard Semantic properties of syntactic structures 10:30 Oct.18 Room 446
Minming Li DVS scheduling for various processor models and task types 10:00 Sep.27 Room 1234
David Woodruff Low Rank Approximation and Regression in Input Sparsity Time 14:00 Sep.11 Room 1234
David Woodruff Sketching Techniques for Numerical Linear Algebra 14:00 Sep.06 Room 446

Schedule for Spring 2012

Speaker Topic Time Location
Lusheng Wang Algorithms for the closest string and the shablue center problems 13:00 May.15 Room 1234
Ning Chen Budget Feasible Mechanism Design 10:30 May.11 Room 446
Jialin Zhang When Selfish Agents Meet Distributed System: distributed consensus resilient to strategic manipulations 09:30 May.11 Room 446
Junming Huang Recommender Systems 14:00 Apr.12 Room 1234
Chunlin Huang, Dawei Chen Better Vaccination Strategies for Better People 14:00 Mar.29 Room 1234
Tianshi Chen Evolutionary Algorithms 14:00 Mar.22 Room 1234
Chao Wang Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs 14:00 Mar.15 Room 1234
Marcos Villagra Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication 14:00 Mar.08 Room 1234
Xiaoming Sun Communication Complexity 09:30 Feb.29 Room 901

Schedule for Fall 2011

Speaker Topic Time Location
Jingjie Liu Optimal Path Search in Small Worlds: Dimension Matters 15:00 Dec.20 Room 440
Dong Han Why Greed Works for Shortest Common Superstring Problem 15:00 Dec.13 Room 440
Lin Wang Distributed Selfish Load Balancing 15:00 Dec.06 Room 440
Lei Nie Which Networks Are Least Susceptible to Cascading Failures 14:00 Oct.29 Room 1234