We examine the computational complexity of the following problem: given an n-variate polynomial f and an m-variate polynomial g over some field F, determine whether there exists an (m x n) matrix A and an m-dimensional vector b such that f(x) = g(Ax + b). In other words, can the polynomial f be obtained by replacing each variable of g by an affine combination of the variables occurring in f? Many foundational problems such as the determinantal complexity of the permanent, the arithmetic complexity of matrix multiplication, the depth-three complexity of the determinant, etc are special instances of this problem. We first examine the complexity of this problem when A is required to be invertible and show that for many nice families of polynomials g, there is a randomized polynomial-time algorithm for this problem. We then remove the restriction that A has to be invertible and give efficient algorithms for some very restricted families of polynomials g.