All reports by Author David Woodruff:

__
TR18-103
| 30th April 2018
__

Zhao Song, David Woodruff, Peilin Zhong#### Relative Error Tensor Low Rank Approximation

__
TR15-083
| 14th May 2015
__

Omri Weinstein, David Woodruff#### The Simultaneous Communication of Disjointness with Applications to Data Streams

__
TR15-031
| 2nd March 2015
__

Marco Molinaro, David Woodruff, Grigory Yaroslavtsev#### Amplification of One-Way Information Complexity via Codes and Noise Sensitivity

Revisions: 1

Zhao Song, David Woodruff, Peilin Zhong

We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-$q$ tensor $A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$ tensor $B$ for which $\|A-B\|_F^2 \leq (1+\epsilon) {\rm OPT}$, where ${\rm OPT} = \inf_{\textrm{rank-}k~A'} \|A-A'\|_F^2$. Despite much success on obtaining relative error low ... more >>>

Omri Weinstein, David Woodruff

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then $\Omega(n \min(\log 1/\delta, \log ... more >>>

Marco Molinaro, David Woodruff, Grigory Yaroslavtsev

We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes ... more >>>