Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Erasures vs. Errors:
TR18-195 | 18th November 2018
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

Erasures versus Errors in Local Decoding and Property Testing

Revisions: 1

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>

TR22-075 | 21st May 2022
Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

ISSN 1433-8092 | Imprint