2 Polynomials Over {0,1}

摘要

We have discussed the challenge of proving correlation bounds for polynomials. We have seen that winning this challenge is necessary for proving lower bounds such as "NP does not have quasipolynomial-size circuits," that a great deal is known for various settings of parameters, and that there are many interesting research directions. The clock is ticking ...