On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth

Uffe Flarup, Laurent Lyaudet

Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with…