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

Joseph Shunia

A deterministic primality test with a polynomial time complexity of $\tilde{O}(\log^3(n))$ is presented. The test posits that an integer $n$ satisfying the conditions of the main theorem is prime. Combining elements of number theory and combinatorics, the proof operates on the basis of simultaneous modular congruences relating to binomial transforms ... more >>>