All reports by Author Dimitris Fotakis:

__
TR98-049
| 10th July 1998
__

Dimitris Fotakis, Paul Spirakis#### Random Walks, Conditional Hitting Sets and Partial Derandomization

__
TR98-031
| 4th May 1998
__

Dimitris Fotakis, Paul Spirakis#### Graph Properties that Facilitate Travelling

Dimitris Fotakis, Paul Spirakis

In this work we use random walks on expanders in order to

relax the properties of hitting sets required for partially

derandomizing one-side error algorithms. Building on a well-known

probability amplification technique [AKS87,CW89,IZ89], we use

random walks on expander graphs of subexponential (in the

random bit complexity) size so as ...
more >>>

Dimitris Fotakis, Paul Spirakis

In this work, we study two special cases of the metric Travelling Salesman

Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of

TSP(1,2) and Graph TSP are essentially as hard to approximate as general

instances of TSP(1,2).

Next, we present an NC algorithm for TSP(1,2) that ... more >>>