The complexity of implementation of a threshold symmetric n-place boolean function with threshold k = O(1) via circuits over the basis {boolean OR, boolean AND} is shown not to exceed 2 log(2) k . n + o(n). Moreover, ...
详细信息
The complexity of implementation of a threshold symmetric n-place boolean function with threshold k = O(1) via circuits over the basis {boolean OR, boolean AND} is shown not to exceed 2 log(2) k . n + o(n). Moreover, the complexity of a threshold-2 function is proved to be 2n + Theta(root n), and the complexity of a threshold-3 function is shown to be 3n + O(log n), the corresponding lower bounds are put forward.
A special metric of interest about booleanfunctions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a boolean circuit over the basis {XOR, AND, NOT}. In this...
详细信息
A special metric of interest about booleanfunctions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (J. ACM 22(2), 195-201, 1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. (Theor. Comput. Sci. 235(1), 43-57, 2000) and by Boyar and Peralta (Theor. Comput. Sci. 396(1-3), 223-246, 2008). We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetricfunctions Sigma kn and counting functions Ekn with up to n =25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric Sigma 48 and the counting E48 functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric boolean functions, for each n up to 132.
Exponential sums of symmetric boolean functions are linear recurrent with integer coefficients. This was first established by Cai, Green and Thierauf in the mid nineties. Consequences of this result has been used to s...
详细信息
Exponential sums of symmetric boolean functions are linear recurrent with integer coefficients. This was first established by Cai, Green and Thierauf in the mid nineties. Consequences of this result has been used to study the asymptotic behavior of symmetric boolean functions. Recently, Cusick extended it to rotation symmetric boolean functions, which are functions with good cryptographic properties. In this article, we put all these results in the general context of Walsh transforms and some of its generalizations (nega-Hadamard transform, for example). Precisely, we show that Walsh transforms, for which exponential sums are just an instance, of symmetric and rotation symmetric boolean functions satisfy linear recurrences with integer coefficients. We also provide a closed formula for the Walsh transform and nega-Hadamard transform of any symmetric boolean functions. Moreover, using the techniques presented in this work, we show that some families of rotation symmetric boolean functions are not bent when the number of variables is sufficiently large and provide asymptotic evidence to a conjecture of Stnic and Maitra.
This work brings techniques from the theory of recurrent integer sequences to the problem of balancedness of symmetric boolean functions. In particular, the periodicity modulo p (p odd prime) of exponential sums of sy...
详细信息
This work brings techniques from the theory of recurrent integer sequences to the problem of balancedness of symmetric boolean functions. In particular, the periodicity modulo p (p odd prime) of exponential sums of symmetric boolean functions is considered. Periods modulo p, bounds for periods and relations between them are obtained for these exponential sums. The concept of avoiding primes is also introduced. This concept and the bounds presented in this work are used to show that some classes of symmetric boolean functions are not balanced. In particular, every elementary symmetricboolean function of degree not a power of 2 and less than 2048 is not balanced. For instance, the elementary symmetricboolean function inn variables of degree 1292 is not balanced because the prime p = 176129 does not divide its exponential sum for any positive integer n. It is showed that for some symmetric boolean functions, the set of primes avoided by the sequence of exponential sums contains a subset that has positive density within the set of primes. Finally, in the last section, a brief study for the set of primes that divide some term of the sequence of exponential sums is presented. (C) 2016 Elsevier B.V. All rights reserved.
We study the circuit complexity of booleanfunctions in an infinite basis consisting of all characteristic functions of antichains over the boolean cube. For an arbitrary symmetric function we obtain the exact value o...
详细信息
We study the circuit complexity of booleanfunctions in an infinite basis consisting of all characteristic functions of antichains over the boolean cube. For an arbitrary symmetric function we obtain the exact value of its circuit complexity in this basis. In particular, we prove that the circuit complexities of the parity function and the majority function of n variables for all integers n 1 in this basis are [n+1/2] and [n/2] + 1 respectively. For the maximum circuit complexity of n-variable booleanfunctions in this basis, we show that its order of growth is equal ton.
Fix a field F. The algebraic immunity over F of boolean function f : {0, 1}(n) -> {0, 1} is defined as the minimal degree of a nontrivial (multilinear) polynomial g(x) is an element of F [x(1),..., x(n)] such that ...
详细信息
Fix a field F. The algebraic immunity over F of boolean function f : {0, 1}(n) -> {0, 1} is defined as the minimal degree of a nontrivial (multilinear) polynomial g(x) is an element of F [x(1),..., x(n)] such that f (x) is a constant (either 0 or 1) for all x is an element of {0, 1}(n) satisfying g(x) = 0. Function f is called k robust immune if the algebraic immunity of f is always not less than k no matter how one changes the value of f (x) for k <= |x| = n - k. For any field F, any integers n, k >= 0, we characterize all k robust immune symmetric boolean functions in n variables. The proof is based on a known symmetrization technique and constructing a partition of nonnegative integers satisfying certain (in) equalities about p-adic distance, where p is the characteristic of the field F.
We prove that the complexity of the implementation of the counting function of n boolean variables by binary formulas is at most n(3.03), and it is at most n(4.47) for DeMorgan formulas. Hence, the same bounds are val...
详细信息
We prove that the complexity of the implementation of the counting function of n boolean variables by binary formulas is at most n(3.03), and it is at most n(4.47) for DeMorgan formulas. Hence, the same bounds are valid for the formula size of any threshold symmetric function of n variables, particularly, for the majority function. The following bounds are proved for the formula size of any symmetricboolean function of n variables: n(3.04) for binary formulas and n(4.48) for DeMorgan ones. The proof is based on the modular arithmetic.
We show that, under certain conditions, restricted and biased exponential sums and Walsh transforms of symmetric and rotation symmetric boolean functions are, as in the case of nonbiased domain, C-finite sequences. We...
详细信息
We show that, under certain conditions, restricted and biased exponential sums and Walsh transforms of symmetric and rotation symmetric boolean functions are, as in the case of nonbiased domain, C-finite sequences. We also prove that under other conditions, these sequences are P-finite, which is a somewhat different behavior than their nonbiased counterparts. We further show that exponential sums and Walsh transforms of a family of rotation symmetric monomials over the restricted domain E-n,E-j = {x is an element of F-2(n) : wt ( x) = j} (wt (x) is the weight of the vector x) are given by polynomials of degree at most j, and so, they are also C-finite sequences. Finally, we also present a study of the behavior of symmetric boolean functions under these biased transforms.
A new method for implementing the counting function with boolean circuits is proposed. It is based on modular arithmetic and allows us to derive new upper bounds for the depth of the majority function of n variables: ...
详细信息
Consider the following Stochastic Score Classification problem. A doctor is assessing a patient's risk of developing a disease and can perform n different binary tests on the patient. The probability that test i i...
详细信息
Consider the following Stochastic Score Classification problem. A doctor is assessing a patient's risk of developing a disease and can perform n different binary tests on the patient. The probability that test i is positive is p(i) and the outcomes of the n tests are independent. A patient's score is the total number of positive tests. Possible scores thus range between 0 and n. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient's risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions.
暂无评论