Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author shafi goldwasser:

TR24-098 | 26th May 2024
Noga Amit, Orr Paradise, Guy Rothblum, shafi goldwasser

Models That Prove Their Own Correctness

Revisions: 2

How can we trust the correctness of a learned model on a particular input of interest? Model accuracy is typically measured $on\ average$ over a distribution of inputs, giving no guarantee for any fixed input. This paper proposes a theoretically-founded solution to this problem: to train $Self$-$Proving\ models$ that prove ... more >>>

TR11-136 | 12th October 2011
eran gat , shafi goldwasser

Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications

Revisions: 1

In this paper we introduce a new type of probabilistic search algorithm, which we call the
{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,
and to produce a correct and {\it unique} solution with high probability.
We argue the applicability of such algorithms ... more >>>

ISSN 1433-8092 | Imprint