Qian Li

**Address:** Room 812, Institute of Computing Technology, CAS

No.6 Kexueyuan South Road, Zhongguancun

Haidian District, Beijing 100190, China

**Email:** liqian@ict.ac.cn

Research interests

Computational Complexity, Quantum Computing

Education

♦ Institute of Computing Technology, Chinese Academy of Sciences 2013 - Present

PhD Candidate in Theoretical Computer Science

Advisor: Xiaoming Sun

♦ Chongqing University 2009 - 2013

BS in Integrated Circuit Design and Integrated System

PhD Candidate in Theoretical Computer Science

Advisor: Xiaoming Sun

♦ Chongqing University 2009 - 2013

BS in Integrated Circuit Design and Integrated System

Research

♦ Qian Li, and Xiaoming Sun. **On the
Sensitivity of k-Uniform Hypergraph Properties. **
*To appear in 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017).*

**Summary: ** In a recent paper
Laszlo Babai conjectures that the sensitivity of any $k$-uniform hypergraph
property is at least $\Omega(n^{k/2})$, where $n$ is the number of vertices. By constructing a series of
hypergraph properties explicitly, we disprove this conjecture.

♦ Jia Zhang, Zheng Wang, Qian Li, Qiang Li, Xiaoming Sun, and Jialin Zhang.**Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising. **
*To appear in the 31st AAAI Conference on Artificial Intelligence (AAAI 2017).*

**Summary: ** In this work, we study the guaranteed delivery model which is widely used in online display advertising. Different from previous works which usually minimize the penalty of unsatisfied contracts and some other cost (e.g. representativeness), we propose the novel consumption minimization model, in which the primary objective is to minimize the user traffic consumed to satisfy all contracts. And we develop a near optimal method to deliver ads for users under this model.

♦ Qian Li, Xiaoming Sun, and Jialin Zhang.**On the Optimality of Tape Merge with Similar Size. **
*In The 27th International Symposium on Algorithms and Computation (ISAAC 2016). Invited to the special issue of ISAAC 2016.* $.M.(m,n)$, $/M.(m,n)$, $/M\backslash(m,n)$, $/M/(m,n)$, Program

**Summary: ** We consider the problem of merging sorted lists in the least number of binary comparisons. In this work, we improve the best known lower bound for the range where tape merge is optimal via Knuth's adversary method, moreover, we also show a limitation of this method.

♦ Qian Li, and Xiaoming Sun.**On the Mod Degree Complexity of Boolean Function.
** *Manuscript*

**Summary: ** In this paper, we investigate
a problem proposed by Parikshit Gopalan et al., which asks
whether the degree complexity of boolean functions is polynomially related to the
degree over the ring $\mathbb{Z}_m$, where $m$ is a composite number. Our results
include: (1) obtain some nontrivial equivalent forms; (2) solve this problem for
some special classes of functions; (2) prove a no-go theorem, explaining why
this problem is difficult to attack from the computational complexity point of
view.

♦ Kun He, Qian Li, and Xiaoming Sun.**A Tighter Relation between Sensitivity and Certificate Complexity.
** *Manuscript*

**Summary: ** The famous sensitivity conjecture asserts that sensitivity and certificate complexity are polynomially related. The best known upper bound of certificate complexity in terms of sensitivity is $bs(f)\leq C(f)\leq\max\{2^{s(f)-1}(s(f)-\frac{1}{3}),s(f)\}$. In this paper, we provide a tighter bound: $bs(f)\leq C(f)\leq(\frac{8}{9} + o(1))s(f)2^{s(f) - 1}$.

♦ Zhihuai Chen, Qian Li, Xiaoming Sun, Lirong Xia, and Jialin Zhang.**Approximate Single-Peakedness in Large
Elections.** *Manuscript*

**Summary: **
In this paper, we study approximating
single-peakedness of large, randomly-generated profiles. The main result is that we can
characterize all asymptotically optimal social axes under the Mallows model for
two case: the case where the dispersion parameter $\varphi$ is close to $0$, and
the case where $\varphi$ is close to $1$.

♦ Jia Zhang, Zheng Wang, Qian Li, Qiang Li, Xiaoming Sun, and Jialin Zhang.

♦ Qian Li, Xiaoming Sun, and Jialin Zhang.

♦ Qian Li, and Xiaoming Sun.

♦ Kun He, Qian Li, and Xiaoming Sun.

♦ Zhihuai Chen, Qian Li, Xiaoming Sun, Lirong Xia, and Jialin Zhang.