All reports by Author Daniel Reichman:

__
TR15-132
| 13th August 2015
__

Daniel Reichman, Igor Shinkar#### On Percolation and NP-Hardness

Revisions: 2

__
TR04-119
| 8th December 2004
__

Uriel Feige, Daniel Reichman#### On The Hardness of Approximating Max-Satisfy

Daniel Reichman, Igor Shinkar

We consider the robustness of computational hardness of problems

whose input is obtained by applying independent random deletions to worst-case instances.

For some classical NP-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary

graph are ...
more >>>

Uriel Feige, Daniel Reichman

Max-Satisfy is the problem of finding an assignment that satisfies

the maximum number of equations in a system of linear equations

over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no

polynomial time algorithm for the problem achieving an

approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number

of ...
more >>>