A Paturi Theorem for Signed Subcube Representations

Hangyu liu

We obtain exponential upper bounds on approximate generalized weight and generalized sparsity in terms of the deepest transition depth D(F), and show that these bounds are optimal…