Sergei Evdokimov

Sergei Evdokimov (December 12, 1950 —September 10, 2016) was a Russian mathematician who contributed to the theory of modular forms, computational complexity theory, algebraic combinatorics and p-adic analysis.

Sergei Evdokimov was born in Leningrad (now Saint Petersburg, Russia), and graduated from Leningrad State University, Dept. of Mathematics and Mechanics, in 1973 (Honours Diploma). During his studies, he attended a seminar on modular forms and started to work in this area under the supervision of professor Anatoli N. Andrianov. After graduation, he continued research in the theory of modular forms, and in 1977 earned his PhD degree (Candidate of Sciences) fromLeningrad Department ofSteklov Mathematical Institute of USSR Academy of Sciences with the thesis "Euler products for congruence subgroups of the Siegel group of genus". During 1981–1993 he was a senior researcher of Laboratory of Theory of Algorithms atLeningrad Institute for Informatics and Automation ofUSSR Academy of Sciences. That time his scientific interests were switched to the computational complexity of algorithms in algebra and number theory. He was an active participant of a seminar on computational complexity headed by Anatol Slissenkoand Dima Grigoriev. From 1993 he also began active collaboration with Ilia Ponomarenko, in algebraic combinatorics, which lasted until the end of his life. Many of the results obtained in this collaboration were included in his DSc thesis "Schurity and separability of association schemes", that was defended in 2004. Starting in 2005, he was a leading researcher in St. Petersburg Department Mathematical Institute of Russian Academy of Sciences.

During 1975-1982 Sergei had published a series of impressive papers on the arithmetic of Siegel modular forms. His PhD thesis contains very fine arithmetic constructions related to the ray classes of ideals of imaginary quadratic fields. Continuing his research on the theory of modular forms, he found an elegant analytical description of the Maass subspace of Siegel modular forms of genus 2, an explicit formula for the generating Hecke series of the symplectic group of genus 3, and the first explicit formulas for the action of degenerate Hecke operators on the space of theta-series

In the mid-1980s, switching to the computational complexity of algorithms in algebra and number theory, he found a delicate and simple algorithm for factorization of polynomials over finite fields. The algorithm has a quasi-polynomial complexity under the assumption of generalized Riemann's hypothesis. Despite considerable efforts by mathematicians working in the theory of computational complexity, up to the present (2019), his estimate for the complexity of the factorization problem has not been improved.

Starting in 1993, Sergei has been engaged into problems of algebraic combinatorics. Several profound results were obtained, including the refutation of the Schur-Klin conjecture on Schur rings over a cyclic group,a polynomial-time algorithm for recognizing and testing isomorphism of circulant graphs,and building a theory of multidimensional coherent configurations . The latter provided an algebraic explanation for the fact that the problem of isomorphism of finite graphs cannot be solved using only combinatoric methods. Another series ofworks was devoted to the problem of isomorphism and the algorithmic theory of permutation groups. In particular, a number of algorithms(which became already classical) for testing graph isomorphism were constructed.

In the last years of his life, Sergei became also interested in p-adic analysis. Jointly withSergio Albeverio and Maria Skopina he studiedp-adic wavelet bases. These studies revealed an unexpected and highly nontrivial fact:unlike similar theories in other structures, the standard method in p-adic analysis leads to nothing except the Haar basis. Moreover, anyp-adic orthogonal wavelet basis generated by test functions is some modification of the Haar basis. In his last work on this topic, an orthogonal p-adic wavelet basis generated by functions with non-compact support was constructed, while all previously known bases, as well as frames, were generated by the test functions.