共查询到20条相似文献,搜索用时 46 毫秒
1.
Tadashi Wadayama Toru Hada Koichiro Wakasugi Masao Kasahara 《Designs, Codes and Cryptography》2001,23(1):23-34
The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions. 相似文献
2.
Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions. 相似文献
3.
Sequential Dynamical Systems (SDSs) are mathematical models for analyzing simulation
systems. We investigate phase space properties of some special classes of SDSs obtained
by restricting the local transition functions used at the nodes. We show that any SDS over the
Boolean domain with symmetric Boolean local transition functions can be efficiently simulated
by another SDS which uses only simple threshold and simple inverted threshold functions, where
the same threshold value is used at each node and the underlying graph is
d-regular for some integer
d. We establish tight or nearly tight upper and lower bounds
on the number of steps needed
for SDSs over the Boolean domain with 1-, 2- or 3-threshold functions at each of the nodes to
reach a fixed point. When the domain is a unitary semiring and each node computes a linear
combination of its inputs, we present a polynomial time algorithm to determine whether such an
SDS reaches a fixed point. We also show (through an explicit construction) that there are Boolean
SDSs with the NOR function at each node such that their phase spaces contain directed cycles
whose length is exponential in the number of nodes of the underlying graph of the SDS.AMS Subject Classification: 68Q10, 68Q17, 68Q80. 相似文献
4.
We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree. 相似文献
5.
Construction of noniterated boolean functions in the basis {&;, ∨, −} and estimation of their number
O. V. Zubkov 《Russian Mathematics (Iz VUZ)》2008,52(10):13-19
In this paper we consider noniterated Boolean functions in the basis {&;, ∨, ?}. We obtain the canonical form of the formula for a noniterated function in this basis. We construct the set of such formulas with respect to variables x 1, …, x n and calculate the number of its elements. Based on these results, we obtain the upper and lower bounds for the number of noniterated Boolean functions of n variables in the basis under consideration. 相似文献
6.
Zhou Bo 《Czechoslovak Mathematical Journal》2002,52(4):731-738
We obtain upper bounds for generalized indices of matrices in the class of nearly reducible Boolean matrices and in the class of critically reducible Boolean matrices, and prove that these bounds are the best possible. 相似文献
7.
This paper contains a review of the authors’ results in the theory of algorithm complexity. The results described concern
methods for obtaining lower bounds (containing almost all exponential lower bounds on monotone complexity of monotone functions),
synthesis of asymptotically optimal functional networks, minimization of Boolean functions, and the problem of solving Boolean
equations. 相似文献
8.
This paper estimates upper and lower bounds for the approximation rates of iterated Boolean sums of multivariate Bernstein polynomials. Both direct and inverse inequalities for the approximation rate are established in terms of a certain K-functional. From these estimates, one can also determine the class of functions yielding optimal approximations to the iterated Boolean sums. 相似文献
9.
V. A. Vitkup 《Journal of Applied and Industrial Mathematics》2016,10(1):126-135
We study the symmetric properties of APN functions as well as the structure and properties of the range of an arbitrary APN function. We prove that there is no permutation of variables that preserves the values of an APN function. Upper bounds for the number of symmetric coordinate Boolean functions in an APN function and its coordinate functions invariant under a cyclic shift are obtained. For n ≤ 6, some upper bounds for the maximal number of identical values of an APN function are given and a lower bound is found for different values of an arbitrary APN function of n variables. 相似文献
10.
V. N. Noskov 《Mathematical Notes》1975,18(1):664-670
Exact upper bounds for the complexity of absolute tests checking the correctness of inputs of logic diagrams realizing Boolean functions which are essentially dependent on n variables have been found for n ≥ 136. 相似文献
11.
A real multivariate polynomial p(x
1, …, x
n
) is said to sign-represent a Boolean function f: {0,1}
n
→{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1}
n
. We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds
for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds
since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs. 相似文献
12.
V. S. Fedorova 《Journal of Applied and Industrial Mathematics》2013,7(3):344-354
We consider functional Boolean equations and the satisfiability problem for them, which amounts to the following: Does there exist a Boolean function satisfying a given functional equation? We establish upper and lower bounds for the complexity of the satisfiability problem for a system of functional Boolean equations. This justifies the impossibility of its solution by any method substantially simpler than the brute-force search. 相似文献
13.
Stasys Jukna 《Combinatorica》1999,19(1):65-85
, and (ii) arbitrary real-valued non-decreasing functions on variables. This resolves a problem, raised by Razborov in 1986, and yields, in a uniform and easy way, non-trivial lower
bounds for circuits computing explicit functions even when . The proof is relatively simple and direct, and combines the bottlenecks counting method of Haken with the idea of finite
limit due to Sipser.
We demonstrate the criterion by super-polynomial lower bounds for explicit Boolean functions, associated with bipartite Paley
graphs and partial t-designs. We then derive exponential lower bounds for clique-like graph functions of Tardos, thus establishing an exponential
gap between the monotone real and non-monotone Boolean circuit complexities. Since we allow real gates, the criterion also
implies corresponding lower bounds for the length of cutting planes proof in the propositional calculus.
Received: July 2, 1996/Revised: Revised June 7, 1998 相似文献
14.
François Rodier 《Designs, Codes and Cryptography》2006,40(1):59-70
Boolean functions on the space
are not only important in the theory of error-correcting codes, but also in cryptography. In these two cases, the nonlinearity
of these functions is a main concept. Carlet, Olejár and Stanek gave an asymptotic lower bound for the nonlinearity of most
of them, and I gave an asymptotic upper bound which was strictly larger. In this article, I improve the bounds and get an
exact limit for the nonlinearity of most of Boolean functions. This article is inspired by a paper of G. Halász about the
related problem of real polynomials with random coefficients.
AMS Classification (2000) Primary: 11T71 · Secondary: 06E30 · 42A05 · 94C10 相似文献
15.
将二重变上限积分看作是一类特殊的一元诱导函数,本文给出了两种二重变上限积分的定义方式,分别对积分限和被积函数做相应的等价无穷小量替换.在一定的条件下,替换后的二重变上限积分与替换前的二重变上限积分是等价无穷小,从而得到一类求极限的方法,并给出了应用实例. 相似文献
16.
We obtain upper bounds on the Hall exponents of symmetric and microsymmetric primitive Boolean matrices respectively. 相似文献
17.
We obtain upper bounds on the Hall exponents of symmetric and microsymmetric primitive Boolean matrices respectively. 相似文献
18.
Siberian Mathematical Journal - Under study are the representations of Boolean functions by formulas. We offer a criterion for the Boolean functions to be repetition-free in the base {V,·,... 相似文献
19.
LIN ShaoBo CAO FeiLong & XU ZongBen Institute for Information System Sciences Xi'an Jiaotong University Xi'an China 《中国科学 数学(英文版)》2011,(9)
In this paper,we investigate the radial function manifolds generated by a linear combination of radial functions.Let Wpr(Bd) be the usual Sobolev class of functions on the unit ball B d.We study the deviation from the radial function manifolds to Wpr(Bd).Our results show that the upper and lower bounds of approximation by a linear combination of radial functions are asymptotically identical.We also find that the radial function manifolds and ridge function manifolds generated by a linear combination of ridg... 相似文献
20.
This paper presents a backward state reduction dynamic programming algorithm for generating the exact Pareto frontier for the bi-objective integer knapsack problem. The algorithm is developed addressing a reduced problem built after applying variable fixing techniques based on the core concept. First, an approximate core is obtained by eliminating dominated items. Second, the items included in the approximate core are subject to the reduction of the upper bounds by applying a set of weighted-sum functions associated with the efficient extreme solutions of the linear relaxation of the multi-objective integer knapsack problem. Third, the items are classified according to the values of their upper bounds; items with zero upper bounds can be eliminated. Finally, the remaining items are used to form a mixed network with different upper bounds. The numerical results obtained from different types of bi-objective instances show the effectiveness of the mixed network and associated dynamic programming algorithm. 相似文献