Title: Subgradient and Sampling Algorithms for L_1 Regression
Speaker: Ken Clarkson, Bell Labs
Host: S. Muthukrishnan
Time: March 7th, 11 AM, Core A. 

Given an n by d matrix A and an n-vector b, the L_1 regression problem 
is to find the vector x minimizing the sum of the absolute values of  
the vector Ax-b.  The running times of previous algorithms for this 
problem seem to either be exponential in the dimension d, or have a 
superlinear dependence on n, or depend on the bit complexity of the 
input.  I'll describe an algorithm needing O(n log n)d^O(1) time in the 
worst case to obtain an approximate solution, with an objective function 
value within a fixed ratio of optimum. Given epsilon>0, a solution whose 
value is within 1+epsilon of optimum can be obtained either by a 
deterministic algorithm using an additional O(n)(d/epsilon)^O(1) time, 
or by a Monte Carlo algorithm using an additional O((d/epsilon)^O(1)) 
time. The analysis of the randomized algorithm shows that weighted 
coresets exist for L_1 regression.  The algorithms use the ellipsoid 
method, the subgradient method, and random sampling.

-------------------------------------------------------------