All reports by Author Elad Hazan:

__
TR07-088
| 7th September 2007
__

Elad Hazan, C. Seshadhri#### Adaptive Algorithms for Online Decision Problems

Revisions: 1

__
TR06-033
| 2nd March 2006
__

Amit Agarwal, Elad Hazan#### Efficient Algorithms for Online Game Playing and Universal Portfolio Management

__
TR05-058
| 24th May 2005
__

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra#### On Non-Approximability for Quadratic Programs

__
TR03-020
| 27th March 2003
__

Elad Hazan, Shmuel Safra, Oded Schwartz#### On the Hardness of Approximating k-Dimensional Matching

Elad Hazan, C. Seshadhri

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>

Amit Agarwal, Elad Hazan

A natural algorithmic scheme in online game playing is called `follow-the-leader', first proposed by Hannan in the 1950's. Simply stated, this method advocates the use of past history to make future predictions, by using the optimal strategy so far as the strategy for the next game iteration. Randomized variations on ... more >>>

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

This paper studies the computational complexity of the following type of

quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ...
more >>>

Elad Hazan, Shmuel Safra, Oded Schwartz

We study bounded degree graph problems, mainly the problem of

k-Dimensional Matching \emph{(k-DM)}, namely, the problem of

finding a maximal matching in a k-partite k-uniform balanced

hyper-graph. We prove that k-DM cannot be efficiently approximated

to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.

This ...
more >>>