Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a
randomized algorithm which, given the ability to make queries whether
a desired pair of vertices of an input graph $G$ with $n$ vertices are
adjacent or not, distinguishes, with high probability, between the
case of $G$ satisfying ... more >>>

A dichotomy theorem for a class of decision problems is
a result asserting that certain problems in the class
are solvable in polynomial time, while the rest are NP-complete.
The first remarkable such dichotomy theorem was proved by
T.J. Schaefer in 1978. It concerns the ... more >>>

In this paper we separate many-one reducibility from truth-table
reducibility for distributional problems in DistNP under the
hypothesis that P neq NP. As a first example we consider the
3-Satisfiability problem (3SAT) with two different distributions
on 3CNF formulas. We show that 3SAT using a version of the
standard distribution ... more >>>