Destinies and Seminars
On the Seminar «Problems of Reducing the Exhaustive Search» at LETI in a Historico-Scientific Context
Abstract
The history of the seminar « Problems of Reducing the Exhaustive Search» organized at the Leningrad Electrotechnical Institute (LETI) by R.I. Freidson (1942-2018) is considered. The seminar opened in 1982, one of its main aims being the development of scientific ideas of S. Yu. Maslov (1939-1982). The meetings continued regularly until the beginning of 1990es. The historico-scientific context is outlined, including the links with other contemporary seminars, such as the S.Yu. Maslov’s seminar and the seminar on mathematical logic at the Leningrad Branch of the Steklov Mathematical Institute (LOMI); the ideas developed at the seminar and main results represented by scientific publications are considered. The pedagogical role of the seminar (its formative influence on young researchers), the organizational talent of R.I. Freidson and the effect of his personality on seminar’s creative atmosphere are considered as well.References
S. V. Soloviev, “Seminar na poslednem etazhe” [Seminar on the Last Floor], Zvezda, no. 3, pp. 177–196, 2019 (in Russian).
D. A. Pospelov, G. E. Mints, and R. I. Freidson eds., “Problemy sokrashcheniya perebora” [Problems of Reducing Exhaustive Search], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987 (in Russian).
R. I. Freidson, “Algoritmika perebornykh zadach” [Algorithmics of exhaustive search], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, pp. 3–6, 1987 (in Russian).
V. Kreinovich and V. G. Mints eds., “Problems of Reducing the Exhaustive Search,” AMS Translations, ser. 2, vol. 178, 1997.
E. Ya. Dantsin and V. Ya. Kreinovich, “Veroyatnostnyi vyvod v sistemakh prognozirovaniya” [Probabilistic deduction in forecasting systems], Doklady Akademii Nauk SSSR, vol. 307, no. 1, 1989 (in Russian).
M. A. Vsemirnov et al., “Nikolai Aleksandrovich Shanin (nekrolog)” [Nikolay Aleksandrovich Shanin (obituary)], Uspekhi Mathematicheskikh Nauk, vol. 68, no. 4(412), pp. 173–176, 2013 (in Russian).
S. Yu. Maslov, “Iterativnye metody v perebornoi modeli, kak model’ intuitivnykh” [Iterative methods in intractable problems as a model of intuitive methods], in Abstracts of 9-th All-Union symposium on Cybernetics, Sukhumi, USSR, 1981, pp. 26–28 (in Russian).
S. Yu. Maslov, “Asimmetriya poznavatel’nykh mekhanizmov i ee sledstviya” [Asymmetry of cognitive mechanisms and its implications], Semiotics and Information Science, vol. 20, pp. 3–31, 1983 (in Russian).
S. Yu. Maslov, “Ischisleniya s monotonnymi vyvodami i ikh ekonomicheskaya interpretatsiya” [Calculi with monotone deductions and their economic interpretation], Zapiski Nauchnych Seminarov LOMI, vol. 88, pp. 90–105, 1979 (in Russian).
V. Ya. Kreinovich, “Semantika interaktivnogo metoda S. Yu. Maslova” [Semantics of interactive method of S. Yu. Maslov], Voprosy Kibernetiki, Moscow: Nauka, vol. 131, pp. 30–62, 1987 (in Russian).
M. I. Zakharevich, “Ergodicheskie svoistva iteratsionnogo metoda S. Yu. Maslova” [Ergodic properties of the iterative method of S. Yu. Maslov], Ibid., pp. 63–75, 1987.
I. V. Melichev, “Anomal’nye svoistva iteratsionnogo metoda S. Yu. Maslova” [Anomalous properties of the iterative method of S. Yu. Maslov], Ibid., pp. 76–86.
E. Ya. Dantsin, “Algoritmika zadachi vypolnimosti” [Algorithmics of the satisfiability problem], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 7–29 (in Russian).
S. M. Moosavi-Dezfooli, A. Fawzi, and P. Frossard, “DeepFool: A simple and accurate method to fool deep neural networks,” in Proc. of IEEE Conf. on computer vision and pattern recognition, Las Vegas, NV, 2016, pp. 2574–2582.
R. Williams, “Improving exhaustive search implies super polynomial lower bounds,” in Proc. of the 42nd Annu. ACM Symp. on Theory of Computing (STOC–2010), 2010, pp. 231–240; Journal version: SIAM J. Comput., vol. 42, no. 3, pp. 1218–1244, 2013; doi: 10.1137/10080703X
R. Williams, “Non-uniform ACC circuit lower bounds,” in Proc. of the 26th Annu. IEEE Conf. on Computational Complexity (CCC–2011), 2011, pp. 115–125; Journal version: JACM, vol. 61, no.1, pp. 2:1– 2:32, 2014; doi: 10.1145/2559903
R. Williams, “Algorithms for circuits and circuits for algorithms: Connecting the tractable and intractable,” in Proc. of the Int. Congr. of Mathematicians (ICM 2014), vol. 4, 2014, pp. 659–682.
G. V. Davydov and I. M. Davydova, “Dvoistvennye algoritmy v diskretnoi optimizatsii” [Dual algorithms in discrete optimization], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 90–117 (in Russian).
Yu. V. Matiyasevich, “Possible nontraditional methods of establishing the satisfiability of propositional formulas,” in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 87–89 (in Russian).
A. Ya. Dikovsky, “Modeli, metody i rezhimy sinteza skhem programm” [Models, methods and modes for the synthesis of program schemes], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 117–148 (in Russian).
N. K. Kossovskii, “Nizhnyaya granitsa skhemnoi slozhnosti pri sokrashchenii eksponentsial’nogo perebor” [Lower bounds of combinatorial complexity for exponential search reduction], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 167–179 (in Russian).
An. A. Muchnik, “Ob odnom klasse polinomial’nykh sistem uravnenii, vytekayushchikh iz formuly polnoi veroyatnosti, i vozmozhnosti ustraneniya perebora pri ikh resheniia” [On a class of polynomial systems of equations following from the formula for total probability and possibilities for elimination search in solving them], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 180–195 (in Russian).
M. I. Kanovich, “Effektivnye ischisleniya kak sredstvo sokrashcheniya perebora” [Effective calculi as a technique for search reduction], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 149–166 (in Russian).
B. A. Kushner, “The Teacher (To the centennial of A.A. Markov, Jr.),” in From the History of Cybernetics, Ya. Fet, ed., Novosibirsk: Geo Academic Publishers, 2006, pp. 189–262 (in Russian).
This work is licensed under a Creative Commons Attribution 4.0 International License.
