Algorithm & Complexity Group
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$.
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$.