TIME: 1:30-2:20 pm,  October 17, 2006

PLACE: CSE 403

TITLE:  Multiplicative Weight Method: A general algorithmic tool (with 
applications to linear and semidefinite programming)

SPEAKER: Sanjeev Arora
         Princeton University
 

ABSTRACT:

Algorithms in a variety of disciplines use the idea of maintaining a 
distribution over a certain set and using the multiplicative weight 
update rule to update the distribution. Examples include approximation 
algorithms for packing-covering LPs, boosting in learning theory, 
portfolio management in finance, and the XOR lemma in cryptography. This 
talk surveys some of these applications, and describes new applications 
of such ideas to computing fast solutions to LPs and SDPs.