Linear Decomposition of the Majority Boolean Function using the Ones on Smaller Variables
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916673948221440 |
|---|---|
| author | Chattopadhyay, Anupam Bhattacharjee, Debjyoti Maitra, Subhamoy |
| author_facet | Chattopadhyay, Anupam Bhattacharjee, Debjyoti Maitra, Subhamoy |
| contents | A long-investigated problem in circuit complexity theory is to decompose an $n$-input or $n$-variable Majority Boolean function (call it $M_n$) using $k$-input ones ($M_k$), $k < n$, where the objective is to achieve the decomposition using fewest $M_k$'s. An $\mathcal{O}(n)$ decomposition for $M_n$ has been proposed recently with $k=3$. However, for an arbitrary value of $k$, no such construction exists even though there are several works reporting continual improvement of lower bounds, finally achieving an optimal lower bound $Ω(\frac{n}{k}\log k)$ as provided by Lecomte et. al., in CCC '22. In this direction, here we propose two decomposition procedures for $M_n$, utilizing counter trees and restricted partition functions, respectively. The construction technique based on counter tree requires $\mathcal{O}(n)$ such many $M_k$ functions, hence presenting a construction closest to the optimal lower bound, reported so far. The decomposition technique using restricted partition functions present a novel link between Majority Boolean function construction and elementary number theory. These decomposition techniques close a gap in circuit complexity studies and are also useful for leveraging emerging computing technologies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03262 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Decomposition of the Majority Boolean Function using the Ones on Smaller Variables Chattopadhyay, Anupam Bhattacharjee, Debjyoti Maitra, Subhamoy Logic in Computer Science Hardware Architecture Emerging Technologies A long-investigated problem in circuit complexity theory is to decompose an $n$-input or $n$-variable Majority Boolean function (call it $M_n$) using $k$-input ones ($M_k$), $k < n$, where the objective is to achieve the decomposition using fewest $M_k$'s. An $\mathcal{O}(n)$ decomposition for $M_n$ has been proposed recently with $k=3$. However, for an arbitrary value of $k$, no such construction exists even though there are several works reporting continual improvement of lower bounds, finally achieving an optimal lower bound $Ω(\frac{n}{k}\log k)$ as provided by Lecomte et. al., in CCC '22. In this direction, here we propose two decomposition procedures for $M_n$, utilizing counter trees and restricted partition functions, respectively. The construction technique based on counter tree requires $\mathcal{O}(n)$ such many $M_k$ functions, hence presenting a construction closest to the optimal lower bound, reported so far. The decomposition technique using restricted partition functions present a novel link between Majority Boolean function construction and elementary number theory. These decomposition techniques close a gap in circuit complexity studies and are also useful for leveraging emerging computing technologies. |
| title | Linear Decomposition of the Majority Boolean Function using the Ones on Smaller Variables |
| topic | Logic in Computer Science Hardware Architecture Emerging Technologies |
| url | https://arxiv.org/abs/2504.03262 |