Counting balanced Boolean functions in n variables with bounded degree

Thomas W. Cusick; Younhwan Cheon

doi:10.1080/10586458.2007.10128984

Counting balanced Boolean functions in n variables with bounded degree

Thomas W. Cusick
, Younhwan Cheon

Mathematics

Korea Army Academy at Young-Cheon

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

We consider the problem of obtaining good upper and lower bounds on the number of balanced Boolean functions in n variables with degree less than or equal to k. This is the same as the problem of finding bounds on the number of codewords of weight 2ⁿ⁻¹ in the Reed–Muller code of length 2ⁿ and order k. We state several conjectures and use them to obtain good bounds. We believe that the conjectures will be highly useful for further research.

Original language	English
Pages (from-to)	101-105
Number of pages	5
Journal	Experimental Mathematics
Volume	16
Issue number	1
DOIs	https://doi.org/10.1080/10586458.2007.10128984
State	Published - 2007

Keywords

Balanced
Boolean functions
Reed-Muller codes

Access to Document

10.1080/10586458.2007.10128984

Cite this

@article{a048bf8db8864950b867a845a1b90072,

title = "Counting balanced Boolean functions in n variables with bounded degree",

abstract = "We consider the problem of obtaining good upper and lower bounds on the number of balanced Boolean functions in n variables with degree less than or equal to k. This is the same as the problem of finding bounds on the number of codewords of weight 2n−1 in the Reed–Muller code of length 2n and order k. We state several conjectures and use them to obtain good bounds. We believe that the conjectures will be highly useful for further research.",

keywords = "Balanced, Boolean functions, Reed-Muller codes",

author = "Cusick, \{Thomas W.\} and Younhwan Cheon",

year = "2007",

doi = "10.1080/10586458.2007.10128984",

language = "English",

volume = "16",

pages = "101--105",

journal = "Experimental Mathematics",

issn = "1058-6458",

publisher = "Taylor and Francis Ltd.",

number = "1",

}

TY - JOUR

T1 - Counting balanced Boolean functions in n variables with bounded degree

AU - Cusick, Thomas W.

AU - Cheon, Younhwan

PY - 2007

Y1 - 2007

N2 - We consider the problem of obtaining good upper and lower bounds on the number of balanced Boolean functions in n variables with degree less than or equal to k. This is the same as the problem of finding bounds on the number of codewords of weight 2n−1 in the Reed–Muller code of length 2n and order k. We state several conjectures and use them to obtain good bounds. We believe that the conjectures will be highly useful for further research.

AB - We consider the problem of obtaining good upper and lower bounds on the number of balanced Boolean functions in n variables with degree less than or equal to k. This is the same as the problem of finding bounds on the number of codewords of weight 2n−1 in the Reed–Muller code of length 2n and order k. We state several conjectures and use them to obtain good bounds. We believe that the conjectures will be highly useful for further research.

KW - Balanced

KW - Boolean functions

KW - Reed-Muller codes

UR - https://www.scopus.com/pages/publications/34249326587

U2 - 10.1080/10586458.2007.10128984

DO - 10.1080/10586458.2007.10128984

M3 - Article

AN - SCOPUS:34249326587

SN - 1058-6458

VL - 16

SP - 101

EP - 105

JO - Experimental Mathematics

JF - Experimental Mathematics

IS - 1

ER -

Counting balanced Boolean functions in n variables with bounded degree

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this