All reports by Author Yonatan Bilu:

__
TR09-057
| 23rd June 2009
__

Yonatan Bilu, Nathan Linial#### Are stable instances easy?

__
TR02-003
| 24th December 2001
__

Eli Ben-Sasson, Yonatan Bilu#### A Gap in Average Proof Complexity

Yonatan Bilu, Nathan Linial

We introduce the notion of a stable instance for a discrete

optimization problem, and argue that in many practical situations

only sufficiently stable instances are of interest. The question

then arises whether stable instances of NP--hard problems are

easier to solve. In particular, whether there exist algorithms

that solve correctly ...
more >>>

Eli Ben-Sasson, Yonatan Bilu

We present the first example of a natural distribution on instances

of an NP-complete problem, with the following properties.

With high probability a random formula from this

distribution (a) is unsatisfiable,

(b) has a short proof that can be found easily, and (c) does not have a short

(general) resolution ...
more >>>