-
Arithmetic circuits: the chasm at depth four gets wider
In their paper on the ''chasm at depth four'', Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size... -
Representations of polynomials, algorithms and lower bounds
Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory... -
A quadratic bound for the determinant and permanent problem.
International audience -
Polynomials and coefficients
Valiant defines algebraic analogues of the classes P and NP. We characterize the classes VP and VQP, yielding a simplified proof of VNP = VNPe and of the... -
Graphs and hypergraphs : algorithmic and algebraic complexities
Beware, this abstract comports irony and humor. In this dissertation, we defend the idea that, for any reasonnable model of computation, this is not the model that is...
