Reductions and projections in circuit complexity

Question

I'm struggling to find a good reference that defines the difference between projection and monotone projection in the context of Boolean functions and circuit complexity.

My understanding is that a Boolean function $f(x_1, \dots, x_n)$ is a projection of $g(y_1, \dots, y_m)$ if there is a mapping $\rho : \{y_1, \dots, y_m\} \to \{x_1, \dots, x_n, 0, 1 \}$ that "rewires" the inputs, such that $f(x_1, \dots, x_n) = g(\rho(y_1), \dots, \rho(y_m))$. This is, for example, the definition of projection reduction that Arora and Barak given in their textbook, in the context of algebraic circuit complexity (p. 325, Definition 16.10).

Now, I've recently encountered the term monotone projection, without definition. At first I thought that in regular projections one is allowed to map a variable to the negation of another variable, and that that would not be allowed in monotone projections, but looking at the previous definition, which seems to be standard, this is not the case, so I don't see what monotonicity could mean in this context.

Is there a good reference discussing different types of reductions between Boolean functions in the context of circuit complexity?

Answer 1

The definition in [Arora, Barak] is the usual definition in algebraic complexity (dating back to the work of Valiant). But in descriptive complexity theory (e.g. N. Immerman, Descriptive Complexity, Springer, Berlin, 1998) and in circuit complexity (such as in my own work, e.g. https://people.cs.rutgers.edu/~allender/papers/niszkl.pdf), the term "projection" is used in the sense that you surmised: which is to say, inputs can be negated.

Thus, in a monotone projection, negated inputs would not be allowed. For instance, see https://eccc.weizmann.ac.il/report/2023/069