7 citations · 8 across the 4 of their papers we have counts for
Showing 2007Show all
2 papers · 1 filter
cs.CC2007
Interpolation in Valiant's theory
Pascal Koiran, Sylvain Perifel
We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit…
cs.DM2007
On the expressive power of planar perfect matching and permanents of bounded treewidth matrices
Laurent Lyaudet, Pascal Koiran, Uffe Flarup
Valiant introduced some 25 years ago an algebraic model of computation along with the complexity classes VP and VNP, which can be viewed as analogues of the classical classes P and…