All reports by Author Shafi Goldwasser:

__
TR19-177
| 6th December 2019
__

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

__
TR19-135
| 2nd October 2019
__

Michel Goemans, Shafi Goldwasser, Dhiraj Holden#### Doubly-Efficient Pseudo-Deterministic Proofs

__
TR17-108
| 19th June 2017
__

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai#### Delegating Computation: Interactive Proofs for Muggles

Revisions: 1

__
TR17-105
| 14th June 2017
__

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

__
TR16-056
| 8th April 2016
__

Shafi Goldwasser, Dhiraj Holden#### On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances

__
TR15-208
| 26th December 2015
__

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

Revisions: 2

__
TR15-009
| 16th January 2015
__

Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan#### Aggregate Pseudorandom Functions and Connections to Learning

Revisions: 1

__
TR14-083
| 19th June 2014
__

Irit Dinur, Shafi Goldwasser, Huijia Lin#### The Computational Benefit of Correlated Instances

__
TR12-101
| 10th August 2012
__

Oded Goldreich, Shafi Goldwasser, Dana Ron#### On the possibilities and limitations of pseudodeterministic algorithms

__
TR12-010
| 5th February 2012
__

Shafi Goldwasser, Guy Rothblum#### How to Compute in the Presence of Leakage

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

Michel Goemans, Shafi Goldwasser, Dhiraj Holden

In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>>

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a ``muggle'' (Muggle: ``In the fiction of J.K. Rowling: a person who possesses no magical powers''; from the Oxford English Dictionary). The verifier should be ... 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, Dhiraj Holden

We set out to study the impact of having access to correlated instances on the fine grained complexity of polynomial time problems, which have notoriously resisted improvement.

In particular, we show how to use a logarithmic number of auxiliary correlated instances to obtain $o(n^2)$ time algorithms for the longest common ...
more >>>

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

Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries'' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values belonging to an exponential-sized interval, or the sum of all ... more >>>

Irit Dinur, Shafi Goldwasser, Huijia Lin

The starting point of this paper is that instances of computational problems often do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. The challenge is how to gain computationally from instance correlations when they exist. We will be interested ... more >>>

Oded Goldreich, Shafi Goldwasser, Dana Ron

We study the possibilities and limitations

of pseudodeterministic algorithms,

a notion put forward by Gat and Goldwasser (2011).

These are probabilistic algorithms that solve search problems

such that on each input, with high probability, they output

the same solution, which may be thought of as a canonical solution.

We consider ...
more >>>

Shafi Goldwasser, Guy Rothblum

We address the following problem: how to execute any algorithm P, for an unbounded number of executions, in the presence of an adversary who observes partial information on the internal state of the computation during executions. The security guarantee is that the adversary learns nothing, beyond P's input/output behavior.

This ... more >>>