Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author David Woodruff:

TR18-103 | 30th April 2018
Zhao Song, David Woodruff, Peilin Zhong

Relative Error Tensor Low Rank Approximation

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 >>>

TR15-083 | 14th May 2015
Omri Weinstein, David Woodruff

The Simultaneous Communication of Disjointness with Applications to Data Streams

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 >>>

TR15-031 | 2nd March 2015
Marco Molinaro, David Woodruff, Grigory Yaroslavtsev

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint