Note: Latex formulas below require Java Scripts enabled for this page, for and
Back to the root file of my research overview.

Some Other Work

Besides the above major areas of my interests, I have papers on various other issues. Here are some examples:

In [Yamnitsky, Levin 82] we studied A.Levin's 1965 version of Ellipsoid Algorithm (EA) which used simplexes $ BA x \ge 0, e*x = 1 $ instead of ellipsoids to solve systems of linear inequalities $A x > 0 $. It was harder to analyze, but we proved that its running time is also polynomial. Our version (simple, and flexible) is still the fastest numerically stable worst-case LP algorithm when the number of inequalities exceeds small polynomials of the dimension. Importantly, unlike EA, it is fully resistant to computational errors: the simplex cannot fail to contain all (normalized) solutions.

I invested efforts in figuring out how to teach Theory of Computations. Many textbooks frustrated me by being devoted to issues entirely unrelated to what the Theory of Computation is at present. [Levin 96] presented my attempts.

[Levin, V'yugin 77] classifies Turing-invariant properties of sequences modulo inaccessible sets, i.e. sets of measure 0 with complement closed under all recursive transformations. Restricting transformations to total, makes, weakly inaccessible sets. Properties are called equivalent if an inaccessible set includes their difference. There are infinitely many non-equivalent invariant properties, but only four of them are not weakly equivalent.

Some of my papers are on Intuitionistic Logic. [Levin 69] proved completeness, gave syntactic characterization and some other results on Medvedev's model of Intuitionistic Propositional Logic. [Levin 76c] introduced an axiom scheme called Principle of Information Conservation for second order Intuitionistic Arithmetic. It yields a maximal conservative extension of classical first order arithmetic. This kind of completeness is very unusual in Intuitionism.