5 citations · 5 across the 3 of their papers we have counts for
4 papers
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Fernando Granha Jeronimo, Pei Wu
Quantum entanglement is a fundamental property of quantum mechanics and plays a crucial role in quantum computation and information. We study entanglement via the lens of computati…
An Optimal Separation of Randomized and Quantum Query Complexity
Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order sum to at most $c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}…
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
Alexander A. Sherstov, Pei Wu
The threshold degree of a Boolean function is the minimum degree of a real polynomial that represents in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}…
Negative type diversities, a multi-dimensional analogue of negative type metrics
Pei Wu, David Bryant, Paul F. Tupper
Diversities are a generalization of metric spaces in which a non-negative value is assigned to all finite subsets of a set, rather than just to pairs of points. Here we provide an…