Regression in lp-norm is a canonical problem in optimization, machine learning and theoretical computer science which asks for a vector with minimum lp-norm in a linear subspace. In this thesis, we give fast, high-accuracy algorithms for lp regression for all pgreater than 2. Our algorithms are built on novel techniques including iterative refinement for lp-norms, and a fast width-reduced multiplicative weight update routine among others. Furthermore, via a new inverse maintenance scheme, we can solve lp-regression almost as fast as linear regression for all p greater than 2. For graph instances, where the goal is to optimize lp-norm objectives (flow or voltages), our algorithms incorporate sparsification routines that preserve such objectives, to obtain near-linear-time algorithms. As a consequence, we also obtain a fast algorithm for the maximum flow problem in unweighted graphs. A popular approach to fast algorithms for lp-regression in practice is via empirical modifications of the {Iteratively Reweighted Least Squares (IRLS)} algorithm since the basic version of IRLS is known to converge only for p in (1, 3) and diverge even for moderate p (e.g., p > 3.5). We give the first IRLS algorithm that provably converges to a high accuracy solution in a few iterations. Our algorithm has shown exemplary practical performance as well beating standard MATLAB CVX implementations by 10-50x. We further extend our techniques to obtain fast algorithms for Quasi-self-concordant (QSC) functions, which includes lp-regression, softmax regression, and logistic regression among others. We show how iterative refinement and width reduction techniques extend and give fast rates of convergence for all QSC functions.