Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DIMITRIS FOTAKIS:
All reports by Author Dimitris Fotakis:

TR98-049 | 10th July 1998
Dimitris Fotakis, Paul Spirakis

Random Walks, Conditional Hitting Sets and Partial Derandomization

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


TR98-031 | 4th May 1998
Dimitris Fotakis, Paul Spirakis

Graph Properties that Facilitate Travelling

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




ISSN 1433-8092 | Imprint