Investigating the Power of Circuits with MOD₆ Gates

2018/10/12 by Daniel J. Saunders, Saunders, Daniel J.
Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.1810.05603

openalex publication_date 2018/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the power of Boolean circuits with MOD₆ gates. First, we introduce a few basic notions of computational complexity, and describe the standard models with which we study the complexity of problems. We then define the model of Boolean circuits, equate a restricted class of circuits with an algebraic model, and present some results from working with this algebra.

Related

• Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth
• Intermediate problems in modular circuits satisfiability
• On the Incompressibility of Truth With Application to Circuit Complexity
• Determining the Multiplicative Complexity of Boolean Functions using SAT
• When Six Gates are Not Enough