All reports by Author Daniel Reichman:

__
TR24-025
| 13th February 2024
__

Mason DiCicco, Vladimir Podolskii, Daniel Reichman#### Nearest Neighbor Complexity and Boolean Circuits

__
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

Mason DiCicco, Vladimir Podolskii, Daniel Reichman

A nearest neighbor representation of a Boolean function $f$ is a set of vectors (anchors) labeled by $0$ or $1$ such that $f(x) = 1$ if and only if the closest anchor to $x$ is labeled by $1$. This model was introduced by Hajnal, Liu, and TurĂ¡n (2022), who studied ... more >>>

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