A comparison of Zeroes and Ones of a Boolean Polynomial
<|reference_start|>A comparison of Zeroes and Ones of a Boolean Polynomial: In this paper we consider the computational complexity of the following problem. Let $f$ be a Boolean polynomial. What value of $f$, 0 or 1, is taken more frequently? The problem is solved in polynomial time for polynomials of degrees 1,2. The next case of degree 3 appears to be PP-complete under polynomial reductions in the class of promise problems. The proof is based on techniques of quantum computation.<|reference_end|>
@article{vyalyi2001a,
    title={A comparison of Zeroes and Ones of a Boolean Polynomial},
    author={M. N. Vyalyi},
    journal={arXiv preprint arXiv:cs/0111052},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0111052},
    primaryClass={cs.CC}
}