Related Experiment Video
Updated: Dec 27, 2025
07:46
Setting Limits on Supersymmetry Using Simplified Models
Published on: November 15, 2013
8.9K
Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions.
Luís T A N Brandão1, Çağdaş Çalık1, Meltem Sönmez Turan1
1Cryptographic Technology Group, National Institute of Standards and Technology - 100 Bureau Drive, Gaithersburg, MD 20899, USA.
Cryptography and Communications : Discrete Structures, Boolean Functions and Sequences
|March 3, 2020
Summary
This study introduces new techniques to reduce the number of AND gates needed for symmetric Boolean functions, achieving better multiplicative complexity (MC) for functions with up to 25 variables.
Area of Science:
- Boolean functions
- Computational complexity theory
- Circuit complexity
Background:
- Multiplicative complexity (MC) is a key metric for Boolean functions.
- Symmetric Boolean functions are invariant under input reordering.
- Previous upper bounds on MC for symmetric functions were established by Boyar et al. and Boyar and Peralta.
Purpose of the Study:
- To investigate and reduce the multiplicative complexity (MC) of symmetric Boolean functions.
- To generate circuits with fewer AND gates for symmetric functions.
- To provide concrete upper bounds for MC for specific symmetric and counting functions.
Main Methods:
- Utilized the Hamming weight method.
- Developed new techniques for circuit construction.
- Generated circuits for symmetric functions up to 25 variables.
Main Results:
- Achieved circuits with fewer AND gates than previously known upper bounds.
- Determined the MC for elementary symmetric and counting functions up to 25 variables.
- Answered specific open questions regarding the MC of and functions, finding MC 6.
- Established upper bounds for the maximum MC in n-variable symmetric Boolean functions up to n=132.
Conclusions:
- The new techniques offer improved multiplicative complexity for symmetric Boolean functions.
- The study provides significant advancements in understanding the circuit complexity of symmetric functions.
- This research contributes to the field of Boolean function analysis and circuit design.
More Related Videos
07:56A Photonic System for Generating Unconditional Polarization-Entangled Photons Based on Multiple Quantum Interference
Published on: September 5, 2019
8.9K
06:35Construction and Systematical Symmetric Studies of a Series of Supramolecular Clusters with Binary or Ternary Ammonium Triphenylacetates
Published on: February 15, 2016
8.4K
Related Concept Videos
01:30Fundamental Theorem of Algebra
150
The Fundamental Theorem of Algebra is central to the study of polynomial equations, asserting that every non-constant polynomial with complex coefficients has at least one complex zero. This means that a polynomial of degree n ≥ 1, written as: with an ≠ 0, has at least one solution in the complex number system. Since the set of real numbers is a subset of complex numbers, this theorem applies equally to polynomials with real coefficients.Building on this result, the...
150
01:14Norton's Theorem
1.3K
Norton's theorem is a fundamental principle stating that a linear two-terminal circuit can be substituted with an equivalent circuit, which comprises a current source (ⅠN) in parallel with a resistor (RN). Here, ⅠN represents the short-circuit current flowing through the terminals, and RN stands for the input or equivalent resistance at the terminals when all independent sources are deactivated. This implies that the circuit illustrated in Figure (a) can be exchanged with the one depicted...
1.3K
01:30The Squeeze Theorem
136
Certain mathematical functions exhibit unpredictable or highly variable behavior near specific input values, making direct evaluation of their limits challenging. This complexity may arise from rapid oscillations or irregular patterns that obscure the function’s trend. In such cases, the Squeeze Theorem offers a reliable method for determining limits.According to the Squeeze Theorem, if a function is confined between two other functions near a particular point, and both outer functions...
136
01:30The Binomial Theorem
186
The Binomial Theorem is a foundational principle in algebra used to expand expressions raised to a power. It provides a structured approach for expanding binomials of the form (a+b)n, where a and b are variables or constants representing algebraic expressions, and n is a non-negative integer.The general form of the Binomial Theorem is:Each term in the expansion involves a binomial coefficient, which is calculated using factorials:The exponent of a in each term decreases from n to 0, while the...
186
01:29Complex Zeros
169
Complex zeros are the solutions to polynomial equations that include imaginary numbers, specifically, numbers of the form a + bi, where a and b are real numbers and i is the imaginary unit defined by i2=-1. These zeros satisfy the equation P(x) = 0, where P(x) is a polynomial with real or complex coefficients. Since the complex number system includes all real numbers, it provides a complete framework for analyzing all possible roots of a polynomial.Every polynomial of degree n≥1 can be...
169
02:40MO Theory and Covalent Bonding
13.3K
The molecular orbital theory describes the distribution of electrons in molecules in a manner similar to the distribution of electrons in atomic orbitals. The region of space in which a valence electron in a molecule is likely to be found is called a molecular orbital. Mathematically, the linear combination of atomic orbitals (LCAO) generates molecular orbitals. Combinations of in-phase atomic orbital wave functions result in regions with a high probability of electron density, while...
13.3K