Narrow Results

Consider $T_n$ and $S_n$ to represent the full transformation semigroup and the symmetric group on the set $X_n=\{1,2,\dots ,n\}$, respectively. A subset $S$ of $T_n$ is called an intersecting family if any two transformations $\alpha ,\beta \in S$ coincide at some point $i\in X_n$. An intersecting family $S$ is called maximum if no other intersecting family $S^{\prime }$ exists with $\left|S^{\prime }\right|>\left|S\right|$. Frankl and Deza [On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A22(3) (1977) 352–360] established that the cardinality of a maximum intersecting family of $S_n$ equals $(n-1)!$. Subsequent research demonstrated that a maximum intersecting family of $S_n$ forms a coset of a stabilizer of one point, as shown by Cameron and Ku [Intersecting families of permutations, European J. Combin.24(7) (2003) 881–890] and independently by Larose and Malvenuto [Stable sets of maximal size in Kneser-type graphs, European J. Combin.25(5) (2004) 657–673]. Define $K(n,r)=\{\alpha \in T_n:|\mathrm{\text{im}}(\alpha )|\le r\}$, where $\mathrm{\text{im}}(\alpha )$ denotes the image set of $\alpha$. This paper presents a formula for the cardinality of a maximum intersecting family of $K(n,r)$. It then characterizes the maximum intersecting families of $K(n,r)$ and concludes by determining the number of maximum intersecting families of $K(n,r)$.

Two decision trees are called decision equivalent if they represent the same function, i.e., they yield the same result for every possible input.

We prove that given a decision tree and a number, to decide if there is a decision equivalent decision tree of size at most that number is NP-complete. As a consequence, finding a decision tree of minimal size that is decision equivalent to a given decision tree is an NP-hard problem.

This result differs from the well-known result of NP-hardness of finding a decision tree of minimal size that is consistent with a given training set. Instead our result is a basic result for decision trees, apart from the setting of inductive inference.

On the other hand, this result differs from similar results for BDDs and OBDDs: since in decision trees no sharing is allowed, the notion of decision tree size is essentially different from BDD size.

We employ the Always Approximately Correct or AAC model defined in [35], to prove learnability results for classes of Boolean functions over arbitrary finite Abelian groups. This model is an extension of Angluin's Query model of exact learning. The Boolean functions we consider belong to approximation classes, i.e. functions that are approximable (in various norms) by few Fourier basis functions, or irreducible characters of the domain Abelian group. We contrast our learnability results to previous results for similar classes in the PAC model of learning with and without membership queries.

In addition, we discuss new, natural issues and questions that arise when the AAC model is used. One such question is whether a uniform training set is available for learning any function in a given approximation class. No analogous question seems to have been studied in the context of Angluin's Query model. Another question is whether the training set can be found quickly if the approximation class of the function is completely unknown to the learner, or only partial information about the approximation class is given to the learner (in addition to the answers to membership queries).

In order to prove the learnability results in this paper we require new techniques for efficiently sampling Boolean functions using the character theory of finite Abelian groups, as well as the development of algebraic algorithms. The techniques result in other natural applications closely related to learning, for example, query complexity of deterministic algorithms for testing linearity, efficient pseudorandom generators, and estimating VC dimensions for classes of Boolean functions over finite Abelian groups.

We present a new method for finding closed forms of recursive Boolean function definitions. Traditionally, these closed forms are found by Kleene iteration: iterative approximation until a fixed point is reached. Conceptually, our new method replaces each k-ary function by 2^k Boolean constants defined by mutual recursion. The introduction of an exponential number of constants is mitigated by the simplicity of their definitions and by the use of a novel variant of ROBDDs to avoid repeated computation. Experiments suggest that this approach is significantly faster than Kleene iteration for examples that require many Kleene iteration steps.

We show that every function of several variables on a finite set of k elements with n > k essential variables has a variable identification minor with at least n − k essential variables. This is a generalization of a theorem of Salomaa on the essential variables of Boolean functions. We also strengthen Salomaa's theorem by characterizing all the Boolean functions f having a variable identification minor that has just one essential variable less than f.

It is a difficult task to compute the r-th order nonlinearity of a given function with algebraic degree strictly greater than r > 1. Though lower bounds on the second order nonlinearity are known only for a few particular functions, the majority of which are cubic. We investigate lower bounds on the second order nonlinearity of cubic Boolean functions , where , d_l = 2^il + 2^jl + 1, m, i_l and j_l are positive integers, n > i_l > j_l. Furthermore, for a class of Boolean functions we deduce a tighter lower bound on the second order nonlinearity of the functions, where , d_l = 2^i_lγ + 2^j_lγ + 1, i_l > j_l and γ ≠ 1 is a positive integer such that gcd(n,γ) = 1.

Lower bounds on the second order nonlinearity of cubic monomial Boolean functions, represented by f_μ(x) = Tr(μx^2i+2j+1), , i and j are positive integers such that i > j, were obtained by Gode and Gangopadhvay in 2009. In this paper, we first extend the results of Gode and Gangopadhvay from monomial Boolean functions to Boolean functions with more trace terms. We further generalize and improve the results to a wider range of n. Our bounds are better than those of Gode and Gangopadhvay for monomial functions f_μ(x). Especially, our lower bounds on the second order nonlinearity of some Boolean functions F(x) are better than the existing ones.

The Global Avalanche Characteristics (including the sum-of-squares indicator and the absolute indicator) measure the overall avalanche characteristics of a cryptographic Boolean function. Son et al. (1998) gave the lower bound on the sum-of-squares indicator for a balanced Boolean function. In this paper, we give a sufficient and necessary condition on a balanced Boolean function reaching the lower bound on the sum-of-squares indicator. We also analyze whether these balanced Boolean functions exist, and if they reach the lower bounds on the sum-of-squares indicator or not. Our result implies that there does not exist a balanced Boolean function with n-variable for odd n(n ≥ 5). We conclude that there does not exist a m(m ≥ 1)-resilient function reaching the lower bound on the sum-of-squares indicator with n-variable for n ≥ 7.

Constructing 2m-variable Boolean functions with optimal algebraic immunity based on decomposition of additive group of the finite field seems to be a promising approach since Tu and Deng's work. In this paper, we consider the same problem in a new way. Based on polar decomposition of the multiplicative group of , we propose a new construction of Boolean functions with optimal algebraic immunity. By a slight modification of it, we obtain a class of balanced Boolean functions achieving optimal algebraic immunity, which also have optimal algebraic degree and high nonlinearity. Computer investigations imply that this class of functions also behaves well against fast algebraic attacks.

Recently, Tang, Carlet and Tang presented a combinatorial conjecture about binary strings, allowing proving that all balanced functions in some infinite class they introduced have optimal algebraic immunity. Later, Cohen and Flori completely proved that the conjecture is true. These functions have good (provable or at least observable) cryptographic properties but they are not 1-resilient, which represents a drawback for their use as filter functions in stream ciphers. We propose a construction of an infinite class of 1-resilient Boolean functions with optimal algebraic immunity by modifying the functions in this class. The constructed functions have optimal algebraic degree, that is, meet the Siegenthaler bound, and high nonlinearity. We prove a lower bound on their nonlinearity, but as for the Carlet-Feng functions and for the functions mentioned above, this bound is not enough for ensuring a nonlinearity sufficient for allowing resistance to the fast correlation attack. Nevertheless, as for previously found functions with the same features, there is a gap between the bound that we can prove and the actual values computed for small numbers of variables. Our computations show that the functions in this class have very good nonlinearity and also good immunity to fast algebraic attacks. This is the first time that an infinite class of functions gathers all of the main criteria allowing these functions to be used as filters in stream ciphers.

We consider the problem of evaluating a boolean function P(x₁,…,x_n), by asking queries of the form “x_i=?”, and receiving answers which may not always be truthful. Assuming that the total number of lies does not exceed E, we present an algorithm with cost O(n+s_PE+t_PE), where s_P is the maximal size of a minterm of P(x) and t_P ‘is the maximal size of a maxterm. We also prove that if P is monotone, then any algorithm for evaluating P must ask Ω(s_PE+t_PE) queries for some input.

A key problem in Binary Neural Network learning is to decide bigger linear separable subsets. In this paper we prove some lemmas about linear separability. Based on these lemmas, we propose Multi-Core Learning (MCL) and Multi-Core Expand-and-Truncate Learning (MCETL) algorithms to construct Binary Neural Networks. We conclude that MCL and MCETL simplify the equations to compute weights and thresholds, and they result in the construction of simpler hidden layer. Examples are given to demonstrate these conclusions.

In this work the notion of divergence of elementary cellular automata is introduced and it is analyzed from a cryptographic point of view. Specifically, the balancedness and propagation characteristics are analyzed.

In this work, the notion of curl of elementary cellular automata is introduced as the discrete and extended version of the curl of three-dimensional vector field.

Homogeneous Boolean functions have many applications in computing systems, e.g., cryptography. This paper presents a factorization algorithm for reducing the quantum cost of the reversible circuits for that class of Boolean functions. The algorithm reduces the multi-calculation of any common parts of the circuit. This allows Homogeneous Boolean related applications to be implemented efficiently on novel computing paradigms such as quantum computers and low power devices.

Two parallel algorithms are proposed in this paper for solving the problem of finding exact exclusive-or sum of products (ESOP) expressions for an arbitrary Boolean function. This minimization problem is a very difficult one and solutions have been proposed only for up to seven variables. The processing time for some symmetric functions of seven variables is of the order of weeks. The proposed algorithm is a hybrid one (OpenMP, MPI) and a speed-up of more than nine could be achieved, for a cluster of three nodes with four cores each.

A novel approach is suggested in this paper for the minimization of Boolean expressions. This is particularly useful in logic synthesis, since it leads to simpler logic circuit implementations. Although the proposed method is general, emphasis is given on Exclusive-or Sum Of Products (ESOPs) functions. A transformation is derived to convert the problem from the Boolean algebra area to the classical algebraic area. The resulting problem becomes a nonlinear, integer program and an original branch-and-bound procedure with several relaxations is developed for its solution. The suggested methodology is especially suitable for the minimization of incompletely specified functions, which is a difficult problem in the Boolean area. Numerical examples are provided to demonstrate the applicability and performance of the approach and possible future directions are described. The resulting nonlinear problems can sometimes be very demanding but their challenging solutions could solve open ESOP problems.

This paper presents a method for generating optimum multi-level implementations of Boolean functions based on Satisfiability (SAT) and Pseudo-Boolean Optimization (PBO) problems solving. The method is able to generate one or enumerate all optimum implementations, while the allowed target gate types and gates costs can be arbitrarily specified. Polymorphic circuits represent a newly emerging computation paradigm, where one hardware structure is capable of performing two or more different intended functions, depending on instantaneous conditions in the target operating environment. In this paper we propose the first method ever, generating provably size-optimal polymorphic circuits. Scalability and feasibility of the method are documented by providing experimental results for all NPN-equivalence classes of four-input functions implemented in AND–Inverter and AND–XOR–Inverter logics without polymorphic behavior support being used and for all pairs of NPN–equivalence classes of three-input functions for polymorphic circuits. Finally, several smaller benchmark circuits were synthesized optimally, both in standard and polymorphic logics.

Using logic gates is the traditional way of designing logic circuits. However, in many cases, the use of modules is advantageous as the module is considered a uniform structure composed of multiple gates. In this paper, a nonlinear approach is proposed for designing logic circuits for use as modules multiplexers (MUXs) or Reed–Muller universal blocks (RMs). The experimental results show that the method gives better results compared to other methods available in the literature. The main advantages of the method are that it guarantees minimality and it can also handle Boolean functions for incompletely specified functions. The method is general enough and can be used for any kind of modules.

Boolean expressions are highly involved in control flows of programs and software specifications. Coverage criteria for Boolean expressions aim at producing minimal test suites to detect software faults. There exist various testing criteria, efficiency of which is usually evaluated through mutation analysis. This paper proposes an integer programming-based minimal test suite generation technique relying on mutation analysis. The proposed technique also takes into account the cost of fault detection. The technique is optimal such that the resulting test suite guarantees to detect all the mutants under given fault assumptions, while maximizing the average percentage of fault detection of a test suite. Therefore, the approach presented can also be considered as a reference method to check the efficiency of any common technique. The method is evaluated using four well-known real benchmark sets of Boolean expressions and is also exemplary compared with MCDC criterion. The results show that the test suites generated by the proposed method provide better fault coverage values and faster fault detection.

We introduce the concept of locally internal aggregation function with domain ℝⁿ and values in ℝ, and demonstrate some results which lead to the characterization of such functions.