13 citations · 39 across the 25 of their papers we have counts for
6 papers · 1 filter
How to Verify Probabilistic Consistency of Predictive Models
Orr Paradise, Oliver Richardson, Yoshua Bengio +1
When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of intere…
Pseudo-deterministic Streaming
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty +1
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. Clas…
Doubly-Efficient Pseudo-Deterministic Proofs
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…
Fine-grained Complexity Meets IP = PSPACE
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu +2
In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from exact to approximat…
Pseudo-deterministic Proofs
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 sam…
On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner
Shafi Goldwasser
Madhu Sudan's work spans many areas of computer science theory including computational complexity theory, the design of efficient algorithms, algorithmic coding theory, and the the…