• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 84
Sort:
by name
by year
Article
Osipov D. Lecture Notes in Computer Science. 2012. Vol. 7642 LNCS. P. 37-48.
In what follows an upper bound for the probability of erroneous decoding in a coded DHA FH OFDMA system with a noncoherent ML detector under multitone jamming is introduced.
Added: Feb 6, 2013
Article
Goldengorin B. I., Krushinsky D. Lecture Notes in Computer Science. 2011. Vol. 6701. P. 503-516.
Added: Jul 30, 2012
Article
Poelmans J., Dedene G., Viaene S. et al. Lecture Notes in Computer Science. 2011. Vol. 6828. P. 201-214.
Added: Mar 6, 2012
Article
Fomichov V. A., Кирилов А. С. Lecture Notes in Computer Science. 2012. Vol. 7557 LNAI. P. 296-304.
The paper describes a new method of constructing semantic expansions of search requests about the achievements and failures of active systems (organizations, people) for improving the results of Web search. This method is based on the theory of K-representations (knowledge representations), proposed by V.A. Fomichov - a new theory of designing semantic-syntactic analysers of natural language texts with the broad use of formal means for representing input, intermediary, and output data. The method uses an original formal model of a goals base - a knowledge base containing the information about the goals of active systems. The stated approach is implemented with the help of the Web programming language Java: an experimental search system AOS (Aspect Oriented Search) has been developed and tested.
Added: Feb 6, 2013
Article
Mirkin B., Fenner T., Nascimento S. et al. Lecture Notes in Computer Science. 2010. Vol. 6076. No. 1. P. 152-161.

A hybrid of two novel methods - additive fuzzy spectral clustering and lifting method over a taxonomy - is applied to analyse the research activities of a department. To be specific, we concentrate on the Computer Sciences area represented by the ACM Computing Classification System (ACM-CCS), but the approach is applicable also to other taxonomies. Clusters of the taxonomy subjects are extracted using an original additive spectral clustering method involving a number of model-based stopping conditions. The clusters are parsimoniously lifted then to higher ranks of the taxonomy by minimizing the count of “head subjects” along with their “gaps” and “offshoots”. An example is given illustrating the method applied to real-world data.

Added: Nov 14, 2012
Article
Shehtman V. B., Chagrov A. Lecture Notes in Computer Science. 1995. Vol. 933. P. 442-455.
Added: Oct 8, 2010
Article
Vereshchagin N., Shen A. Lecture Notes in Computer Science. 2017. Vol. 10010. P. 669-737.

Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there is no good model? If yes, how often these bad ("non-stochastic") data appear "in real life"? Another, more technical motivation comes from algorithmic information theory. In this theory a notion of complexity of a finite object (=amount of information in this object) is introduced; it assigns to every object some number, called its algorithmic complexity (or Kolmogorov complexity). Algorithmic statistic provides a more fine-grained classification: for each finite object some curve is defined that characterizes its behavior. It turns out that several different definitions give (approximately) the same curve. In this survey we try to provide an exposition of the main results in the field (including full proofs for the most important ones), as well as some historical comments. We assume that the reader is familiar with the main notions of algorithmic information (Kolmogorov complexity) theory.

Added: Feb 13, 2017
Article
Maxim Babenko, Goldberg A. V., Gupta A. et al. Lecture Notes in Computer Science. 2013. Vol. 7965. No. PART 1. P. 69-80.

Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (l1 norm). We give O(log n)- approximation algorithms for the problems of minimizing the maximum label (l∞ norm) and minimizing lp and lq norms simultaneously.

Added: Nov 13, 2013
Article
Разенштейн И. П., Бабенко М. А., Колесниченко И. И. Lecture Notes in Computer Science. 2010. № 5901. С. 165-175.
Added: Dec 17, 2010
Article
Ignatov D. I., Poelmans J., Dedene G. et al. Lecture Notes in Computer Science. 2012. Vol. 7143 LNCS. P. 195-202.
The topic of recommender systems is rapidly gaining interest in the user-behaviour modeling research domain. Over the years, various recommender algorithms based on different mathematical models have been introduced in the literature. Researchers interested in proposing a new recommender model or modifying an existing algorithm should take into account a variety of key performance indicators, such as execution time, recall and precision. Till date and to the best of our knowledge, no general cross-validation scheme to evaluate the performance of recommender algorithms has been developed. To fill this gap we propose an extension of conventional cross-validation. Besides splitting the initial data into training and test subsets, we also split the attribute description of the dataset into a hidden and visible part. We then discuss how such a splitting scheme can be applied in practice. Empirical validation is performed on traditional user-based and item-based recommender algorithms which were applied to the MovieLens dataset.
Added: Feb 6, 2013
Article
Nazarenko A., Sukhoroslov O. V. Lecture Notes in Computer Science. 2017. Vol. 10421. P. 327-341.

The paper studies the efficiency of nine state-of-the-art algorithms for scheduling of workflow applications in heterogeneous computing systems (HCS). The comparison of algorithms is performed on the base of discrete-event simulation for a wide range of workflow and system configurations. The developed open source simulation framework based on SimGrid toolkit allowed us to perform a large number of experiments in a reasonable amount of time and to ensure reproducible results. The accuracy of the used network model helped to reveal drawbacks of simpler models commonly used for studying scheduling algorithms.

Added: Aug 30, 2018
Article
Bogdanova-Beglarian N., Sherstinova T., Blinova O. et al. Lecture Notes in Computer Science. 2016. Vol. 9811. P. 100-107.

The research presented in this paper has been conducted in the framework of the large sociolinguistic project aimed at describing everyday spoken Russian and analyzing the special characteristics of its usage by different social groups of speakers. The research is based on the material of the ORD corpus containing long-term audio recordings of everyday communication. The aim of the given exploratory study is to reveal the linguistic parameters, in terms of which the difference in speech between different social groups is the most evident. An exploratory subcorpus, consisting of audio fragments of spoken communication of 12 respondents (6 men and 6 women, 4 representatives for each age group, and representatives of different professional and status groups) with the total duration of 106 min and of similar communication settings, was created and fully annotated. The quantitative description of a number of linguistic parameters on phonetic, lexical, morphological, and syntax levels in each social group was made. The biggest difference between social groups was observed in speech rate, phonetic reduction, lexical preferences, and syntactic irregularities. The study has shown that the differences between age groups are more significant than between gender groups, and the speech of young people differs most strongly from the others.

Added: Dec 31, 2017
Article
Babenko M. A., Artamonov S. I., Salikhov K. Lecture Notes in Computer Science. 2012. No. 7434. P. 109-120.

A digraph G = (V,E) with a distinguished set T V of terminals is called inner Eulerian if for each v V T the numbers of arcs entering and leaving v are equal. By a T-path we mean a simple directed path connecting distinct terminals with all intermediate nodes in V T. This paper concerns the problem of finding a maximum T-path packing, i.e. a maximum collection of arc-disjoint T-paths. A min-max relation for this problem was established by Lomonosov. The capacitated version was studied by Ibaraki,  Karzanov, and Nagamochi, who came up with a strongly-polynomial algorithm of complexity O(φ(V,E) log T +V 2E) (hereinafter φ(n,m) denotes the complexity of a max-flow computation in a network with n nodes and m arcs). For unit capacities, the latter algorithm takes O(φ(V,E) log T +V E) time, which is unsatisfactory since a max-flow can be found in o(V E) time. For this case, we present an improved method that runs in O(φ(V,E) log T + E log V ) time. Thus plugging in the max-flow algorithm of Dinic, we reduce the overall complexity from O(V E) to O(min(V 2/3E,E3/2) log T).

Added: Jan 27, 2013
Article
Savchenko A. Lecture Notes in Computer Science. 2015. Vol. 9124. P. 236-245.

The insufficient performance of statistical recognition of composite objects (images, speech signals) is explored in case of medium-sized database (thousands of classes). In contrast to heuristic approximate nearest-neighbor methods we propose a statistically optimal greedy algorithm. The decision is made based on the Kullback-Leibler minimum information discrimination principle. The model object to be checked at the next step is selected from the class with the maximal likelihood (joint density) of distances to previously checked models. Experimental study results in face recognition task with FERET dataset are presented. It is shown that the proposed method is much more effective than the brute force and fast approximate nearest neighbor algorithms, such as randomized kd-tree, perm-sort, directed enumeration method.

Added: Jul 5, 2015
Article
Mikhail Klimushkin, Sergei Obiedkov, Camille Roth Lecture Notes in Computer Science. 2010. Т. 5986. С. 255-266.

Concept lattices built on noisy data tend to be large and hence hard to interpret. We introduce several measures that can be used in selecting relevant concepts and discuss how they can be combined together. We study their performance in a series of experiments.

Added: Nov 14, 2012
Article
Mirkin B. Lecture Notes in Computer Science. 2011. Vol. 6743. P. 248-256.

A disjunctive model of box bicluster and tricluster analysis is considered. A least-squares locally-optimal one cluster method is proposed, oriented towards the analysis of binary data. The method involves a parameter, the scale shift, and is proven to lead to ”contrast” box biand tri-clusters. An experimental study of the method is reported.

Added: Feb 1, 2012
Article
Babin M. A., Kuznetsov S. Lecture Notes in Computer Science. 2012. Vol. 7278 LNAI. P. 7-15.
Concept stability was used in numerous applications for selecting concepts as biclusters of similar objects. However, scalability remains a challenge for computing stability. The best algorithms known so far have algorithmic complexity quadratic in the size of the lattice. In this paper the problem of approximate stability computation is analyzed. An approximate algorithm for computing stability is proposed. Its computational complexity and results of computer experiments in comparing stability index and its approximations are discussed.
Added: Feb 7, 2013
Article
Savelieva A., Khovratovich D., Rechberger C. Lecture Notes in Computer Science. 2012. Vol. 7549 LNCS. P. 244-263.

We present a new concept of biclique as a tool for preimage attacks, which employs many powerful techniques from differential cryptanalysis of block ciphers and hash functions. The new tool has proved to be widely applicable by inspiring many authors to publish new results of the full versions of AES, KASUMI, IDEA, and Square. In this paper, we show how our concept leads to the first cryptanalysis of the round-reduced Skein hash function, and describe an attack on the SHA-2 hash function with more rounds than before.

Added: Feb 7, 2013
Article
Nascimento S., Mirkin B. Lecture Notes in Computer Science. 2011. Vol. 6743. P. 273-277.
Added: Feb 1, 2012
Article
Zakharov V.A. Lecture Notes in Computer Science. 2015. Vol. 9270. P. 208-221.

Finite state transducers over semigroups can be regarded as a formal model of sequential reactive programs. In this paper we introduce a uniform tech- nique for checking e ectively functionality, k-valuedness, equivalence and inclusion for this model of computation in the case when a semigroup these transducers op- erate over is embeddable in a decidable group.

Added: Sep 30, 2015
Article
Maxim Babenko. Lecture Notes in Computer Science. 2013. Vol. 7741. P. 146-156.

Let G = (V,E) be a digraph with disjoint sets of sources S ⊂ V and sinks T ⊂ V endowed with an S–T flow f : E → Z+. It is a well-known fact that f decomposes into a sum_st(fst) of s–t flows fst between all pairs of sources s ∈ S and sinks t ∈ T . In the usual RAM model, such a decomposition can be found in O(E log V 2 E ) time. The present paper concerns the complexity of this problem in the external memory model (introduced by Aggarwal and Vitter). The internal memory algorithm involves random memory access and thus becomes inefficient. We propose two novel methods. The first one requires O(Sort(E) log V 2 E ) I/Os and the second one takes O(Sort(E) log U) expected I/Os (where U denotes the maximum value of f).

Added: Nov 13, 2013