Computing all monomials of degree n-1 using 2n-3 AND gates

2023/06/06 by Thomas Häner, Häner, Thomas
Computer Science · Mathematics · #Coding theory and cryptography #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2307.07424

openalex publication_date 2023/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the vector-valued Boolean function f:\0,1\ⁿ→ \0,1\ⁿ that outputs all n monomials of degree n-1, i.e., f_i(x)=\bigwedge_{j≠ i}x_j, for n≥ 3. Boyar and Find have shown that the multiplicative complexity of this function is between 2n-3 and 3n-6. Determining its exact value has been an open problem that we address in this paper. We present an AND-optimal implementation of f over the gate set \AND,XOR,NOT\, thus establishing that the multiplicative complexity of f is exactly 2n-3.

Related

• Monomial Testing and Applications
• Algorithms for Testing Monomials in Multivariate Polynomials
• Combinatorial and Algorithmic Properties of One Matrix Structure at Monotone Boolean Functions
• Monomials in arithmetic circuits: Complete problems in the counting hierarchy
• Improved Lower Bounds for Monotone q-Multilinear Boolean Circuits