-
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... -
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...
