Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GUY GOLDBERG:
All reports by Author Guy Goldberg:

TR21-146 | 19th October 2021
Guy Goldberg, Guy Rothblum

Sample-Based Proofs of Proximity

Revisions: 1

Suppose we have random sampling access to a huge object, such as a graph or a database.
Namely, we can observe the values of \emph{random} locations in the object, say random records in the database or random edges in the graph.
We cannot, however, query locations of our choice. Can ... more >>>




ISSN 1433-8092 | Imprint