---

Title: Efficient Algorithms using the Multiplicative Weights Update method

Algorithms based on convex optimization, especially linear and semidefinite
programming, are ubiquitous in Computer Science. While there are polynomial
time algorithms known to solve such problems, quite often the running time of
these algorithms is very high. Designing simpler and more efficient algorithms
is important for practical impact.

In my talk, I  will describe applications of the Multiplicative Weights Update
method in the design of efficient algorithms for various optimization problems.
This method, which was repeatedly discovered in quite diverse fields, is an
algorithmic technique which maintains a distribution on a certain set of
interest, and updates it iteratively by multiplying the probability mass of
elements by suitably chosen factors based on the distribution.

The central result of my thesis is a generalization of the method to the setting of
symmetric matrices rather than real numbers. I will describe the following
applications of the resulting Matrix Multiplicative Weights algorithm:
  1. The first truly general, combinatorial, primal-dual method for designing
  efficient algorithms for semidefinite programming. Using these techniques, we
  obtain significantly faster algorithms for obtaining O(sqrt{log n})
  approximations to various graph partitioning problems, such as Sparsest
  Cut, Balanced Separator in both directed and undirected weighted graphs,
  and the Min UnCut problem.

  2. An O*(n^3) time derandomization of the Alon-Roichman construction of
  expanders using Cayley graphs.

  3. An O*(n^3) time deterministic O(log n) approximation algorithm for the
  quantum hypergraph covering problem.

  4. A simpler proof of a result of Aaronson that the gamma-fat-shattering
  dimension of quantum states on n qubits is O(n/gamma^2).

I will also briefly mention the following algorithmic applications of the classical
Multiplicative Weights Update method:
  1. Fast algorithms for approximately solving several families of semidefinite
  programs, which beat interior point methods.

  2. O(sqrt{log n}) approximation to the Sparsest Cut in graphs in O*(n^2) time.