63 citations · 168 across the 57 of their papers we have counts for
13 papers · 1 filter
New Distinguishers for Negation-Limited Weak Pseudorandom Functions
Zhihuai Chen, Siyao Guo, Qian Li +2
We show how to distinguish circuits with negations (a.k.a -monotone functions) from uniformly random functions in $\exp\left(\tilde{O}\left(n^{1/3}k^{2/3}\right)\right)…
Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
Xiaoming Sun, Yufan Zheng
In this paper, we introduce the hybrid query complexity, denoted as , which is the minimal query number needed to compute , when a classical decision tree is al…
On the Degree of Boolean Functions as Polynomials over
Xiaoming Sun, Yuan Sun, Jiaheng Wang +3
Polynomial representations of Boolean functions over various rings such as and have been studied since Minsky and Papert (1969). From then on, they have…
Querying a Matrix through Matrix-Vector Products
Xiaoming Sun, David P. Woodruff, Guang Yang +1
We consider algorithms with access to an unknown matrix via matrix-vector products, namely, the algorithm chooses vectors $\mathbf{v}^1, \ldots, \math…
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…
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…