I am curious if the following model was studied or has some obvious lower bounds:

We want to compute a polynomial $P(x_1,x_2, \dots , x_n)$. Suppose we have a graph G on $n$ nodes that we are going to call restriction graph. Now we will call a monomial $x_{i_1} \times x_{i_2} \times \dots \times x_{i_d}$ valid if no two variables form an edge in the restriction graph $G$:

$$x_{i_1} \times x_{i_2} \times \dots \times x_{i_d} \text{ is valid } \iff \forall a,b: \{x_{i_{a}},x_{i_b}\} \not\in E(G)$$

A polynomial is valid if all of its monomials are valid. We will call a circuit $G$-restricted if all the gates in $G$ compute valid polynomials. We will be only interested in $G$-restricted circuits for valid polynomials.

This model is a strict generalization of multilinear circuits: we can take $G$ to be a collection of loops. My questions are:

  • Was this model studied?
  • Are there any other classes of circuits that can be represented this way?
  • Are there any obvious lower bounds for $G$-restricted circuits for explicit polynomials (and explicit $G$)?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.