2016, ESA 2016,ICALP 2015, FOCS 2015,ISAAC 2014, WINE 2014 (co-Chair for Poster track), TAMC 2013, STOC 2013,CATS 2012, ICALP 2012, FAW-AAIM 2012 (PC
co-Chair), FAW-AAIM 2011, COCOON 2011, WINE 2011,FAW
Current and Past PhD Student:
- Chihao Zhang (Shanghai Jiao
Tong University,now at The Chinese University of Hong Kong)
- Tao Xiao(Shanghai Jiao
Tong University, co-advised with Xiaotie Deng)
- Chao Liao (Shanghai Jiao
Students at MSRA:
Guangda HuZhang, Yumeng Zhang, Lingxiao Huang, Kuan Yang, Tao Xiao, Zhengyang Liu, Jingcheng Liu, Menghui Wang, Liang Li, Bo Tang, Xue Chen, Nick Gravin, Zeyuan Zhu, Sangxia Huang, Lei Wang, Yuan Zhou
My DBLP Site
- FPTAS for Counting Proper Four Colorings on Cubic Graphs. with Kuan Yang ,Chihao Zhang,and Minshen Zhu, SODA 2017.
- FPTAS for Hardcore and Ising Models on Hypergraphs. with Kuan Yang and Chihao Zhang, STACS 2016.
- Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems. with Heng Guo, RANDOM 2016.
Paths for MCMC: from Art to Science. with Lingxiao Huang and Chihao Zhang, SODA 2016.
for #BIS with Degree Bounds on One Side. with Jingcheng Liu, STOC 2015.
for Counting Monotone CNF. with Jingcheng Liu, SODA 2015.
for Counting Weighted Edge Covers. with Jingcheng Liu and Chihao Zhang, ESA 2014.
Complexity of Ferromagnetic Two-spin Systems with External Fields. with Jingcheng Liu and Chihao Zhang, RANDOM 2014.
for Weighted Fibonacci Gates and Its Applications. with Menghui Wang and Chihao Zhang, ICALP 2014.
Simple FPTAS for Counting Edge Covers. with Chengyu Lin and Jingcheng Liu, SODA 2014.
FPTAS for Multi-Spin Systems. with Yitong Yin, RANDOM 2013.
Complexity of Approximating Conservative Counting CSPs. with Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan and David Richerby,
Decay up to Uniqueness in Spin Systems. with Liang Li and Yitong Yin,
- Inapproximability After Uniqueness Phase Transition in Two-Spin Systems. with Jin-Yi Cai, Xi Chen and Heng Guo. COCOA 2012.
Counting via Correlation Decay in Spin Systems. with Liang Li and Yitong Yin,
Complexity of Counting Problems
for Holant* Problems with a Function on Domain
Size 3. with Jin-Yi Cai and Mingji Xia, SODA 2013.
- A Dichotomy
for Real Weighted Holant Problems. with Sangxia Huang, CCC 2012.
Complexity of Symmetric Boolean Parity Holant Problems. with Heng Guo and Leslie Valiant,
Weighted #CSPs: An Effective Complexity Dichotomy. with Jin-Yi Cai and Xi Chen, CCC 2011.
Complexity of Weighted Boolean #CSP Modulo k. with Heng Guo, Sangxia Huang and Mingji Xia, STACS 2011.
- Dichotomy for Holant* Problems of Boolean Domain. with Jin-Yi Cai and Mingji Xia, SODA
- From Holant To #CSP And Back:
Dichotomy For Holantc Problems. with Jin-Yi Cai and Sangxia Huang, ISAAC 2010. (Best Paper Award.)
Algorithms with Matchgates Capture Precisely
Tractable Planar #CSP. with Jin-Yi Cai and Mingji Xia, FOCS 2010.
- On Tractable
Exponential Sums. with Jin-Yi Cai, Xi Chen and
Richard Lipton, FAW 2010. (Best
- Graph Homomorphisms with Complex Values: A Dichotomy
Theorem. with Jin-Yi Cai and Xi Chen, ICALP
- Holant Problems and Counting CSP. with Jin-Yi Cai and Mingji Xia, STOC 2009.
Computational Proof of Complexity of Some Restricted Counting Problems. with Jin-Yi Cai and Mingji Xia, TAMC 2009.
Algorithmic Game Theory
Efficiency Guarantees in Auctions with Budgets. with Tao Xiao, EC 2015.
analysis via benchmark decomposition. with Ning Chen and Nick Gravin, EC 2015.
Competitive Auctions. with Ning Chen and Nick Gravin, STOC 2014.
Generalized Assignments via Stable Matching. with Ning Chen and Nick Gravin, Mathematics of Operations
of Truthful Mechanisms for One-dimensional Single Facility Location Game
with Payments. with Lan Yu, WINE 2013.
Auctions for Markets with Positive Externalities. with Nick Gravin, ICALP 2013.
Feasible Mechanism Design: From Prior-Free to Bayesian. with Xiaohui Bei, Ning Chen and Nick Gravin,
the Nucleolus of Matching, Cover and Clique Games. with Ning Chen and Hongyang Zhang, AAAI 2012.
the Approximation Ratio of k-lookahead Auction. with Xue Chen, Guangda Hu and Lei Wang, WINE 2011.
Pricing in Social Networks with Incomplete Information. with Wei Chen, Xiaorui Sun, Bo Tang, Yajun Wang and Zeyuan Allen Zhu, WINE 2011.
the Approximability of Budget Feasible
Mechanisms. with Ning
Chen and Nick Gravin, SODA 2011.
- Envy-free Pricing with General Supply Constraints. with Sungjin Im and Yajun Wang, WINE
Optimal Strategy-Proof Mechanisms for Two-Facility Games. with Xiaorui Sun, Yajun Wang and Zeyuan Allen
Zhu, EC 2010.
2-Player Randomized Mechanisms for Scheduling. WINE 2009.
Bounds for Facility Games. with Yajun Wang and Yuan
Zhou, WINE 2009.
Nash Equilibria in Restricted Routing. With Changyuan Yu, WINE 2008.
Truthful Mechanisms for Scheduling Unrelated Machines. With Changyuan Yu, WINE 2008.
- An Improved
Randomized Truthful Mechanism for Scheduling Unrelated Machines, with Changyuan Yu, STACS 2008.
Auctions with Optimal Profit. with Shang-Hua Teng and Changyuan Yu, WINE 2006.
Algorithms by Fibonacci Gates and Holographic Reductions for Hardness, with Jin-Yi Cai and Mingji Xia,
Algorithms with Unsymmetric Signatures,
with Jin-Yi Cai, SODA 2008.
Theory in Holographic Algorithms. with Jin-Yi. Cai, ISAAC 2008.
Block-wise Symmetric Signatures for Matchgates. with Jin-Yi Cai, FCT 2007.
Algorithms: The Power of Dimensionality Resolved. with Jin-Yi Cai, ICALP 2007. (Best Paper Award)
Algorithms: From Art to Science. with Jin-Yi Cai, STOC 2007.
Collapse in Holographic Algorithms. with Jin-Yi Cai, CCC 2007.
the Theory of Matchgate Computations. with Jin-Yi Cai and Vinay Choudhary, CCC
Symmetric Signatures in Holographic Algorithms. with Jin-Yi Cai, STACS 2007.
- Combinatorial Multi-Armed Bandit with General Reward Functions. with Wei Chen, Wei Hu,Fu Li ,Jian Li,Yu Liu, NIPS 2016.
Optimal Differentially Private Mechanisms for Count-Range Queries. with
Chen Zeng, Jin-Yi Cai,
and Jeffrey Naughton, ICDT 2013.
- Simulating Undirected st-Connectivity
Algorithms on Uniform JAGs and NNJAGs. with jialin zhang, Chung Keung
Poon, Jin-Yi Cai,