<p>The definition in [Arora, Barak] is the usual definition in <em>algebraic</em> 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. <a href="https://people.cs.rutgers.edu/%7Eallender/papers/niszkl.pdf" rel="noreferrer">https://people.cs.rutgers.edu/~allender/papers/niszkl.pdf</a>), the term &quot;projection&quot; is used in the sense that you surmised: which is to say, inputs can be negated.</p>
<p>Thus, in a monotone projection, negated inputs would not be allowed.  For instance, see <a href="https://eccc.weizmann.ac.il/report/2023/069" rel="noreferrer">https://eccc.weizmann.ac.il/report/2023/069</a></p>

CC BY-SA 4.0
2023-09-30T03:23:44.463Z
2023-09-30T03:23:44.463Z
Eric Allender
<p>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.</p>
<p>My understanding is that a Boolean function <span class="math-container">$f(x_1, \dots, x_n)$</span> is a <em>projection</em> of <span class="math-container">$g(y_1, \dots, y_m)$</span> if there is a mapping <span class="math-container">$\rho : \{y_1, \dots, y_m\} \to \{x_1, \dots, x_n, 0, 1 \}$</span> that &quot;rewires&quot; the inputs, such that <span class="math-container">$f(x_1, \dots, x_n) = g(\rho(y_1), \dots, \rho(y_m))$</span>. 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).</p>
<p>Now, I've recently encountered the term <em>monotone</em> 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.</p>
<p>Is there a good reference discussing different types of reductions between Boolean functions in the context of circuit complexity?</p>

CC BY-SA 4.0
2022-12-03T14:37:12.047Z
Where did you encounter the term monotone projection?
Reijo Jaakkola
<circuit-complexity><boolean-functions><monotone>
Reductions and projections in circuit complexity
Noel Arteche
# Reductions and projections in circuit complexity

(Asked by: username_0 on 2022-12-02)

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?

**Tags:** circuit-complexity, boolean-functions, monotone
> **Comments:**
> **username_1**: Where did you encounter the term monotone projection?  

---

## 1 answers

### Answer by username_2 on 2023-09-30. Score: 5 | Accepted answer

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](https://people.cs.rutgers.edu/%7Eallender/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>


---

