SIGMA

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 (zhangjia@ict.ac.cn).

Schedule for Fall 2016

Speaker Topic Time Location
Youming Qiao Quantum matching problems 13:30 Sept. 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 July 21 Room 801
Jin-yi Cai Is the FKT algorithm universal for planar sum-of-product computation? 14:00 June 30 Room 446
Shiteng Chen Depth reduction for composites 11:00 May 24 Room 1201
David Woodruff Beating CountSketch for Heavy Hitters in Insertion Streams 11:00 Feb. 18 Room 850

Schedule for Fall 2015

Speaker Topic Time Location
Xiangliang Zhang Large-scale Streaming Data Mining, Model Design and Application 13:00 Dec. 25 Room 850
Fei Gao Introduction to Quantum Crytology 10:00 Dec. 24 Room 801
Jian Li Learning Arbitrary Statistical Mixtures of Discrete Distributions 16:00 Sept. 24 Room 850
Runyao Duan On zero-error communication via quantum channels in the presence of noiseless feedback 16:00 Sept. 15 Room 446
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

Schedule for Spring 2015

Speaker Topic Time Location
Huacheng Yu An Improved Combinatorial Algorithm for Boolean Matrix Multiplication 16:00 Jul. 23 Room 850
Guangda Hu Sylvester-Gallai for Arrangements of Subspaces 16:00 Jul. 3 Room 810
Kai Jin Finding maximal parallelograms in convex polygons 15:00 May 21 Room 850
Periklis A. Papakonstantinou Big Data as a powerful source of randomness 15:00 May 7 Room 850
Pinyan Lu Approximate Counting via Correlation Decay 9:30 Apr. 23 Room 801
Zhaohui Wei An introduction to PSD-rank and its applications 10:30 Apr. 16 Room 801
Wei Chen Combinatorial Learning for Combinatorial Optimizations 10:30 Apr. 8 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
David Woodruff Lower Bounds for Data Streams- A Survey and Open Questions 10:00 Sept. 18 Room 801
Uri Zwick The Random-Facet pivoting rule 10:30 Sept. 4 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 850
Minming Li Algorithmic mechanism design on cloud computing and facility location 10:30 Jun. 13 Room 850
David Guoliang Wang Log-concavity of combinations of sequences and applications to genus distributions 10:30 Jun. 4 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 5 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
Yuan Zhou Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs 11:00 Dec. 10 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
Navid Talebanfard Semantic properties of syntactic structures 10:30 Oct. 18 Room 446
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 Sept. 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. 2 Room 1234
Guang Yang Streaming Cryptography 14:00 Jun. 5 Room 1234
Chengu Wang Communication Complexity of Inner Product and Determinant 14:00 May 7 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. 9 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 9:30 Mar. 29 Room 446
Yajun Wang Algorithms for submodular matroid secretary problems 14:00 Mar. 7 Room 1234
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. 9 Room 1234
Jie Tang Social Influence Analysis in Large Social Networks 9:45, Jan. 4 Room 446

Schedule for Fall 2012

Speaker Topic Time Location
Liwei Wang Margin theories for machine learning 14:00, Dec. 13 Room 446
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. 6 Room 1234
Pingzhong Tang Optimal Mechanism Design: Computation and Economics 10:00, Dec. 4 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
Minming Li DVS scheduling for various processor models and task types 10:00, Sept. 27 Room 1234
David Woodruff Low Rank Approximation and Regression in Input Sparsity Time 14:00, Sept. 11 Room 1234
David Woodruff Sketching Techniques for Numerical Linear Algebra 14:00, Sept. 6 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 9: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. 8 Room 1234
Xiaoming Sun Communication Complexity 9: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. 6 Room 440
Lei Nie Which Networks Are Least Susceptible to Cascading Failures 14:00, Oct. 29 Room 1234