This paper presents robust solutions to least-squares problems with uncertain data. The authors consider least-squares problems where the coefficient matrices A and b are unknown but bounded. They minimize the worst-case residual error using convex second-order cone programming (SOCP), yielding an algorithm with complexity similar to one singular value decomposition of A. The method can be interpreted as a Tikhonov regularization procedure, with the advantage that it provides an exact bound on the robustness of the solution and a rigorous way to compute the regularization parameter. When the perturbation has a known structure, the same problem can be solved in polynomial time using semidefinite programming (SDP). The authors also consider the case when A and b are rational functions of an unknown-but-bounded perturbation vector. They show how to minimize upper bounds on the optimal worst-case residual using SDP. Numerical examples, including one from robust identification and one from robust interpolation, are provided. Key words: least-squares problems, uncertainty, robustness, second-order cone programming, semidefinite programming, ill-conditioned problem, regularization, robust identification, robust interpolation. The paper discusses the robust least squares (RLS) problem, which is to compute the worst-case residual for a given x. The authors show that the worst-case residual can be computed using SOCP or SDP. They also consider the structured RLS (SRLS) problem, which is to compute the worst-case residual for a given x when the perturbation has a known structure. The authors show that the SRLS problem can be solved in polynomial time using SDP. They also consider the linear-fractional SRLS problem, which is a generalization of the SRLS problem where the matrix functions A(δ) and b(δ) depend rationally on the parameter vector δ. The authors show that the linear-fractional SRLS problem is NP-complete, but upper bounds on the worst-case residual can be computed using SDP. The paper also discusses the link between RLS and regularization methods for standard least-squares problems. The authors show that the RLS solution can be interpreted as a Tikhonov regularization technique for ill-conditioned least-squares problems. The RLS solution is continuous in the data matrices A and b, and the regularization parameter is optimal for robustness. The authors also show that the SRLS solution is continuous in the data matrices A and b. The paper concludes with numerical examples, including one from robust identification and one from robust interpolation.This paper presents robust solutions to least-squares problems with uncertain data. The authors consider least-squares problems where the coefficient matrices A and b are unknown but bounded. They minimize the worst-case residual error using convex second-order cone programming (SOCP), yielding an algorithm with complexity similar to one singular value decomposition of A. The method can be interpreted as a Tikhonov regularization procedure, with the advantage that it provides an exact bound on the robustness of the solution and a rigorous way to compute the regularization parameter. When the perturbation has a known structure, the same problem can be solved in polynomial time using semidefinite programming (SDP). The authors also consider the case when A and b are rational functions of an unknown-but-bounded perturbation vector. They show how to minimize upper bounds on the optimal worst-case residual using SDP. Numerical examples, including one from robust identification and one from robust interpolation, are provided. Key words: least-squares problems, uncertainty, robustness, second-order cone programming, semidefinite programming, ill-conditioned problem, regularization, robust identification, robust interpolation. The paper discusses the robust least squares (RLS) problem, which is to compute the worst-case residual for a given x. The authors show that the worst-case residual can be computed using SOCP or SDP. They also consider the structured RLS (SRLS) problem, which is to compute the worst-case residual for a given x when the perturbation has a known structure. The authors show that the SRLS problem can be solved in polynomial time using SDP. They also consider the linear-fractional SRLS problem, which is a generalization of the SRLS problem where the matrix functions A(δ) and b(δ) depend rationally on the parameter vector δ. The authors show that the linear-fractional SRLS problem is NP-complete, but upper bounds on the worst-case residual can be computed using SDP. The paper also discusses the link between RLS and regularization methods for standard least-squares problems. The authors show that the RLS solution can be interpreted as a Tikhonov regularization technique for ill-conditioned least-squares problems. The RLS solution is continuous in the data matrices A and b, and the regularization parameter is optimal for robustness. The authors also show that the SRLS solution is continuous in the data matrices A and b. The paper concludes with numerical examples, including one from robust identification and one from robust interpolation.