
PreviousNext
The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))
is very complicated.
One source of difficulty is the technically involved
analysis of low-degree tests.
Here, we refer to the difficulty of obtaining strong results
regarding low-degree tests; namely, results of the type obtained and
used by ...
more >>>
We consider the Traveling Salesperson Problem (TSP) restricted
to Euclidean spaces of dimension at most k(n), where n is the number of
cities. We are interested in the relation between the asymptotic growth of
k(n) and the approximability of the problem. We show that the problem is ...
more >>>
We study EP, the subclass of NP consisting of those
languages accepted by NP machines that when they accept always have a
number of accepting paths that is a power of two. We show that the
negation equivalence problem for OBDDs (ordered binary decision
diagrams) ...
more >>>
PreviousNext