Title: On the Perceptron Rescaling Algorithm

The perceptron algorithm is not a polynomial time algorithm to solve linear inequality systems, as its complexity depends on r^{-2}, where r is the radius of the largest inscribed ball. However, as Dunagan and Vempala showed, combined with an iterative re-scaling algorithms, with high probability the largest inscribed ball can be inflated sufficiently to reach polynomial solvability.
In this talk we discuss how to extend the rescaling idea to improve the complexity of the von Neumann algorithm. Upon successful completion of that project, the road open to improve the complexity of the colourful feasibility problem, as the B�r�ny-Onn algorithms can be interpreted as generalizations of the von Neumann algorithm.
Finally, various properties and parallelizablity of the re-scaling phase is analyzed in this talk.
Joint work with Dan Li