We investigate the max min of the algebraic degree and the nonlinearity of a boolean function inn variables when restricted to a k-dimensional affine subspace of Fn2. Previous authors have focused on the cases when th...
详细信息
We investigate the max min of the algebraic degree and the nonlinearity of a boolean function inn variables when restricted to a k-dimensional affine subspace of Fn2. Previous authors have focused on the cases when the max min of the algebraic degree is 0 or 1. Upper bounds, lower bounds and a conjecture on the exact value in special cases are presented. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
We study the relationship between the Walsh Transform of a boolean function and its Algebraic Normal Form(ANF), and present algorithms that compute the Walsh coefficients at a small set of points in terms of certain p...
详细信息
We study the relationship between the Walsh Transform of a boolean function and its Algebraic Normal Form(ANF), and present algorithms that compute the Walsh coefficients at a small set of points in terms of certain parameters derived from the ANF of a boolean function. In the first part of this paper, based on the previous result by Gupta and Sarkar, we investigate the formula in Gupta-Sarkar's algorithm in a novel iterative method and obtain a recurrence relation for the Walsh Transform of a boolean function. The second part is devoted to applying this formula to algorithms to evaluate it. Experimental result shows that for the specified classes of boolean functions, our algorithms can perform better than Gupta-Sarkar's algorithm. For example, the proposed algorithm "Compute Walsh" is able to compute the Walsh coefficients of the functions for which the complexity of Gupta-Sarkar's algorithm is impractical. Besides, for functions acting on high number of variables (m > 30) and having low number of monomials, the proposed algorithms are advantageous over the Fast Walsh Transform which is a standard method of computing the Walsh Transform with a complexity of O(m2(m)) operations.
We introduce a new transform on boolean functions generalizing the Walsh-Hadamard transform. For boolean functions q and f, the q-transform of f measures the proximity of f to the set of functions obtained from q by c...
详细信息
We introduce a new transform on boolean functions generalizing the Walsh-Hadamard transform. For boolean functions q and f, the q-transform of f measures the proximity of f to the set of functions obtained from q by change of basis. This has implications for security against certain algebraic attacks. In this paper, we derive the expected value and second moment (Parseval's equation) of the q-transform, leading to a notion of q-bentness. We also develop a Poisson summation formula, which leads to a proof that the q-transform is invertible.
We study the relationship between the Walsh transform and the algebraic normal form (ANF) of a boolean function. In the first part of the paper, we obtain a formula for the Walsh transform at a certain point in terms ...
详细信息
We study the relationship between the Walsh transform and the algebraic normal form (ANF) of a boolean function. In the first part of the paper, we obtain a formula for the Walsh transform at a certain point in terms of parameters derived from the algebraic normal form. We use previous results by Carlet and Guillot to obtain an explicit expression for the Walsh transform at a point in terms of parameters derived from the ANF. The second part of the paper is devoted to simplify this formula And develop an algorithm to evaluate it. This algorithm can be applied in situations where it is practically impossible to use the fast Walsh transform algorithm. Experimental results show that under certain conditions it is possible to execute our algorithm to evaluate the Walsh transform (at a small set of points) of functions on a few scores of variables having a few hundred terms in the algebraic normal form.
In this paper, a general problem of the robust template decomposition with restricted weights for cellular neural networks (CNNs) implementing an arbitrary boolean function is investigated. First, the geometric margin...
详细信息
In this paper, a general problem of the robust template decomposition with restricted weights for cellular neural networks (CNNs) implementing an arbitrary boolean function is investigated. First, the geometric margin of a linear classifier with respect to a training data set is used to de. ne the robustness of an uncoupled CNN implementing a linearly separable boolean function. Second, maximal margin classifiers, i.e. robust CNNs, for such boolean functions can be designed via support vector machines (SVMs). Third, some general properties of robust CNNs with or without restricted weights are discussed. Moreover, all robust CNNs with restricted weights are characterized. Finally, for an arbitrarily given boolean function, we propose an algorithm, which is the generalized version of the well-known CFC algorithm, to find a sequence of robust uncoupled CNNs implementing the given boolean function. Several illustrative examples demonstrate the efficiency of the proposed method. It will be seen that, in general, the tradeoff between the complexity regarding the number of terms in the decomposition and the guaranteed robustness regarding the geometric margins of the resulting CNNs must be made in the robust template decomposition with restricted weights.
Consider a hypercube of 2(n) points described by n boolean variables and a subcube of 2(m) points. m less than or equal to n. As is well-known, the boolean function with value 1 in the points of the subcube can be exp...
详细信息
Consider a hypercube of 2(n) points described by n boolean variables and a subcube of 2(m) points. m less than or equal to n. As is well-known, the boolean function with value 1 in the points of the subcube can be expressed as the product (AND) of n - m variables. The standard synthesis of arbitrary functions exploits this property. We extend the concept of subcube to the more powerful pseudocube. The basic set is still composed of 2(m) points, but has a more general form. The function with value 1 in a pseudocube, called pseudoproduct, is expressed as the AND of n - m EXOR-factors, each containing at most m + 1 variables. Subcubes are special cases of pseudocubes and their corresponding pseudoproducts reduce to standard products. An arbitrary boolean function can be expressed as a sum of pseudoproducts (SPP). This expression is in general much shorter than the standard sum of products. as demonstrated on some known benchmarks. The logical network of an n-bit adder is designed in SPP, as a relevant example of application of this new technique. A class of symmetric functions is also defined, particularly suitable for SPP representation.
In quantum computation, designing an optimal exact quantum query algorithm (i.e., a quantum decision tree algorithm) for any small input boolean function is a fundamental and abstract problem. As we are aware, there i...
详细信息
In quantum computation, designing an optimal exact quantum query algorithm (i.e., a quantum decision tree algorithm) for any small input boolean function is a fundamental and abstract problem. As we are aware, there is not a general method for this problem. Due to the fact that every boolean function can be represented by a sum-of-squares of some multilinear polynomials, in this paper a primary algorithm framework is proposed with three basic steps: The first basic step is to find sum-of-squares representations of the boolean function and its negation function;the second basic step is to construct a state which is assumed to be the final state of an optimal exact quantum query algorithm;the third basic step is to find each unitary operator in the undetermined algorithm. However, there still exist some intractable problems such that the algorithm framework may not be feasible in some cases, but it can be used to investigate the quantum query model with low complexity, such as Deutsch's problem, a five-bit symmetric boolean function and the characterization of boolean functions with exact quantum 2-query complexity.
We focus on energy complexity, a boolean function measure related closely to boolean circuit design. Given a circuit C over the standard basis {boolean OR(2), Lambda(2), (sic)}, the energy complexity of C, denoted by ...
详细信息
We focus on energy complexity, a boolean function measure related closely to boolean circuit design. Given a circuit C over the standard basis {boolean OR(2), Lambda(2), (sic)}, the energy complexity of C, denoted by EC(C), is the maximum number of its activated inner gates over all inputs. The energy complexity of a boolean function f, denoted by EC(f), is the minimum of EC(C) over all circuits C computing f. Recently, K. Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738-750, 2018) gave EC(f) an upper bound by the decision tree complexity, EC(f) = O(D(f)(3)). On the input size n, They also showed that EC(f) is at most 3n - 1. For the lower bound side, they showed that EC(f) >= 1/3 psens(f), where psens(f) is called positive sensitivity. A remained open problem is whether the energy complexity of a boolean function has a polynomial relationship with its decision tree complexity. Our results for energy complexity can be listed below. - For the lower bound, we prove the equation that EC(f) = Omega(root D(f)), which answers the above open problem. - For upper bounds, EC(f) <= min{1/2 D(f)(2) + O(D(f)), n + 2D(f) - 2} holds. - For non-degenerated functions, we also provide another lower bound EC(f) = Omega(log n) where n is the input size. - We also discuss the energy complexity of two specific function classes, OR functions and ADDRESS functions, which implies the tightness of our two lower bounds respectively. In addition, the former one answers another open question in Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738-750, 2018) asking for non-trivial lower bound for energy complexity of OR functions.
The influence of a variable is an important concept in the analysis of boolean functions. The more general notion of influence of a set of variables on a boolean function has four separate definitions in the literatur...
详细信息
The influence of a variable is an important concept in the analysis of boolean functions. The more general notion of influence of a set of variables on a boolean function has four separate definitions in the literature. In the present work, we introduce a new definition of influence of a set of variables which is based on the auto-correlation function and develop its basic theory. Among the new results that we obtain are generalizations of the Poincare inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterizations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et al. [Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), Vancouver, BC, Canada, IEEE Computer Society, 2002, pp. 103-112] and Blais [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, M. Mitzenmacher, ed., Bethesda, MD, ACM, 2009, pp. 151-158] is half the value of the auto-correlation based influence that we introduce. Regarding the other prior notions of influence, we make a detailed study of these and show that each of these definitions does not satisfy one or more desirable properties that a notion of influence may be expected to satisfy.
Tunnel field-effect transistors (TFETs) have been explored extensively as a possible substitute for MOSFETs, especially for digital system design applications. Unlike conventional MOSFET devices, TFETs exhibit certain...
详细信息
Tunnel field-effect transistors (TFETs) have been explored extensively as a possible substitute for MOSFETs, especially for digital system design applications. Unlike conventional MOSFET devices, TFETs exhibit certain unique characteristics which are suitable for energy-efficient digital system design. In this paper, we report the use of a single device with both terminals biased independently for basic two-input boolean logic operations AND, OR, NAND, and NOR using technology computer-aided design (TCAD) simulations. It is shown that these basic boolean operations can be realized by minimally altering the design of a double-gate vertical TFET (DGVTFET) device and by selecting the appropriate device characteristics. The results show that when the boolean functions are implemented, the ION/IOFF ratio is in the range of 109 to 1013 at a supply voltage VDD = 1 V. Simulation results show that the use of a gate-source overlap technique and the selection of a suitable silicon body thickness are vital to obtaining distinct logic functions using a DGVTFET.
暂无评论