In this paper we present an efficient new approach for addressing two-view minimal-case problems in camera motion estimation, most notably the so-called five-point relative orientation, and the six-point focal-length problem. Our approach is based on the hidden variable technique for solving multivariate polynomial systems. The resulting algorithm is conceptually simple, which involves a relaxation which replaces monomials in all but one of the variables to reduce the problem to the solution of sets of linear equations, and finding the solution of a polynomial eigenvalue problem. To actually solve the polynomial eigenvalues efficiently, we make novel use of several numeric techniques, which include quotient-free Gaussian elimination, Levinson-Durbin iteration, as well as a dedicated root-polishing procedure. We have tested the approach on different minimal cases and extensions, with very satisfactory results obtained. Both executables and source codes of the proposed algorithms are made online and freely downloadable.