Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Yonatan Bilu:

TR09-057 | 23rd June 2009
Yonatan Bilu, Nathan Linial

Are stable instances easy?

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

TR02-003 | 24th December 2001
Eli Ben-Sasson, Yonatan Bilu

A Gap in Average Proof Complexity

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

ISSN 1433-8092 | Imprint