Search

In this paper, we study quantum Ordered Binary Decision Diagrams(OBDD ) model; it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present a new technique ("reordering") for proving lower bounds and upper bounds for OBDD with an arbitrary order of input variables if we have similar bounds for the natural order. Using this transformation, we construct a total function REQ such that the deterministic OBDD complexity of it is at least 2 Ω (n / log n) , and the quantum OBDD complexity of it is at most O (n 2 / log n) . It is the biggest known gap for explicit functions not representable by OBDD s of a linear width. Another function(shifted equality function) allows us to obtain a gap 2 Ω (n) vs O (n 2) . Moreover, we prove the bounded error quantum and probabilistic OBDD width hierarchies for complexity classes of Boolean functions. Additionally, using "reordering" method we extend a hierarchy for read-k-times Ordered Binary Decision Diagrams ( k - OBDD ) of polynomial width, for k = o (n / log 3 n) . We prove a similar hierarchy for bounded error probabilistic k - OBDD s of polynomial, superpolynomial and subexponential width. The extended abstract of this work was presented on International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8 – 12, 2017 Khadiev and Khadieva (2017) [ABSTRACT FROM AUTHOR]

Foreign students coming to study in Russia learn the Russian language at all levels, enriching their vocabulary. Besides possessing the lexical minimum of the Russian language, foreign students studying at the preparatory department of the Russian university need to master specialised terminology used in computer science, physics and mathematics. These subjects are included in the list of disciplines of the supplementary general programme, which aims to provide a preparation course for foreign citizens and stateless persons to master professional educational programmes in the Russian language. This article describes the need and conditions for enriching and activating the vocabulary of foreign students, while providing a general description of research methods. It expounds on the structure and content of the computer science course at the pre-university stage of training for foreign citizens. The paper considers the process of teaching foreign studentsthe terminology used in the computer science course. This paper provides a number of examples of new terms as well as exercises related to their acquisition. It is concluded that teaching computer-science vocabulary to foreign students is one of the most important components of teaching information science and expanding the learners’ vocabulary in general. [ABSTRACT FROM AUTHOR]

Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from "classical" algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan–Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia (Milovanov 10). [ABSTRACT FROM AUTHOR]

The CSR conference series is devoted to a broad range of topics of theoretical computer science, which is reflected in the selected papers. This article belongs to the Topical Collection: Special Issue on Computer Science Symposium in Russia (2019) Guest Editor: René van Bevern and Gregory Kucherov This special issue of Theory of Computing Systems consists of a selection of works originally presented at the 14th International Computer Science Symposium in Russia (CSR 2019), held on July 1-5, 2019 in Novosibirsk, Russian Federation. [Extracted from the article]

The Russian Academy of Sciences is supporting the opening of two computing history sites. The first, an archive in Akademgorodok, Siberia, contains the papers of Andre P. Ershov, a Soviet pioneer of information processing. The archive is sponsored in part by Microsoft Research Ltd. and has a good English-language Web page. The archive also has a well-organized physical library. The staff has digitized many of the documents held there and made them accessible remotely. The second is Yakov Fet's History of Computing in Siberia site at Novosibirsk State University.