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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.