Ultrametric algorithms and automata

Ultrametric algorithms are similar to probabilistic algorithms, only the degree of indeterminism is presented not by a real number between 0 and 1 (called “probability”) but by a p-adic number. This notion was introduced in 2012. Since then many results have been obtained. Partly, they explain why p-adic numbers are so popular in string theory and modern molecular biology. Probably, the most interesting part of this study is the complexity. For some languages ultrametric algorithms are more efficient than probabilistic ones, while for other languages probabilistic algorithms perform better.

Rusins Freivalds (b. 1942) is a full professor of Computer Science in the University of Latvia. He got his Ph.D. in 1971 from the S. L. Sobolev Institute of Mathematics in Novosibirsk, USSR (under Prof. Boris A. Trakhtenbrot) and Dr. habil. math. in 1985 from Moscow State University. R. Freivalds is best known for his randomized algorithm used to verify matrix multiplication. The best known matrix multiplication algorithm runs in O(n^2.3729) time. Freivalds’ algorithm (1977) utilizes randomization in order to reduce this time bound to O(n²) with high probability. Other highly cited Freivalds’ papers concern inductive inference problems and quantum computation.