  Strict linear feasibility or linear separation is usually tackled using
efficient approximation/stochastic algorithms (that may even run in sub-linear
times in expectation). However, today state of the art for solving
exactly/deterministically such instances is to cast them as a linear
programming instances. Inversely, this paper introduces a self-concordant
perceptron algorithm which tackles directly strict linear feasibility with
interior point paradigm. This algorithm has the same worse times complexity
than state of the art linear programming algorithms but it complexity can be
characterized more precisely eventually proving that it binary complexity is
low on a sub-family of linear feasibility.
