Yi Wu

most citedComputational Complexity of Certifying Restricted Isometry Property

5 citations · 8 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2015★ 1 cited

Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems

Alina Ene, Jan Vondrak, Yi Wu

We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate thes…

cs.CC2014★ 5 cited

Computational Complexity of Certifying Restricted Isometry Property

Abhiram Natarajan, Yi Wu

Given a matrix $A$ with $n$ rows, a number $k < n$ , and $0 < δ < 1$ , $A$ is $(k, δ)$ -RIP (Restricted Isometry Property) if, for any vector $x \in R^{n}$ , with at most $k$ non-zero…

cs.CC2014★ 2 cited

Optimal query complexity for estimating the trace of a matrix

Karl Wimmer, Yi Wu, Peng Zhang

Given an implicit $n \times n$ matrix $A$ with oracle access $x^{T} A x$ for any $x \in R^{n}$ , we study the query complexity of randomized algorithms for estimating the trace of…