The Covering Radius of the Reed-Muller Code RM(m - 4, m) in RM(m - 3, m)

We present methods for computing the distance from a Boolean polynomial on m variables of degree m-3 (i.e., a member of the Reed-Muller code RM(m-3, m) ) to the space of lower-degree polynomials ( RM(m-4, m) ). The methods give verifiable certificates for both the lower and upper bounds on this...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2022-01, Vol.68 (1), p.560-571
Main Authors: Dougherty, Randall, Mauldin, R. Daniel, Tiefenbruck, Mark
Format: Article
Language:English
Subjects:
Boolean algebra
Boolean functions
certificate
Codes
covering radius
Input variables
Lower bounds
minimum weight
nonlinearity
Polynomials
Reed-Muller codes
Reed–Muller code
resilient
Terminology
Upper bound
Upper bounds
Web sites
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present methods for computing the distance from a Boolean polynomial on m variables of degree m-3 (i.e., a member of the Reed-Muller code RM(m-3, m) ) to the space of lower-degree polynomials ( RM(m-4, m) ). The methods give verifiable certificates for both the lower and upper bounds on this distance. By applying these methods to representative lists of polynomials, we show that the covering radius of RM(4,8) in RM(5,8) is 26 and the covering radius of RM(5,9) in RM(6,9) is between 28 and 32 inclusive, and we get improved lower bounds for higher m . We also apply our methods to various polynomials in the literature, thereby improving the known bounds on the distance from 2-resilient polynomials to RM(m-4, m) .
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2021.3120754