Search

We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in $O(\log D)$ rounds in the massively parallel computation model (MPC), with $O(n^\delta)$ words of local memory per machine, for any given constant $0 < \delta < 1$. Here $D$ is the diameter of the tree and $n$ is the number of nodes--we emphasize that our running time is independent of $n$. Our algorithm can solve many classical graph optimization problems such as maximum weight independent set, maximum weight matching, minimum weight dominating set, and minimum weight vertex cover. It can also be used to solve many accumulation tasks in which some aggregate information is propagated upwards or downwards in the tree--this includes, for example, computing the sum, minimum, or maximum of the input labels in each subtree, as well as many inference tasks commonly solved with belief propagation. Our algorithm can also solve any locally checkable labeling problem (LCLs) in trees. Our algorithm works for any reasonable representation of the input tree; for example, the tree can be represented as a list of edges or as a string with nested parentheses or tags. The running time of $O(\log D)$ rounds is also known to be necessary, assuming the widely-believed $2$-cycle conjecture. Our algorithm strictly improves on two prior algorithms: (i) Bateni, Behnezhad, Derakhshan, Hajiaghayi, and Mirrokni [ICALP'18] solve problems of these flavors in $O(\log n)$ rounds, while our algorithm is much faster in low-diameter trees. Furthermore, their algorithm also uses randomness, while our algorithm is deterministic. (ii) Balliu, Latypov, Maus, Olivetti, and Uitto [SODA'23] solve only locally checkable labeling problems in $O(\log D)$ rounds, while our algorithm can be applied to a much broader family of problems.

In this paper, we developed a new technique for blind embedding of ternary coded watermarks into audio files. Usage of ternary coding increases payload of the method that can be considered as an advantage against binary-coded watermarks. A well-known melody is presented as a sequence of ternary digits (trits) and is used as a watermark. This sequence is embedded into the time domain of a host audio file through amplitude modulation and B-splines. There is a version of that procedure where the clean copy of the container is necessary for extraction watermark [1]. In our approach, we exclude that container and convert the method into a blind one. The strong correlation between neighbor samples in the container is used to this end. A procedure based on neuron net is suggested for enhancement perception of ternary coded music. In this case, we exploit the correlation between samples in the watermark melody. It is supposed that a person checks the mark's existence, and he/she can recognize the melody even after significant distortions. The resistance of the technique to the most successful attacks is investigated. The paper is an extended version of the conference paper [1].

We propose a new family of echo hiding procedures designed to work with audio files with ternary watermarks. Most attention is paid to the case when the image is used as a watermark. The possibility of using a melody for this purpose is also mentioned. A human is supposed to be a detector to prove the presence of a watermark in the audio file. The approach employs infinite impulse response (IIR) filters of a particular form that provides a capability insertion a few symbols into a fragment of the container. The suggested method’s payload and resistance to various attacks exceed the parameters of the classical implementation of echo hiding.

In the general case, a finite impulse response (FIR)filter has no inverse filter. To solve the inverse filtering problem, we propose an approximate method that restores the initial sequence. We analyze the sequence obtained by filtering the source sequence with an arbitrary FIR filter. The analysis made with the help of a deep neural network. The results of the study are applied to speech coding. We show experimentally, that our approach provides lowering bit rate in the transmission of speech data through a channel.

Most industrial automatic systems are remotely controlled, so the problem of protecting control information transmitted through an open channel is relevant. The use of cryptographic systems for security involves the ability to fast exchange system keys. In this paper, a new family of the true random key generators is proposed. The source of entropy for such random devices is the phenomenon of jittering in electronic circuits. Generators are built in the form of cascade schemes based on adders. We give the architectural solution for the synthesis of the generator that based on transition dynamics of such an appliance. The procedure for the hidden transfer of keys using those generators is discussed.

We propose a new type of watermarks for graphic black and white documents. Insertion of the watermark in a document minimizes distortion of the latter. The watermarking allows extra verification of blockchain database records containing scans of documents.

In this paper, we present a novel archival system called ARCHAIN, developed for the State Archive-keeping Committee of the Republic of Tatarstan (Russia). Blockchain is the principal part of the system, which stores transactions (facts of transfer of documents to the archive) in a protected form. The developed system uses a permissioned blockchain model due to the customer's requirement for the presence of a trusted center. Index Terms-blockchain, archival science, cryptography

Asynchronous combinational circuits with feedback containing linear units over GF(3) are considered. Using a special scheme designs one can create controlled true random generators. The offered generators can be utilized as a part of built-in security systems.

In this paper, we propose a new method for estimating the slant of word in handwritten text. The method allows a researcher to analyze snippets of a picture containing a few words in different lines. The main goal of the research is to present a tool to observe small changes of slant in the text during work. Student check sheets were used as a database for the research. Some changes in slant depending on speed of writing are discovered.

Programmable logic devices on base of asynchronous combinational circuits with feedback are considered. The main aim of the research is to obtain a method for designing a circuit with a set of prescribed stable states or a circuit without stable states — a generator of true random numbers. Both the cases of binary and ternary logics are studied.

Nowadays the progress in information technologies filed is opening great new possibilities for people in all areas of living. As education is fundamental step in every person's life we have to increase its’ popularity, availability and convenience for everybody. Information technologies present a lot of new tools and approaches which expand the infrastructure of the educational process. Our idea integrates the simplicity and reliability of client-server architecture and usability of various forms of user interfaces. The design describes an e-learning system, which has an m-learning interface, and several new modules which increase the efficiency of the studies. For these purposes we propose module for preliminary homework checking, statistical module and feedback module that can be extended to the separate rating system. The variety of interfaces is supported by three components: desktop application, mobile application and web-based application. Although we concentrate on desktop and mobile forms as according to the statistical data they are more usable. The difference of European, American and Russian systems of education predetermine some aspects in the design approach. It allows to use the strongest advantages of every model in the solution and to share the multinational experience. The paper describes in details the highlighted moments.

We show that instantaneous frequency (IF) can be used for automatic detection of speech dynamics. A very simple procedure for IF estimation is developed which spends much less computer resources in comparison with standard IF calculation methods. The input file is divided into frames, and IFs are calculated at points related to local maximums in frame. All inferences about presence of speech dynamics in the file are done on the base of distributions of IFs inside of the frames. Efficiency of considered technique is demonstrated by the problem of source separation.

Education is a key element in the life of every person. In the recent years we have seen strong growth and development of information technologies, and as a consequence - informatization process in all areas of society. Particular attention is now being paid to mobile technologies, based on the analysis of the market it has been revealed that tablets and smartphones are one of the most promising areas of development in the near future. The paper presents an approach to design of the e-learning systems in terms of diversity of implementation on the side of the client/end user (mobile application, web application and a classic application for PC). To improve the performance of teachers and students the implementation of special units is suggested, such as the module of the analytical statistics for teachers, the module of additional advanced checking of home work and feedback module.

The latest achievements in the information sciences area are mostly connected with the mobile technologies. The significant growth in this area attracts more and more users worldwide. In this paper we concentrate on the mobile learning aspect in education process, specifically in learning management systems. We propose a new design approach which consolidates different front-end representations of the learning system with the single back-end instance. To increase the efficiency of the system we consider new module like preliminary homework checking module, which will be useful especially in software engineering field, and additional statistical and feedback modules.