Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Guy Goldberg:

TR23-067 | 7th May 2023
Guy Goldberg

Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error

Revisions: 1

Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword.
Unlike standard (non-relaxed) decoders, a relaxed one is allowed to output a ``rejection'' symbol, indicating that the decoding failed.
To prevent the ... more >>>

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