All reports by Author David Woodruff:

__
TR19-177
| 6th December 2019
__

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff#### Pseudo-deterministic Streaming

__
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

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff

A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, $\ell_2$ approximation, finding a nonzero entry in a vector (for turnstile algorithms) ... more >>>

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