Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Daniel Reichman:

TR24-025 | 13th February 2024
Mason DiCicco, Vladimir Podolskii, Daniel Reichman

Nearest Neighbor Complexity and Boolean Circuits

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

TR15-132 | 13th August 2015
Daniel Reichman, Igor Shinkar

On Percolation and NP-Hardness

Revisions: 2

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

TR04-119 | 8th December 2004
Uriel Feige, Daniel Reichman

On The Hardness of Approximating Max-Satisfy

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

ISSN 1433-8092 | Imprint