Matching Smolensky's correlation bound with majority

摘要

We show that there are degree- d polynomials over F 2 with correlation ( d n ) with the majority function on n bits. This matches the O ( d n ) bound by Smolensky.