Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields

Bin Fu, Yunhui Fu

We study exact representations of explicit signed modular predicates on $\{-1,1{\}}^n$ as products of bounded-degree polynomials over prime fields, measured by total variable-occurre…