
PreviousNext
A polynomial time approximation scheme (PTAS) for an optimization
problem $A$ is an algorithm that on input an instance of $A$ and
$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time
that is polynomial for each fixed $\epsilon$. Typical running times
are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ...
more >>>
We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family ...
more >>>
The study of the approximability properties of NP-hard
optimization problems has recently made great advances mainly due
to the results obtained in the field of proof checking. In a
recent breakthrough the APX-completeness of several important
optimization problems is proved, thus reconciling `two distinct
views of ...
more >>>
PreviousNext