63 citations · 168 across the 57 of their papers we have counts for
Showing 2019 · cs.CCShow all
3 papers · 2 filters
cs.CC2019★ 2 cited
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…
cs.CC2019
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…
cs.CC2019
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…