Lower Bounds on the PTF Weight of ODD-MAXBIT Function

摘要

We show that every polynomial threshold function thatsign-represents the ODD-MAXBIT function has total absolute weight2~(Ω( 1/3)) . The bound is tight up to a logarithmic factor in the exponent.