63 citations · 168 across the 57 of their papers we have counts for
6 papers · 1 filter
On the Relationship between Energy Complexity and other Boolean Function Measures
Xiaoming Sun, Yuan Sun, Kewen Wu +1
In this work we investigate into energy complexity, a Boolean function measure related to circuit complexity. Given a circuit over the standard basis $\{\vee_2,\wedge…
Coreness of Cooperative Games with Truncated Submodular Profit Functions
Wei Chen, Xiaohan Shan, Xiaoming Sun +1
Coreness represents solution concepts related to core in cooperative games, which captures the stability of players. Motivated by the scale effect in social networks, economics and…
Quantum Advantages in Hypercube Game
Xiaoyu He, Kun Fang, Xiaoming Sun +1
We introduce a novel generalization of the Clauser-Horne-Shimony-Holt (CHSH) game to a multiplayer setting, i.e., Hypercube game, where all players are required to assign value…
Quantum Lovász Local Lemma: Shearer's Bound is Tight
Kun He, Qian Li, Xiaoming Sun +1
The Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all bad events under some weakly dependent conditio…
Higher order monotonicity and submodularity of influence in social networks: from local to global
Wei Chen, Qiang Li, Xiaohan Shan +2
Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity imply global monotoni…
Exact quantum query complexity of weight decision problems via Chebyshev polynomials
Xiaoyu He, Xiaoming Sun, Guang Yang +1
The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding…