On the Fourier spectrum of symmetric Boolean functions

We study the following questionWhat is the smallest t such that every symmetric boolean function on κ variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?We exclude the constant functions for which there is no such t and the parity functions for which t has to be κ. Let τ (κ) be the smallest such t. Our main result is that for large κ, τ (κ)≤4κ/logκ.The motivation for our work is to understand the complexity of learning symmetric juntas. A κ-junta is a boolean function of n variables that depends only on an unknown subset of κ variables. A symmetric κ-junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric κ-juntas, in the uniform PAC learning model, in time n ^o(κ) . This improves on a result of Mossel, O’Donnell and Servedio in [16], who show that symmetric κ-juntas can be learned in time n ^2κ/3.     

On the minimal fourier degree of symmetric Boolean functions

In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function. Specifically, we prove that for every non-linear and symmetric f: {0, 1} ^k → {0, 1} there exists a set; \(\not 0 \ne S \subset [k]\) such that ¦S¦ = O(Γ(k)+√k, and \(\hat f(S) \ne 0\) where Γ(m)≤m ^0.525 is the largest gap between consecutive prime numbers in {1,..., m}. As an application we obtain a new analysis of the PAC learning algorithm for symmetric juntas, under the uniform distribution, of Mossel et al. [10]. Our bound on the degree is a significant improvement over the previous result of Kolountzakis et al. [8] who proved that ¦S¦=O(k=log k). We also show a connection between lower-bounding the degree of non-constant functions that take values in {0,1,2} and the question that we study here.     

Complexity and depth of formulas for symmetric Boolean functions

A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis B₂ of all dyadic functions and over the standard basis B₀ = {∧, ∨,^- } were non-constructively obtained. In particular, the depth of multiplication of n-bit binary numbers is asymptotically estimated from above by 4.02 log₂n relative to the basis B₂ and by 5.14log₂n relative to the basis B₀.     

Upper bounds on the depth of symmetric Boolean functions

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: 3.34log₂ n over the basis B ₂ of all binary Boolean functions and 4.87log₂ n over the standard basis B ₀ = {∧, ∨, ?}. As a consequence, the depth of the multiplication of n-digit binary numbers does not exceed 4.34log₂ n and 5.87log₂ n over the bases B ₂ and B ₀, respectively. The depth of implementation of an arbitrary symmetric Boolean function of n variables is shown to obey the bounds 3.34log₂ n and 4.88log₂ n over the same bases.     

FP-软布尔代数

将FP-软集(Fuzzy Parameterized Soft Sets)与布尔代数相结合,定义了FP-软布尔代数、FP-软布尔子代数、FP-软布尔代数的FP-软理想、FP-理想软布尔代数等概念,研究了它们的相关性质.最后,讨论了FP-软布尔代数的同态.     

On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2

We improve parts of the results of [T. W. Cusick, P. Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Mathematics 258 (2002) 289-301; J. Pieprzyk, C. X. Qu, Fast hashing and rotation-symmetric functions, Journal of Universal Computer Science 5 (1) (1999) 20-31]. It is observed that the n-variable quadratic Boolean functions, for , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weights and nonlinearity are exactly characterized by the cyclic subgroup 〈s−1〉 of Z_n. If , the order of s−1, is even, the weight and nonlinearity are the same and given by . If the order is odd, it is balanced and nonlinearity is given by .     

Tests for multiple monotone symmetric conglutinations of variables in Boolean functions

A linear lower and a quadratic upper bound on the Shannon function for the length of a detecting test for multiple monotone symmetric conglutinations are proved. Additionally, the exact value of the Shannon function for the length of a diagnostic test for multiple monotone symmetric conglutinations is found. Some of the variables of a Boolean function are said to conglutinate if each of them is replaced by a function of these variables. A conglutination is called multiple if there are several groups of conglutinated variables.     

Upper bounds for the formula size of symmetric Boolean functions

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 symmetric Boolean 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.     

On generalized Boolean functions i

In this paper we introduce the concept of generalized Boolean function. Such a function has its arguments and values in a Boolean algebra and can be written in a manner similar to the canonical disjunctive form, but instead of the product of simple or complemented variables, the product of values of certain functions is used. Every Boolean function is a generalized Boolean one but the converse is not true. The set of all generalized Boolean function “generated” by some fixed function is a Boolean algebra.     

On generalized Boolean functions II

This cycle of papers is based on the concept of generalized Bolean functions introduced by the author in the first article of the series. Every generalized Boolean function f:Bⁿ→B can be written in a manner similar to the canonical disjunctive form using some function defined on A×B, where A is a finite subset of B containing 0 and 1. The set of those functions f is denoted by GBF_n[A]. In this paper the following questions are presented: (1) What is the relationship between GBF_n[A₁] and GBF_n[A₂] when A₁A₂. (2) What can be said about GBF_n[A₁∩A₂] and GBF_n[A₁A₂] in comparison with GBF_n[A₁]∩GBF_n[A₂] and GBF_n[A₁]GBF_n[A₂], respectively.     

On complemented subspaces ofm

It is proved that an infinite dimensional subspace ofm is complemented inm if and only if it is isomorphic tom. The research reported in this document has been sponsored by the Air Force Office of Scientific Research under Grant AF EOAR 66-18, through the European Office of Aerospace Research (OAR) United States Air Force.     

On Boolean ranges of Banaschewski functions

We construct a countable lattice \({\varvec{\mathcal {S}}}\) isomorphic to a bounded sublattice of the subspace lattice of a vector space with two non-iso-morphic maximal Boolean sublattices. We represent one of them as the range of a Banaschewski function and we prove that this is not the case of the other. Hereby we solve a problem of F. Wehrung. We study coordinatizability of the lattice \({\varvec{\mathcal {S}}}\). We prove that although it does not contain a 3-frame, the lattice \({\varvec{\mathcal {S}}}\) is coordinatizable. We show that the two maximal Boolean sublattices correspond to maximal Abelian regular subalgebras of the coordinatizating ring.