Having graduated from the University in 1963 he became a researcher at the Leningrad Department of Steklov Mathematical Institute of the Academy of Sciences of the USSR (nowadays it is called slightly differently [3].

In 1963–1966 he continued his research in constructive mathematics and at the same time he participated in the development and implementation of Shanin's algorithm for automatic theorem proving in classical propositional logic [4].

Another major result of Slissenko was a real-time algorithm that solved a large variety of string-matching problems (including finding of all periodicities in a compact form) [8].

He worked on the complexity of Markov decision processes [14], on algorithms constructing shortest paths amidst semi-algebraic and other obstacles and on the verification of timed systems.

Paper [15] describes a polytime algorithm for constructing a shortest path touching skew straight lines in 3-dimensional space that solves a known open problem.

He collaborated with Nikolai Shanin, S.Maslov, G.Mints and V.Orevkov on automatic theorem proving, with D.Beauquier,  Dima Grigoriev, D.Burago, A.Rabinovich and others on various topics related to algorithmics  [6], [7].

A.O.Slissenko was a part-time professor in Leningrad Polytechnical Institute [8] in 1981–1987, and in 1988–1992 he was a part-time professor in the faculty of Mathematics and Mechanics of Leningrad State University [9] where he was the head of the Department of Computer Science whose creation he initiated (the student teams of the Department were world champions of ACM International Collegiate Programming Contest four times).

The seminar functioned until 1992, date on which after the collapse of the Soviet Union (and of its research system) the main part of its participants left the country and found jobs in USA, France, UK.