Zakablukov, Dmitry V.
Published in
Discrete Mathematics and Applications
The paper is concerned with the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates under constraints on the number of additional inputs. We study the Shannon functions for the complexity L(n, q) and depth D(n, q) of a reversible circuit implementing a map f:ℤ2n→ℤ2n$f\colon \mathbb{Z}_2^n \to \mathbb{Z}_2^n$ under ...
Cherepnev, Mikhail A.
Published in
Discrete Mathematics and Applications
We construct a probabilistic polynomial algorithm that solves the integer factorization problem using an oracle solving the Diffie–Hellman problem.
Pavlov, Yuriy L.
Published in
Discrete Mathematics and Applications
We consider configuration graphs with vertex degrees being independent identically distributed random variables. The distribution of these variables satisfies only relatively weak constraints on the probabilities of large values of degrees. For the case when the number of vertices tends to infinity, the conditions are found under which the graph is...
Yakymiv, Arsen L.
Published in
Discrete Mathematics and Applications
Dedicated to the memory of Alexander Ivanovich Pavlov. We consider the set of n-permutations with cycle lengths belonging to some fixed set A of natural numbers (so-called A-permutations). Let random permutation τn be uniformly distributed on this set. For some class of sets A we find the asymptotics with remainder term for moments of total cycle n...
Faruqi, Shahab Katre, S. A. Garg, Manisha
Published in
Discrete Mathematics and Applications
Two Latin squares A, B of order n are called pseudo orthogonal if for any 1 ≤ i, j ≤ n there exists a k, 1 ≤ k ≤ n, such that A(i, k) = B(j, k). We prove that the existence of a family of m mutually pseudo orthogonal Latin squares of order n is equivalent to the existence of a family of m mutually orthogonal Latin squares of order n. We also obtain...
Kravtsov, D. A. Krokhmal, N. E. Shabanov, D. A.
Published in
Discrete Mathematics and Applications
We study the threshold probability for the existence of a panchromatic coloring with r colors for a random k-homogeneous hypergraph in the binomial model H(n, k, p), that is, a coloring such that each edge of the hypergraph contains the vertices of all r colors. It is shown that this threshold probability for fixed r
Mazalov, Vladimir V. Trukhina, Lyudmila I.
Published in
Discrete Mathematics and Applications
Selivanov, Boris I. Chistyakov, Vladimir P.
Published in
Discrete Mathematics and Applications
We consider random polynomial allocations of particles over N cells. Let τk, k ≥ 1, be the minimal number of trials when k particles hit the occupied cells. For the case N → ∞ the limit distribution of the random variable τ k / N $\tau_k/\sqrt{N}$is found. An example of application of τk is given.
Voloshko, Valeriy A. Kharin, Yuriy S.
Published in
Discrete Mathematics and Applications
We introduce a new model P ${\mathscr{P}}$-CNAR(s) of sequences of discrete random variables with long memory determined by semibinomial conditionally nonlinear autoregression of order s ∈ ℕ with small number of parameters. Probabilistic properties of this model are studied. For parameters of the model P ${\mathscr{P}}$-CNAR a family of consistent ...
Cherednik, Igor V.
Published in
Discrete Mathematics and Applications
We study the set of transformations {ΣF : F∈ 𝓑∗(Ω)} implemented by a network Σ with a single binary operation F, where 𝓑∗(Ω) is the set of all binary operations on Ω that are invertible as function of the second variable. We state a criterion of bijectivity of all transformations from the family {ΣF : F∈ 𝓑∗(Ω)} in terms of the structure of the netw...
