Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Elad Hazan:

TR07-088 | 7th September 2007
Elad Hazan, C. Seshadhri

Adaptive Algorithms for Online Decision Problems

Revisions: 1

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 >>>

TR06-033 | 2nd March 2006
Amit Agarwal, Elad Hazan

Efficient Algorithms for Online Game Playing and Universal Portfolio Management

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 >>>

TR05-058 | 24th May 2005
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

On Non-Approximability for Quadratic Programs

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 >>>

TR03-020 | 27th March 2003
Elad Hazan, Shmuel Safra, Oded Schwartz

On the Hardness of Approximating k-Dimensional Matching

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 >>>

ISSN 1433-8092 | Imprint