Theory Lunch Seminar

Wednesday, April 10, 2019 - 12:00pm to 1:00pm


4305 Newell-Simon Hall


DAVID WOODRUFF, Associate Professor

Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension

We obtain the first strong coresets for the k-median and subspace approximation problems with sum of distances objective function, on n points in d dimensions, with  a  number  of  weighted  points  that  is  independent  of both n and d; namely our coresets have size poly(k/eps). A strong  coreset (1+eps)-approximates  the  cost  function for all possible  sets  of  centers  simultaneously.  We  also  give input sparsity time algorithms for computing these coresets, which are fixed parameter tractable in k/eps.  We  obtain  the  result  by  introducing  a  new  dimensionality  reduction  technique  for  coresets  that  significantly generalizes earlier results for  squared  Euclidean  distances  to  sums  of p-th  powers  of  Euclidean  distances  for  constant p >= 1.

Joint work with Christian Sohler

Event Website:

For More Information, Contact:


Seminar Series