We give an efficient structural decomposition theorem for formulas that depends on their negation complexity and demonstrate its power with the following applications:

-- We prove that every formula that contains $t$ negation gates can be shrunk using a random restriction to a formula of size $O(t)$ with the shrinkage exponent of monotone formulas. As a result, the shrinkage exponent of formulas that contain a constant number of negation gates is equal to the shrinkage exponent of monotone formulas.
-- We give an efficient transformation of formulas with $t$ negation gates to circuits with $\log{t}$ negation gates. This transformation provides a generic way to cast results for negation-limited circuits to the setting of negation-limited formulas. For example, using a result of Rossman (CCC '15), we obtain an average-case lower bound for formulas of polynomial-size on $n$ variables with $n^{1/2-\eps}$ negations.

In addition, we prove a lower bound on the number of negations required to compute one-way permutations by polynomial-size formulas.

Mostly a generalization of the techniques used resulting in a new result and better presentation.

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk using a random restriction to a formula of size $O(t)$ with the shrinkage exponent of monotone formulas. As a result, the shrinkage exponent of formulas that contain a constant number of negation gates is equal to the shrinkage exponent of monotone formulas. Moreover, we show that average-case lower bounds for monotone formulas can be extended to get average-case lower bounds for formulas with few negations. Using the average-case lower bound for polynomial-size monotone formulas of Rossman (CCC '15), we obtain an average-case lower bound for polynomial-size formulas with $n^{1/2-o(1)}$ negations, where $n$ is the input size.

Recently, circuits with few negations have drawn much attention in various areas of theoretical computer science. Specifically, Blais et al. (ECCC '14) studied the uniform-distribution learnability of circuits with few negations, and Guo et al. (TCC '15) proved lower bounds on the number of negations required to represent many cryptographic primitives as circuits. Following Guo et al., we study how many negations are required to implement cryptographic primitives using formulas, and provide lower bounds for pseudorandom functions, one-way permutations, hardcore predicates and extractors. In particular, we show that every formula that computes a one-way permutation on $n$ inputs must have $\omega(\log n)$ negations, and that any formula that computes a pseudorandom function on $n$ inputs must contain $\Omega(n)$ negations (which is optimal up to a constant factor). Following Blais et al., we show that formulas with $t$ negations can be learned as fast as circuits with $\log t$ negations.