I am trying to understand the definition of skewed circuits in these slides which is given as follows:

A circuit is skew if in each product gate, at least one product has degree $\le 1$.

I think author wants to say that each product gate is either a leaf node or one level above the leaf node.


Skew arithmetic circuits are usually defined a bit differently: in every multiplication gate, one of the inputs of the gate is a constant or an input of the circuit (we assume that multiplication gates are binary).

This is very similar to your definition, if linear is interpreted as syntactically linear. That is, one of the inputs of any multiplication gate is either a constant, an input of the circuit, or the output of an addition gate whose inputs are inputs of the circuit or constants. Using the distributive rule, we can take a circuit satisfying this definition and turn it into a circuit satisfying the usual definition.

Another interpretation would be that one of the inputs of any multiplication gate is a linear function of the inputs, that is, it is semantically linear. For example, $(a+b)^2-(a-b)^2$ is semantically linear but not syntactically linear. This is probably not the interpretation which is meant here.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.