dorsal/arxiv
View SchemaConstant communication complexity protocols for multiparty accumulative boolean functions
| Authors | Sudebkumar Prasant Pal, Sima Das, Somesh Kumar |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0510050 |
| URL | https://arxiv.org/abs/quant-ph/0510050 |
Abstract
Generalizing a boolean function from Cleve and Buhrman \cite{cb:sqec}, we consider the class of {\it accumulative boolean functions} of the form $f_B(X_1,X_2,..., X_m)=\bigoplus_{i=1}^n t_B(x_i^1x_i^2... x_i^m)$, where $X_j=(x^j_1,x^j_2,..., x^j_n), 1\leq j\leq m$ and $t_B(x_i^1x_i^2... x_i^m)=1$ for input $m$-tuples $x_i^1x_i^2...x_i^m\in B\subseteq A\subseteq \{0,1\}^n$, and 0, if $x_i^1x_i^2...x_i^m\in A\setminus B$. Here the set $A$ is the input {\it promise} set for function $f_B$. The input vectors $X_j, 1\leq j\leq m$ are given to the $m\geq 3$ parties respectively, who communicate cbits in a distributed environment so that one of them (say Alice) comes up with the value of the function. We algebraically characterize entanglement assisted LOCC protocols requiring only $m-1$ cbits of communication for such multipartite boolean functions $f_B$, for certain sets $B\subseteq \{0,1\}^n$, for $m\geq 3$ parties under appropriate uniform parity promise restrictions on input $m$-tuples $x_i^1x_i^2...x_i^m, 1\leq i\leq n$. We also show that these functions can be computed using $2m-3$ cbits in a purely classical deterministic setup. In contrast, for certain $m$-party accumulative boolean functions ($m\geq 2$), we characterize promise sets of mixed parity for input $m$-tuples so that $m-1$ cbits of communication suffice in computing the functions in the absence of any a priori quantum entanglement. We compactly represent all these protocols and the corresponding input promise restrictions using uniform group theoretic and hamming distance characterizations.
{
"annotation_id": "32607595-7a9e-4d1a-96f4-3e5595d3651f",
"date_created": "2026-03-02T18:02:20.487000Z",
"date_modified": "2026-03-02T18:02:20.487000Z",
"file_hash": "b5603961d5503a7d590532cb07e1e7a8c94b5f6021ef88345bfb48e2eaec6dfb",
"private": false,
"record": {
"abstract": "Generalizing a boolean function from Cleve and Buhrman \\cite{cb:sqec}, we\nconsider the class of {\\it accumulative boolean functions} of the form\n$f_B(X_1,X_2,..., X_m)=\\bigoplus_{i=1}^n t_B(x_i^1x_i^2... x_i^m)$, where\n$X_j=(x^j_1,x^j_2,..., x^j_n), 1\\leq j\\leq m$ and $t_B(x_i^1x_i^2... x_i^m)=1$\nfor input $m$-tuples $x_i^1x_i^2...x_i^m\\in B\\subseteq A\\subseteq \\{0,1\\}^n$,\nand 0, if $x_i^1x_i^2...x_i^m\\in A\\setminus B$. Here the set $A$ is the input\n{\\it promise} set for function $f_B$. The input vectors $X_j, 1\\leq j\\leq m$\nare given to the $m\\geq 3$ parties respectively, who communicate cbits in a\ndistributed environment so that one of them (say Alice) comes up with the value\nof the function. We algebraically characterize entanglement assisted LOCC\nprotocols requiring only $m-1$ cbits of communication for such multipartite\nboolean functions $f_B$, for certain sets $B\\subseteq \\{0,1\\}^n$, for $m\\geq 3$\nparties under appropriate uniform parity promise restrictions on input\n$m$-tuples $x_i^1x_i^2...x_i^m, 1\\leq i\\leq n$. We also show that these\nfunctions can be computed using $2m-3$ cbits in a purely classical\ndeterministic setup. In contrast, for certain $m$-party accumulative boolean\nfunctions ($m\\geq 2$), we characterize promise sets of mixed parity for input\n$m$-tuples so that $m-1$ cbits of communication suffice in computing the\nfunctions in the absence of any a priori quantum entanglement. We compactly\nrepresent all these protocols and the corresponding input promise restrictions\nusing uniform group theoretic and hamming distance characterizations.",
"arxiv_id": "quant-ph/0510050",
"authors": [
"Sudebkumar Prasant Pal",
"Sima Das",
"Somesh Kumar"
],
"categories": [
"quant-ph"
],
"title": "Constant communication complexity protocols for multiparty accumulative boolean functions",
"url": "https://arxiv.org/abs/quant-ph/0510050"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6e3807fb-d44a-4323-92f3-71933e4c1ea4",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}