All reports by Author Ofer Grossman:

__
TR20-038
| 15th March 2020
__

Ofer Grossman, Justin Holmgren#### Error Correcting Codes for Uncompressed Messages

__
TR19-185
| 6th December 2019
__

Greg Bodwin, Ofer Grossman#### Strategy-Stealing is Non-Constructive

__
TR19-177
| 6th December 2019
__

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

__
TR19-072
| 17th May 2019
__

Lijie Chen, Ofer Grossman#### Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators

__
TR18-048
| 11th March 2018
__

Ofer Grossman, Yang P. Liu#### Reproducibility and Pseudo-Determinism in Log-Space

__
TR17-105
| 14th June 2017
__

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden#### Pseudo-Deterministic Proofs

__
TR15-208
| 26th December 2015
__

Shafi Goldwasser, Ofer Grossman#### Perfect Bipartite Matching in Pseudo-Deterministic $RNC$

Revisions: 2

__
TR15-207
| 23rd December 2015
__

Ofer Grossman#### Finding Primitive Roots Pseudo-Deterministically

__
TR15-158
| 27th September 2015
__

Ofer Grossman, Dana Moshkovitz#### Amplification and Derandomization Without Slowdown

Ofer Grossman, Justin Holmgren

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We ... more >>>

Greg Bodwin, Ofer Grossman

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing.

This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing ...
more >>>

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

Lijie Chen, Ofer Grossman

Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) ... more >>>

Ofer Grossman, Yang P. Liu

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits ... more >>>

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where

the verifier is guaranteed with high probability to output the same output on different executions.

As in the case with classical interactive proofs,

the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

Shafi Goldwasser, Ofer Grossman

In this paper we present a pseudo-deterministic $RNC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly({\log n})$ depth, $poly(\log n)$ random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That ... more >>>

Ofer Grossman

Pseudo-deterministic algorithms are randomized search algorithms which output unique solutions (i.e., with high probability they output the same solution on each execution). We present a pseudo-deterministic algorithm that, given a prime $p,$ finds a primitive root modulo $p$ in time $\exp(O(\sqrt{\log p \log \log p}))$. This improves upon the previous ... more >>>

Ofer Grossman, Dana Moshkovitz

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms.

The ... more >>>