Paper 2020/002

On a Conjecture of O'Donnell

Qichun Wang

Abstract

Let be with total degree , and be the linear Fourier coefficients of . The relationship between the sum of linear coefficients and the total degree is a foundational problem in theoretical computer science. In 2012, O'Donnell Conjectured that In this paper, we prove that the conjecture is equivalent to a conjecture on the cryptographic Boolean function. We then prove that the conjecture is true for . Moreover, we count the number of 's such that the upper bound is achieved.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Boolean functionLinear coefficientTotal degreeResiliency
Contact author(s)
qcwang @ fudan edu cn
History
2020-01-03: received
Short URL
https://ia.cr/2020/002
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/002,
      author = {Qichun Wang},
      title = {On a Conjecture of O'Donnell},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/002},
      year = {2020},
      url = {https://eprint.iacr.org/2020/002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.