Blum-Luby-Rubinfeld linearity test
GPTKB entity
Statements (18)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
property testing algorithm
|
| gptkbp:alsoKnownAs |
BLR test
|
| gptkbp:field |
theoretical computer science
property testing |
| gptkbp:hasConcept |
queries function at random points to check linearity
|
| https://www.w3.org/2000/01/rdf-schema#label |
Blum-Luby-Rubinfeld linearity test
|
| gptkbp:introduced |
gptkb:Manuel_Blum
gptkb:Michael_Luby gptkb:Ronitt_Rubinfeld |
| gptkbp:introducedIn |
1990
|
| gptkbp:publisher |
gptkb:Self-Testing/Correcting_with_Applications_to_Numerical_Problems_(STOC_1990)
|
| gptkbp:purpose |
test linearity of Boolean functions
|
| gptkbp:queryComplexity |
constant
|
| gptkbp:relatedTo |
gptkb:PCP_theorem
gptkb:probabilistically_checkable_proofs error-correcting codes |
| gptkbp:bfsParent |
gptkb:Michael_Luby
|
| gptkbp:bfsLayer |
5
|