8 citations · 11 across the 4 of their papers we have counts for
4 papers
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
Oded Goldreich, Avi Wigderson
A graph is called self-ordered (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from to any graph that i…
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model
Oded Goldreich
In a recent work (ECCC, TR18-171, 2018), we introduced models of testing graph properties in which, in addition to answers to the usual graph-queries, the tester obtains {\em rando…
Finding Cycles and Trees in Sublinear Time
Artur Czumaj, Oded Goldreich, Dana Ron +3
We present sublinear-time (randomized) algorithms for finding simple cycles of length at least and tree-minors in bounded-degree graphs. The complexity of these algorithm…
The Random Oracle Methodology, Revisited
Ran Canetti, Oded Goldreich, Shai Halevi
We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing…