Sergei Evdokimov

Sergei Alekseevich 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.

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

After graduation, he continued research in the theory of modular forms, and in 1977 earned his PhD degree (Candidate of Sciences) from Leningrad Department of Steklov Mathematical Institute of USSR Academy of Sciences with the thesis "Euler products for congruence subgroups of the Siegel group of genus".

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.

During 1981–1993 he was a senior researcher of Laboratory of Theory of Algorithms at Leningrad Institute for Informatics and Automation of USSR 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 Slissenko and Dima Grigoriev.

From 1993 he also began active collaboration with Ilia Ponomarenko, in algebraic combinatorics, which lasted until the end of his life.

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 of works 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 with Sergio Albeverio and Maria Skopina he studied p-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, any p-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.

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.

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.