?
Стохастические булевы функции и их спектры
Математические вопросы криптографии. 2012. Т. 3. № 3. С. 21-34.
Ivchenko G., Медведев Ю. И.
Research target:
Mathematics
Language:
Russian
Keywords: spectral characteristicsспектральные характеристикибулева функцияпреобразование Уолшаспектр функциипредельные теоремыBoolean functionconversion Walshspectrum of functioncharacteristic functionparametric measurelimit theoremsхарактеристическая функцияпараметрическая мераприменение теоретико-вероятностных и статистических методов
Ivchenko G., Медведев Ю. И., Математические вопросы криптографии 2011 Т. 2 № 2 С. 41-53
Исследуются свойства спектра случайной булевой функции от n переменных. Выводится общая производящая функция спектра и находятся точные и асимптотические (при ) распределения различных характеристик спектра. ...
Added: April 12, 2012
Ivchenko G., Миронова В. А., Дискретная математика 2013 Т. 25 № 1 С. 90-110
We analyse properties of the Walsh spectrum of Boolean functions of n variables which are chosen at random from some subsets of the set of all these functions. We derive the characteristic functions of the spectrum and find exact and asymptotic, as n → ∞, distributions of its various characteristics. ...
Added: August 20, 2013
Ложкин С. А., Шуплецов М. С., Коноводов В. А. et al., Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС) 2016 Т. 1 С. 40-47
The synthesis of optimal or suboptimal switching circuits is an actual problem of theory of discrete control
systems. Libraries of such circuits could be used in various algorithms of logic synthesis (e.g., see [1]). The structure
analysis of optimal circuits for functions of few variables may be useful in the development of standard cell libraries.
The first catalogs ...
Added: December 2, 2019
Bufetov A. I., Annals of Mathematics 2014 Vol. 179 No. 2 P. 431-499
The aim of this paper is to obtain an asymptotic expansion for ergodic integrals of translation ows on at surfaces of higher genus (Theorem 1) and to give a limit theorem for these ows (Theorem 2). © 2014 Department of Mathematics, Princeton University. ...
Added: February 19, 2014
Golubin A. Y., Gridin V. N., Автоматика и телемеханика 2012 № 9 С. 111-123
В работе найдены оптимальные с точки зрения страховщика стратегии страхования и перестрахования в управляемом процессе риска Крамера-Лундберга, описывающем динамику капитала страховой компании на длительном временном интервале. В качестве минимизируемого критерия оптимальности использовался стационарный коэффициент вариации, были учтены дополнительные ограничения на остаточные риски как страхователей, так и перестраховщика. ...
Added: October 23, 2012
Ulyanov V.V., Theory Probability and its Applications 2016 Vol. 60 No. 2 P. 325-336
This paper deals with different properties of polynomials in random elements: bounds for characteristic functionals of polynomials, a stochastic generalization of the Vinogradov mean value theorem, the characterization problem, and bounds for probabilities to hit the balls. These results cover the cases when the random elements take values in finite as well as infinite dimensional ...
Added: March 12, 2017
Podolskii V. V., Logical Methods in Computer Science 2013 Vol. 9 No. 2 P. 1-17
An integer polynomial p of n variables is called a threshold gate for a Boolean function f of n variables if for all x∈{0,1}n f(x)=1 if and only if p(x) > 0. The weight of a threshold gate is the sum of its absolute values. In this paper we study how large a weight might be needed if ...
Added: October 20, 2014
А.И. Буфетов, Успехи математических наук 2013 Т. 68 № 5(413) С. 3-80
In this paper an asymptotic expansion of ergodic integrals for suspension flows over Vershik automorphisms is obtained and a limit theorem for these flows is given.
Bibliography: 49 titles. ...
Added: October 23, 2014
Lozhkin S. A., Danilov B.R., Computational Mathematics and Modeling 2012 Vol. 23 No. 4 P. 487-506
The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements may have different input delays. Asymptotic bounds of the form τ B n±O(1), where τ B is a constant that depends only on the basis B, are obtained for ...
Added: December 2, 2019
Sysoeva L., Вестник Московского университета. Серия 1: Математика. Механика 2019 № 6 С. 51-55
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и n входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант 0 или 1, зависящих от n переменных, n > 0.
Построен пример инициального булева автомата с минимальным количеством константных состояний и n входами, реализующего максимальное возможное число булевых функций от n фиксированных переменных, при ...
Added: October 14, 2018
Ложкин С. А., Danilov B. R., Прикладная математика и информатика 2011 № 39 С. 107-129
The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements may have different input delays. Asymptotic bounds of the form τ_B n ± O(1), where τ_B is a constant that depends only on the basis B, are obtained for ...
Added: December 2, 2019
Fomin D., Математические вопросы криптографии 2019 Vol. 10 No. 2 P. 169-180
This work introduces new classes of 8-bit permutation based on a butterfly structure. These classes set up a new way for generating 2n-bit permutation from n-bit ones. We introduce some classes that contain permutations with good cryptographic properties and could be efficiently implemented for hardware and software applications. ...
Added: May 4, 2019
Revenko A., Kuznetsov S., Fundamenta Informaticae 2012 Vol. 4 No. 115 P. 377-394
An approach for studying relations between properties of functions on sets is proposed. The approach is based on Attribute Exploration. 16 properties of functions are considered, among them monotonicity, idempotency, path independence, exchange properties, convexity, etc. Example functions are partially computer generated on the powersets of sets with 2, 3 and 4 elements. Attribute Exploration ...
Added: December 31, 2012
Belomestny D., Iosipoi L., Mathematics and Computers in Simulation 2021 No. 181 P. 351-363
Markov Chain Monte Carlo methods become increasingly popular in applied mathematics as a tool for numerical integration with respect to complex and high-dimensional distributions. However, application of MCMC methods to heavy-tailed distributions and distributions with analytically intractable densities turns out to be rather problematic. In this paper, we propose a novel approach towards the use ...
Added: October 31, 2020
Penikas H. I., Andrievskaya I. K., Model Assisted Statistics and Applications 2012 Vol. 7 No. 4 P. 267-280
According to the strategy of the banking system development until 2015, the Central Bank of Russia is going to implement Basel II Internal-Ratings-Based (IRB) approaches in 2015, while Basel III is planned to be introduced in full starting from 2019. Taking into account the effects of the Basel II regulation during the crisis 2008-2009, in ...
Added: November 6, 2012
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2008 № 6 С. 141-146
Рассматривается понятие граничного класса, которое является полезным инструментом для анализа вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся задачи, для которых эти классы являются граничными. ...
Added: August 31, 2012
Beklemishev L. D., Оноприенко А. А., Математический сборник 2015 Т. 206 № 9 С. 3-20
We formulate some term rewriting systems in which the number of computation steps is finite for each output, but this number cannot be bounded by a provably total computable function in Peano arithmetic PA. Thus, the termination of such systems is unprovable in PA. These systems are derived from an independent combinatorial result known as the Worm ...
Added: March 13, 2016
D. V. Gribanov, D.S. Malyshev, P. M. Pardalos et al., Journal of Combinatorial Optimization 2018 Vol. 35 No. 4 P. 1128-1146
In this paper, we present fixed-parameter tractable algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems’ formulations are near square. The parameter is the maximum absolute value of the rank minors in the corresponding matrices. Additionally, we present fixed-parameter tractable algorithms ...
Added: February 19, 2018
Yashunsky A., Вестник Московского университета. Серия 1: Математика. Механика 2019 № 4 С. 3-9
We consider systems of Boolean functions inducing algebras of Bernoulli distributions, whose universal set has a single limit point. We establish a criterion for an algebra generated by a given set of distributions to have a unique limit point. ...
Added: September 9, 2020
Babash A. V., М. : ИНФРА-М, РИОР, 2013
Пособие предназначено для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в экономике)». Оно также содержит методический материал для ряда инновационных курсов лекций по профилю «Информационная безопасность» и может быть использовано и для блока дисциплин этого профиля. Ряд представленных результатов полезен специалистам и аспирантам, специализирующихся в указанной области. ...
Added: January 14, 2014
Feigin B. L., Finkelberg M. V., Rybnikov L. G. et al., Selecta Mathematica, New Series 2011 Vol. 17 No. 3 P. 573-607
Laumon moduli spaces are certain smooth closures of the moduli spaces of maps from the projective line to the flag variety of GLn. We construct the action of the Yangian of sln in the cohomology of Laumon spaces by certain natural correspondences. We construct the action of the affine Yangian (two-parametric deformation of the universal ...
Added: October 9, 2012
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Added: August 31, 2012
Vyalyi M., Дискретная математика 1991 Т. 3 № 3 С. 35-45
Added: October 17, 2014
Sirotkin D., Malyshev D., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Added: September 7, 2017